blob: 1cc14c3e3d92937c334ec6b6c055c26b6aeb83fc (
plain) (
blame)
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
|
#include <iostream>
template <typename T>
class Queue
{
T* data;
size_t capacity;
size_t count;
size_t head; //where to get
size_t tail; //last added element;
void resize(size_t newCapacity);
public:
Queue();
void enqueue(const T& obj);
T dequeue();
size_t getCount();
size_t isEmpty();
};
template <typename T>
Queue<T>::Queue()
{
capacity = 4;
data = new T[capacity];
count = 0;
head = tail = 0;
}
template <typename T>
void Queue<T>::enqueue(const T& obj)
{
if (count == capacity)
resize(capacity * 2);
if (count != 0)
tail++;
tail %= capacity; //so we don't get an out of range exception
data[tail] = obj;
count++;
}
template <typename T>
T Queue<T>::dequeue()
{
if (count == 0)
throw std::exception("The collection is empty!");
T toReturn = data[head];
(++head) %= capacity;
count--;
return toReturn;
}
template <typename T>
size_t Queue<T>::getCount()
{
return count;
}
template <typename T>
size_t Queue<T>::isEmpty()
{
return getCount() == 0;
}
template <typename T>
void Queue<T>::resize(size_t newCapacity)
{
T* newData = new T[newCapacity];
for (int i = 0, ind = head; i < count; i++, (++ind) %= capacity)
newData[i] = data[ind];
delete[] data;
capacity = newCapacity;
data = newData;
head = 0;
tail = count - 1;
}
|
