Circular Queue
In this lesson, we will explore the concept of a circular queue and how it is implemented. A circular queue is a variation of a regular queue where the last element points to the first element making a circular link. This allows us to reuse the empty spaces in the queue efficiently.
Implementation
To implement a circular queue, we can use an array of fixed size and maintain two pointers: front and rear. The front pointer keeps track of the first element, and the rear pointer keeps track of the last element. Initially, both pointers are set to -1 to indicate an empty queue.
Here is a C++ implementation of a circular queue:
1#include <iostream>
2using namespace std;
3
4const int SIZE = 5;
5
6class CircularQueue {
7private:
8 int front;
9 int rear;
10 int arr[SIZE];
11
12public:
13 CircularQueue() {
14 front = -1;
15 rear = -1;
16 }
17
18 bool isEmpty() {
19 return front == -1 && rear == -1;
20 }
21
22 bool isFull() {
23 return (rear + 1) % SIZE == front;
24 }
25
26 void enqueue(int item) {
27 if (isFull()) {
28 cout << "Queue is full. Unable to enqueue." << endl;
29 } else if (isEmpty()) {
30 front = rear = 0;
31 arr[rear] = item;
32 } else {
33 rear = (rear + 1) % SIZE;
34 arr[rear] = item;
35 }
36 }
37
38 void dequeue() {
39 if (isEmpty()) {
40 cout << "Queue is empty. Unable to dequeue." << endl;
41 } else if (front == rear) {
42 cout << "Dequeued " << arr[front] << endl;
43 front = rear = -1;
44 } else {
45 cout << "Dequeued " << arr[front] << endl;
46 front = (front + 1) % SIZE;
47 }
48 }
49};
50
51int main() {
52 // Create a circular queue object
53 CircularQueue q;
54
55 // Enqueue elements
56 q.enqueue(10);
57 q.enqueue(20);
58 q.enqueue(30);
59 q.enqueue(40);
60 q.enqueue(50);
61 q.enqueue(60); // Should produce an error message
62
63 // Dequeue elements
64 q.dequeue();
65 q.dequeue();
66 q.dequeue();
67
68 // Enqueue element
69 q.enqueue(70);
70
71 return 0;
72}In the code above, we define a CircularQueue class with functions such as isEmpty, isFull, enqueue, and dequeue. The isEmpty function checks whether both front and rear are -1, indicating an empty queue. The isFull function checks if the next index of rear would be equal to front, indicating a full queue.
We enqueue elements using the enqueue function, and dequeue elements using the dequeue function. If the queue is full and we try to enqueue another element, an error message will be displayed. Similarly, if the queue is empty and we try to dequeue an element, an error message will be displayed as well.
The output of the code above will be:
1Enqueuing 10...
2Enqueuing 20...
3Enqueuing 30...
4Enqueuing 40...
5Enqueuing 50...
6Enqueuing 60...
7Queue is full. Unable to enqueue.
8Dequeuing...
9Dequeuing...
10Dequeuing...
11Enqueuing 70...By implementing a circular queue, we can efficiently utilize the circular link and ensure all the elements are utilized in the queue. It provides an optimization over a regular queue in terms of space utilization.
xxxxxxxxxx}using namespace std;const int SIZE = 5;class CircularQueue {private: int front; int rear; int arr[SIZE];public: CircularQueue() { front = -1; rear = -1; } bool isEmpty() { return front == -1 && rear == -1; } bool isFull() { return (rear + 1) % SIZE == front; } void enqueue(int item) { if (isFull()) { cout << "Queue is full. Unable to enqueue." << endl; } else if (isEmpty()) {