Handout 6
A Queue Example Implementation
1 // queue example
2
3 #include <iostream.h>
4 #include "queue.h"
5 int main() {
6 Queue A(3);
7
8 A.enQueue(99);
9 for(int i = 0; i < 5; i++) {
10 if(!A.isFull()) A.enQueue(i);
11 A.display();
12 if(!A.isEmpty()) QueueDataType x = A.deQueue();
13 }
14 return 0;
15 }
16
17 /* program output
18
19 number of elements in the queue = 2
20 element = 0 : 99
21 element = 1 : 0
22 number of elements in the queue = 2
23 element = 1 : 0
24 element = 2 : 1
25 number of elements in the queue = 2
26 element = 2 : 1
27 element = 0 : 2
28 number of elements in the queue = 2
29 element = 0 : 2
30 element = 1 : 3
31 number of elements in the queue = 2
32 element = 1 : 3
33 element = 2 : 4
34
35 */
36
37 // ====================================================================
38
39 // queue.h
40
41 #ifndef QUEUE_H
42 #define QUEUE_H
43
44 #define MAXQUEUESIZE 100
45 #define QueueDataType int
46
47 class Queue {
48 public:
49 Queue(); //default constructot
50 Queue(int); // one parameter constructor
51 ~Queue(); // destructor
52 enQueue(QueueDataType); // add an element
53 QueueDataType deQueue(); // remove an element
54 bool isEmpty(); // returns true if empty
55 bool isFull(); // return true if full
56 display(); // shows queue contents
57 private:
58 int queueFront; // array index for front of queue
59 int queueRear; // array index for rear of queue
60 int queueElements; // number of elements currently in queue
61 int queueSize; // maximum number of elements in queue
62 int * theQueue; // pointer to first queue element
63 };
64
65 #endif
66
67 // ====================================================================
68
69 // queue.cpp
70
71 #include <iostream.h>
72 #include "queue.h"
73
74 /* Implementation Notes
75 Circular queue using an array. Note that the implementation
76 uses a count of the number of queue elements (queueElements)
77 to avoid the issue of leaving an empty slot in the queue
78 for detection of the empty versus one element queue question.
79 */
80
81 Queue::Queue() { //default constructor
82 queueFront = 0;
83 queueRear = 0;
84 queueElements = 0;
85 queueSize = MAXQUEUESIZE;
86 theQueue = new QueueDataType[MAXQUEUESIZE];
87 }
88
89 Queue::Queue(int size) { // one parameter constructor
90 queueFront = 0;
91 queueRear = 0;
92 queueElements = 0;
93 queueSize = size;
94 theQueue = new QueueDataType[size];
95 }
96
97 Queue::~Queue() { // destructor
98 delete [] theQueue;
99 }
100
101 Queue::enQueue(QueueDataType dataValue) { // add an element
102 queueElements++;
103 if(queueElements != 1)
104 queueRear = (queueRear + 1) % queueSize;
105 theQueue[queueRear] = dataValue;
106 }
107
108 QueueDataType Queue::deQueue() { // remove an element
109 QueueDataType valueToReturn = theQueue[queueFront];
110 if(queueElements != 1)
111 queueFront = (queueFront + 1) % queueSize;
112 queueElements--;
113 return valueToReturn;
114 }
115
116 bool Queue::isEmpty() { // returns true if empty
117 if(queueElements == 0) return true;
118 else return false;
119 }
120
121 bool Queue::isFull() { // return true if full
122 if((queueRear + 1) % queueSize == queueFront) return true;
123 else return false;
124 }
125
126 Queue::display() { // shows queue contents
127 int queuePointer = queueFront;
128 cout << "number of elements in the queue = " << queueElements << endl;
129
130 for(int i = 0; i < queueElements; i++) {
131 cout << "element = " << ((queueFront + i) % queueSize) << " : "
132 << theQueue[(queueFront + i) % queueSize] << endl;
133 }
134 }