-
Notifications
You must be signed in to change notification settings - Fork 0
/
tDeque.h
197 lines (171 loc) · 5.46 KB
/
tDeque.h
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#ifndef S_DEQUE_H_
#define S_DEQUE_H_
#include <iostream>
#include <sstream>
#include <stdexcept>
#define INIT_SIZE 8 // initialize size
template <typename T> class Deque {
private:
// Private members
T* queue;
unsigned int back;
unsigned int front;
unsigned int capacity;
unsigned int size_of_queue;
int get_capacity() { return capacity; }
int get_front() { return front; }
int get_back() { return back; }
/* Helper function that handles the array recreation for grow() and shrink() */
// Create a new array with passed in capacity; temp
// Store a counter for the new index; new_index
// Iterate from back + 1 to front, modding by the old capacity
// Assign current element in queue to element @ new_index in temp
// Increment new_index
// Assign 0 to back
// Assign new_index to front
// Assign temp to new queue
// Update capacity
void change_capacity(int new_capacity) {
std::string* temp = new std::string[new_capacity];
int new_index(1);
for (int i = (back + 1) % capacity; i != (front + 1) % capacity; i = (i + 1) % capacity) {
temp[new_index] = queue[i];
++new_index;
}
back = 0;
front = new_index - 1;
queue = temp;
capacity = new_capacity;
}
/* Method used for automatically increasing the size of the dequeue
* To be used whenever the dequeue reaches full capacity
* Doubles the capacity
*/
// Call helper function, passing the new capacity
void grow() {
int new_capacity = capacity * 2;
change_capacity(new_capacity);
}
/* Method used for automatically decreasing the size of the dequeue
* To be used whenever the dequeue reaches less than 1/4 of its full capacity
* Cuts capacity in half
*/
// Half the capacity and store in temp variable
// Call helper function, passing the new capacity
void shrink() {
int new_capacity = capacity / 2;
change_capacity(new_capacity);
}
public:
//Constructor
Deque() {
capacity = INIT_SIZE;
queue = new std::string[capacity];
back = 0;
front = 0;
size_of_queue = 0;
}
//Destructor
~Deque() {
delete [] queue;
}
/* Inserts the element at the front of the queue. */
// Check for full capacity
// If full, grow
// Increment front, accounting for wrap around
// Assign item to the element at index front
// Increment size_of_queue
// Catch bad_alloc exception if free store runs dry and throw descriptive runtime_error exception
void push_front(std::string item) {
try {
if ( ( (front + 1) % capacity ) == back) { // queue is full
grow();
}
front = (front + 1) % capacity;
queue[front] = item;
++size_of_queue;
} catch (std::bad_alloc out_of_mem) {
throw std::runtime_error("Program has run out of memory");
}
}
/* Inserts the element at the back of the queue */
// Check for full capacity
// If full, grow
// Decrement back, accounting for wrap around
// Assign item to the queue at index back
// Increment size_of_queue
// Catch bad_alloc exception if free store runs dry and throw descriptive runtime_error exception
void push_back(std::string item) {
try {
if ((back - 1) % capacity == front) { // queue is full
grow();
}
queue[back] = item;
back = (back - 1) % capacity;
++size_of_queue;
} catch (std::bad_alloc out_of_mem) {
throw std::runtime_error("Program has run out of memory");
}
}
/* Removes and returns the element at the front of the queue. */
// Check for empty deque
// If empty, throw runtime error
// Check for under 1/4 capacity
// If under, shrink
// Assign current front item to temp
// Decrement front, accounting for wrap around
// Decrement size_of_queue
// Return temp
std::string pop_front() {
if (empty() ) {
throw std::runtime_error("Deque is empty; cannot pop");
}
if ( (size_of_queue - 1 < capacity / 4) && (capacity != 8) ) {
shrink();
}
std::string temp = queue[front];
front = (front - 1) % capacity;
--size_of_queue;
return temp;
}
/* Removes and returns the element at the back of the queue. */
// Check for empty deque
// If empty, throw runtime error
// Check for under 1/4 capacity
// If under, shrink
// Assign current back item to temp
// Increment back, accounting for wrap around
// Decrement size_of_queue
// Return temp
std::string pop_back() {
if (empty() ) {
throw std::runtime_error("Deque is empty; cannot pop");
}
if ( (size_of_queue - 1 < capacity / 4) && (capacity != 8) ) {
shrink();
}
std::string temp = queue[back];
back = (back + 1) % capacity;
--size_of_queue;
return temp;
}
/* Returns the number of elements in the queue. */
int size() {
return size_of_queue;
}
/* Tells whether the queue is empty or not. */
bool empty() {
return front == back;
}
/* Puts the contents of the queue from front to back into a
* return string with each string item followed by a newline
*/
std::string toStr() {
std::ostringstream oss; // Instantiate string stream
for (int i = front; i != back; i = (i - 1) % capacity) { // Iterate through queue, accounting for wrap-around
oss << queue[i] << std::endl; // Output the ith element, followed by a newline, to the string stream
}
return oss.str(); // Convert the string stream to a string and return it
}
};
#endif /* S_DEQUE_H_ */