-
Notifications
You must be signed in to change notification settings - Fork 0
/
Queue.cpp
95 lines (77 loc) · 2.87 KB
/
Queue.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// Honor Pledge:
//
// I pledge that I have neither given nor receieved any help
// on this assignment.
template <typename T>
Queue <T>::Queue (void)
: array_ (Array <T> ())
{
} // end default constructor
template <typename T>
Queue <T>::Queue (const Queue & queue)
: array_ (Array <T> (queue.size()))
{
// COMMENT Your code will eventually crash since queue will be sharing
// the same array allocation.
// SOLUTION Dr. Hill, I resolved this issue by allocating the array on the stack.
array_ = queue.array_;
} // end copy constructor
template <typename T>
Queue <T>::~Queue (void)
{
// nothing allocated in this class to delete
} // end destructor
template <typename T>
const Queue <T> & Queue <T>::operator = (const Queue & rhs)
{
// COMMENT Always check for self assignment.
// SOLUTION Dr. Hill, I resolved this issue by adding an if branch that returns the
// self (this) pointer if the object is being assigned to itself.
// COMMENT Your code will eventually crash since queue will be sharing
// the same array allocation.
// SOLUTION Dr. Hill, I resolved this issue by allocating the array on the stack.
if (this == &rhs) {
// do nothing
} else {
// change the current array to be equal to passed in array
array_ = rhs.array_;
} // end if-else
return *this;
} // end operator =
template <typename T>
void Queue <T>::enqueue (T element)
{
array_.resize (array_.size() + 1);
// size is now updated with the new size, hence
array_ [array_.size() - 1] = element;
} // end enqueue
template <typename T>
T Queue <T>::dequeue (void)
{
if (is_empty()) {
empty_exception ex;
throw ex;
} // end if
else {
T first_element = array_[0];
// COMMENT This design is OK, but it is not the best design. This will be
// a very expensive array to use if you are dequeing a lot of elements. This
// is because you are copying N elements each time you dequeue 1 element.
// Instead, you only want to copy element when necessary. Come up with a better
// design that is not as expensive for the client to use.
// SOLUTION Dr. Hill, instead of copying each element over to dequeue one element
// each time, I used the existing reverse method of the array to delete the element using
// the resize method and then reversing back the contents again. However, it is not
// any better in terms of performance, now that I think about it, because the reverse
// method also makes copies of elements to move them around. It just makes the design look cleaner.
array_.reverse ();
array_.resize (array_.size () - 1);
array_.reverse ();
return first_element;
} // end else
} // end dequeue
template <typename T>
void Queue <T>::clear (void)
{
array_.resize (0);
} // end clear