« Queues using Arrays

QueueUsingArray.h

Copy
1template <typename T>
2
3class QueueUsingArray
4{
5private:
6    T *data;
7    int nextIndex;
8    int firstIndex;
9    int size;
10    int capacity;
11
12public:
13    QueueUsingArray(int s)
14    {
15        data = new T[s];
16        nextIndex = 0;
17        firstIndex = -1;
18        size = 0;
19        capacity = s;
20    }
21
22    int getSize() const { return size; }
23
24    bool isEmpty() const { return size == 0; }
25
26    void enqueue(T element)
27    {
28        // static size queue
29        //  if (size == capacity)
30        //  {
31        //      cout << "Queue Full" << endl;
32        //      return;
33        //  }
34        //  data[nextIndex] = element;
35        //  nextIndex = ((nextIndex + 1) % capacity);
36        //  if (firstIndex == -1)
37        //  {
38        //      firstIndex = 0;
39        //  }
40        //  size++;
41
42        // dynamic size queue
43        if (size == capacity)
44        {
45            T *newData = new T[2 * capacity];
46            int j = 0;
47            for (int i = firstIndex; i < capacity; i++)
48            {
49                newData[j] = data[i];
50                j++;
51            }
52            for (int i = 0; i < firstIndex; i++)
53            {
54                newData[j] = data[i];
55                j++;
56            }
57            delete[] data;
58            data = newData;
59            firstIndex = 0;
60            nextIndex = capacity;
61            capacity = 2 * capacity;
62        }
63        data[nextIndex] = element;
64        nextIndex = ((nextIndex + 1) % capacity);
65        if (firstIndex == -1)
66        {
67            firstIndex = 0;
68        }
69        size++;
70    }
71
72    T front()
73    {
74        if (isEmpty())
75        {
76            cout << "Queue is empty !" << endl;
77            return 0;
78        }
79        return data[firstIndex];
80    }
81
82    T dequeue()
83    {
84        if (isEmpty())
85        {
86            cout << "Queue is empty !" << endl;
87            return 0;
88        }
89
90        T ans = data[firstIndex];
91        firstIndex = (firstIndex + 1) % capacity;
92        size--;
93        if (size == 0)
94        {
95            firstIndex = -1;
96            nextIndex = 0;
97        }
98        return ans;
99    }
100};