Array implementation can be the preferred choice for Circular Queue when the data is limited in size. The Front and Rear position works similarly to the Simple Queue except it can circle back to the first position when it reaches the end.
See Circular Queue Implementation using Linked List to deal with dynamic data.
1. Representation
An array with the size of 8 is represented here in circular form for quick understanding.
// Queue maximum capacity
#define CAPACITY 8
// Queue
int queue[CAPACITY];
// Front position
int front = -1;
// Rear position
int rear = -1;
2. Circular Queue Implementation using Array
An example program to implement the Circular Queue using Array. This object-oriented implementation encapsulates the Queue data structure using a c++ class.
/**
* C++ example to demonstrate Circular Queue implementation using Array
*/
#include <iostream>
using namespace std;
// Queue maximum capacity
#define CAPACITY 8
/**
* Circular Queue implementation using Array
*/
class CircularQueue
{
private:
// Queue
int queue[CAPACITY];
// Front position
int front;
// Rear position
int rear;
public:
// Constructor
CircularQueue() : front(-1), rear(-1) {}
// Enqueue new element to the Queue
void enqueue(int element);
// Dequeue the element from Queue
int dequeue();
// Returns the Front element without deleting it
int peek();
// Print the Queue
void display(string msg);
// Check if the Queue is empty
bool isEmpty();
// Check if the Queue is full
bool isFull();
};
// Enqueue new element to the Queue
void CircularQueue::enqueue(int element) {
// Step 1. Return if the Queue is full, proceed otherwise
if (isFull()) {
return;
}
// Step 2. Move the Rear position
if (front == -1) {
// Step 2.A If Queue is empty, set Front and Rear to point the first position.
front = rear = 0;
} else if (rear == (CAPACITY-1)) {
// Step 2.B If Rear reached the last position, move Rear to first position
rear = 0;
} else {
// Step 2.C Otherwise increment the Rear to next position.
rear++;
}
// Step 3. Insert the new element at Rear
queue[rear] = element;
}
// Dequeue the element from Queue
int CircularQueue::dequeue() {
// Step 1. Return if the Queue is empty, proceed otherwise
if (isEmpty()) {
return -1;
}
// Step 2. Retrieve the element at Front
int element = queue[front];
// Step 3. Move the Front position
if (front == rear) {
// Step 3.A If this is the last element, reset Front and Rear to -1.
front = -1;
rear = -1;
} else if (front == (CAPACITY-1)) {
// Step 3.B If Front reached the last position, move Front to first position
front = 0;
} else {
// Step 3.C Otherwise increment the Front to next position
front++;
}
return element;
}
// Returns the Front element without deleting it
int CircularQueue::peek() {
if (isEmpty()) {
return -1;
}
return queue[front];
}
// Check if the Queue is empty
bool CircularQueue::isEmpty() {
if (front == -1) {
cout << "Queue is Empty" << endl;
return true;
}
return false;
}
// Check if the Queue is full
bool CircularQueue::isFull() {
if ((front == 0 && rear == (CAPACITY-1)) ||
(front == (rear+1))) {
cout << "Queue is Full" << endl;
return true;
}
return false;
}
// Print the Queue
void CircularQueue::display(string msg) {
cout << msg << endl;
if (isEmpty()) {
return;
}
cout << "IDX ELEMENT" << endl;
cout << "---+-------" << endl;
for (int i=0; i < CAPACITY; i++) {
if (front <= rear) {
if (! (i >= front && i <= rear) ) {
cout << "[" << i << "] " << endl;
continue;
}
} else if (front > rear) {
if (! (i >= front || i <= rear) ) {
cout << "[" << i << "] " << endl;
continue;
}
}
if (i == front && front == rear) {
cout << "[" << i << "] " << queue[i] << " <-- front, rear" << endl;
} else if (i == front) {
cout << "[" << i << "] " << queue[i] << " <-- front" << endl;
} else if (i == rear) {
cout << "[" << i << "] " << queue[i] << " <-- rear" << endl;
} else {
cout << "[" << i << "] " << queue[i] << endl;
}
}
}
// The main function to begin the execution
int main()
{
// Create a Queue
CircularQueue queue;
// Enqueue elements (10, 20, 30, 40, and 50)
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
queue.enqueue(50);
queue.display("Queue after inserting 10 20 30 40 and 50");
// Get the peek element
int element = queue.peek();
cout << "Peek element returned " << element << endl;
// Dequeue the elements from Queue
element = queue.dequeue();
cout << "Dequeue element returned " << element << endl;
element = queue.dequeue();
cout << "Dequeue element returned " << element << endl;
queue.display("Queue after removing 10 and 20");
// Enqueue elements (60, 70, 80, and 90) to check circular behavior
queue.enqueue(60);
queue.enqueue(70);
queue.enqueue(80);
queue.enqueue(90);
queue.display("Queue after inserting 60, 70, 80, and 90");
}
Output
Queue after inserting 10 20 30 40 and 50
IDX ELEMENT
---+-------
[0] 10 <-- front
[1] 20
[2] 30
[3] 40
[4] 50 <-- rear
[5]
[6]
[7]
Peek element returned 10
Dequeue element returned 10
Dequeue element returned 20
Queue after removing 10 and 20
IDX ELEMENT
---+-------
[0]
[1]
[2] 30 <-- front
[3] 40
[4] 50 <-- rear
[5]
[6]
[7]
Queue after inserting 60, 70, 80, and 90
IDX ELEMENT
---+-------
[0] 90 <-- rear
[1]
[2] 30 <-- front
[3] 40
[4] 50
[5] 60
[6] 70
[7] 80
3. Operations of Circular Queue
Here, we discuss the operations performed on the Circular Queue with an Array.
3.1. Enqueue on Circular Queue
Enqueue operation inserts a new element on the rear side of the Circular Queue. If the Rear reaches the last index, then it can circle back to the first index when there is an empty space available.
Algorithm
- Return if the Queue is full, proceed otherwise
- Move the Rear position with any one of the following steps
- If Queue is empty, set Front and Rear to point to the first position.
- If Rear reached the last position, move Rear to the first position
- Otherwise, increment the Rear to the next position.
- Insert the new element at the Rear
Examples
The queue is empty initially and the Front and Rear are set to -1. The following steps illustrate enqueuing the first element to an empty Queue.
The Front and Rear point to some valid position when the queue is not empty. The new element is inserted if there is a space left at the Rear side and the Rear will be changed to point to the new element.
Assume that the Rear moved to the last position of the Array after inserting the elements 30, 40, 50, 60, 70, and 80. The Front moved to position 2 after dequeuing elements 10 and 20. An enqueue operation at this stage should insert the new element at index 0 to mimic the circular behavior.
3.2. Dequeue on Circular Queue
The dequeue operation removes an element from the Front side of the Queue. The Front position can also circle back to the first index when it reaches the end of the array.
Algorithm
- Return if the Queue is empty, proceed otherwise
- Retrieve the element at the Front
- Move the Front position
- If this is the last element, reset the Front and Rear to -1.
- If Front reached the last position, move Front to the first position
- Otherwise, increment the Front to the next position
Examples
The queue must be non-empty to perform the Dequeue operation. The element present at the Front will be retrieved and the Front will point to the next position.
The procedure for Dequeuing the last element differs in Step 3. The Front position can not be moved because the next element is unavailable. In such a case, the Front and Rear will be reset as -1 to indicate the queue is empty.
Assume that the Front moved to the last position of the Array and the Rear is at index 1 after circling back. A dequeue operation at this stage should move the Front to index 0 to mimic the circular behavior.
