C++ Circular Queue Data Structure: Implementation & Applications

This Tutorial on C++ Circular Queue Data Structure Explains What is Circular Queue, What are the Basic Operations along with Implementation & Applications:

A circular queue is an extension of the basic queue that we have discussed earlier. It is also known as “Ring buffer”.

What is Circular Queue in C++?

A circular queue is a linear data structure that is used to store data items. It performs operations by following the FIFO (First In, First Out) approach and the last position in the queue is connected back to the first position to form a circle.

=> Look For The Entire C++ Training Series Here

C++ Circular Queue

Circular Queue In C++

The following diagram shows a circular queue.

circular queue

The above image shows a circular data structure of size 10. The first six elements are already in the queue and we see that the first position and last position are joined. Due to this arrangement, space doesn’t go wasted as it happens in a linear queue.

In a linear queue after the queue is full, we delete the elements from another end, and the status of the queue is still shown as full and we cannot insert more elements.

In the circular queue, when the queue is full, and when we remove elements from the front since last and first positions are connected, we can insert the elements at the rear which was vacated by deleting the element.

In the next section, we will learn about the basic operations of the circular queue.

Basic Operations

Some of the basic operations of the circular queue are as follows:

Front: Returns the front position in the circular queue.

Rear: Returns the rear position in the circular queue.

Enqueue: Enqueue (value) is used to insert an element in the circular queue. The element is always inserted at the rear end of the queue.

We follow the following sequence of steps to insert a new element in the circular queue.

#1) Check if the circular queue is full: test ((rear == SIZE-1 && front == 0) || (rear == front-1)), where ‘SIZE’ is the size of the circular queue.

#2) If the circular queue is full then it displays a message as “Queue is full”. If queue is not full then, check if (rear == SIZE – 1 && front != 0). If it is true then set rear=0 and insert element.

Dequeue: Dequeue function is used to delete an element from the queue. In the circular queue, the element is always deleted from the front end. Given below is the sequence for dequeue operation in a circular queue.

Steps:

#1) Check if the circular queue is Empty: check if (front==-1).

#2) If it is empty then display the message “Queue is empty”. If queue is not empty then perform step 3.

#3) Check if (front==rear). If it is true then set front=rear= -1 else check if (front==size-1), if it is true then set front=0 and return the element.

Illustration

In this section, we will go through a detailed illustration of adding/removing elements in the circular queue.

Consider the following circular queue of 5 elements as shown below:

circular queue of 5 elements

Next, we insert item 1 in the queue.

insert item 1 in the queue

Next, we insert an item with value 3.

insert an item with value 3

When we insert the elements to make a queue full, the representation will be as shown below.

insert the elements to make queue full

Now we delete the two elements i.e. item 1 and item 3 from the queue as shown below.

delete the two elements item 1 and item 3 from the queue

Next, we insert or enqueue element 11 in the circular queue as represented below.

insert or enqueue element 11

Again let us insert element 13 in the circular queue. The queue will look as shown below.

us insert element 13

We see that in the circular queue we move or insert elements in a circle. Hence we can consume the entire space of the queue till it becomes full.

Implementation

Let's implement the circular queue using C++.

#include<iostream> 
using namespace std; 
  
class Queue { 
    public:
    // Initialize front and rear 
    int rear, front; 
  
    // Circular Queue 
    int size; 
    int *circular_queue; 
  
    Queue(int sz) { 
       front = rear = -1; 
       size = sz; 
       circular_queue = new int[sz]; 
    } 
   void enQueue(int elem); 
    int deQueue(); 
    void displayQueue(); 
}; 
  
/* Function to create Circular queue */
void Queue::enQueue(int elem) 
{ 
    if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1)))  { 
        cout<<"\nQueue is Full"; 
        return; 
    } 
    else if (front == -1) {     /* Insert First Element */
         front = rear = 0; 
        circular_queue[rear] = elem; 
    } 
   else if (rear == size-1 && front != 0) { 
        rear = 0; 
        circular_queue[rear] = elem; 
    } 
    else {  
        rear++; 
        circular_queue[rear] = elem; 
    } 
}
// Function to delete element from Circular Queue 
int Queue::deQueue() 
{ 
    if (front == -1)  { 
        cout<<"\nQueue is Empty"; 
        return -1; 
    } 
  
    int data = circular_queue[front]; 
    circular_queue[front] = -1; 
    if (front == rear)  { 
        front = -1; 
        rear = -1; 
    } 
    else if (front == size-1) 
        front = 0; 
    else
        front++; 
  
    return data; 
} 
 
//display elements of Circular Queue 
void Queue::displayQueue() 
{ 
    if (front == -1) { 
        cout<<"\nQueue is Empty"<<endl; 
        return; 
    } 
    cout<<"\nCircular Queue elements: "; 
    if (rear >= front) { 
        for (int i = front; i <= rear; i++) 
            cout<<circular_queue[i]<<" "; 
    } 
    Else  { 
        for (int i = front; i < size; i++) 
            cout<<circular_queue[i]<<" "; 
  
        for (int i = 0; i <= rear; i++) 
            cout<<circular_queue[i]<<" "; 
    } 
} 
  
//main program
int main() 
{ 
    Queue pq(5); 
  
    // Insert elements in Circular Queue 
    pq.enQueue(2); 
    pq.enQueue(4); 
    pq.enQueue(6); 
    pq.enQueue(8); 
  
    // Display elements present in Circular Queue 
    pq.displayQueue(); 
  
    // Delete elements from Circular Queue 
    cout<<"\nElement Dequeued = "<<pq.deQueue(); 
    cout<<"\nElement Dequeued = "<<pq.deQueue(); 
  
    pq.displayQueue(); 
  
    pq.enQueue(10); 
    pq.enQueue(12); 
    pq.enQueue(14); 
  
    pq.displayQueue(); 
  
    pq.enQueue(10); 
    return 0; 
}

Output:

Circular Queue Output

Above shown is the output of circular queue operations. First, we add the elements and then dequeue or remove two elements. Next, we insert or enqueue three more elements in the circular queue. We see that unlike linear queue, the elements are added at the end of the queue.

Linked List Implementation

Let's discuss the linked list implementation of a circular queue now. Given below is the linked list implementation of the circular queue in C++. Note that we make use of struct to represent each node. The operations are the same as discussed before except that in this case, we have to perform them with respect to the linked list nodes.

The output shows the circular queue after enqueue operation, dequeue and also after the second enqueue operation.

#include<iostream> 
using namespace std; 
  
struct Node 
{ 
    int data; 
    struct Node* link; 
}; 
  
struct PQueue 
{ 
    struct Node *front, *rear; 
}; 
  
/* this functions performs enqueue operation for circular queue */
void enQueue(PQueue *pq,int elem) 
{ 
    
   struct Node *temp = new Node; 
    temp->data = elem; 
    if (pq->front == NULL) 
        pq->front = temp; 
    else
        pq->rear->link = temp; 
  
    pq->rear = temp; 
    pq->rear->link = pq->front; 
}
// This function performs dequeue operation for Circular Queue 
int deQueue(PQueue *pq) 
{ 
   if (pq->front == NULL) 
    { 
        cout<<"Queue is empty!!"; 
        return -1; 
    } 
  
    int elem; // item to be dequeued
    // item is the last node to be deleted 
    if (pq->front == pq->rear) 
    { 
        elem = pq->front->data; 
        free(pq->front); 
        pq->front = NULL; 
        pq->rear = NULL; 
    } 
    else  //more than one nodes 
    { 
        struct Node *temp = pq->front; 
        elem = temp->data; 
        pq->front = pq->front->link; 
        pq->rear->link= pq->front; 
        free(temp); 
    } 
  
    return elem ; 
} 
 
//display elements of Circular Queue 
void displayQueue(struct PQueue *pq) 
{ 
    struct Node *temp = pq->front; 
    while (temp->link != pq->front) 
    { 
        cout<<temp->data<<" "; 
        temp = temp->link; 
    } 
    cout<<temp->data;
} 
  
//main program
int main() 
{ 
    // Create a circular queue and initialize front and rear 
    PQueue *pq = new PQueue; 
    pq->front = pq->rear = NULL; 
  
    // Insert/enqueue elements in Circular Queue 
    enQueue(pq, 1); 
    enQueue(pq, 3); 
    enQueue(pq, 5); 
  
    cout<<"\nCircular Queue elements after enqueue operation: "; 
    // Display elements in Circular Queue 
    displayQueue(pq); 
  
    // Delete/dequeue elements from Circular Queue 
    cout<<"\nDequeued Item: "<<deQueue(pq); 
    cout<<"\nDequeued Item: "<<deQueue(pq); 
  
    cout<<"\nCircular Queue elements after two dequeue operation: "; 
    // Remaining elements in Circular Queue after dequeue
    displayQueue(pq); 
  
    enQueue(pq, 7); 
    enQueue(pq, 9); 
    cout<<"\nCircular Queue elements after two enqueue operations: "; 
    displayQueue(pq); 
  
    return 0; 
}

Output:

Linked list implementation - output

Next implementation is a Java program to demonstrate circular queue using the linked list.

import java.util.* ; 
  
class Main 
{ 
// Node structure 
static class Node  {  
    int data;  
     Node  link;  
} 
    
static class CQueue {  
     Node  front,  rear;  
} 
    
// Enqueue operation for circular queue  
static void enQueue(CQueue  cq, int value)  {  
     Node  temp = new Node();  
    temp .data = value;  
    if (cq .front ==  null)  
        cq .front = temp;  
    else
        cq .rear .link = temp;  
    
    cq .rear = temp;  
    cq .rear .link = cq .front;  
}  
    
// Dequeue operation for Circular Queue  
static  int deQueue(CQueue  cq)  {  
    if (cq .front ==  null)  {  
        System.out.printf ("Queue is empty!!");  
        return Integer.MIN_VALUE;  
    }  
     int value; // Value to be dequeued  
    // the last node to be deleted
    if (cq.front == cq.rear)   {  
        value = cq.front.data;  
        cq.front =  null;  
        cq.rear =  null;  
    }  
    else   {         // There are more than one nodes    
         Node  temp = cq.front;  
        value = temp.data;  
        cq.front = cq.front.link;  
        cq.rear.link= cq.front;  
    }  
    return value ;  
}  
 // display the elements of Circular Queue  
static void displayQueue( CQueue  cq)  
{  
     Node  temp = cq.front;  
    while (temp.link != cq.front)  
    {  
        System.out.printf("%d ", temp.data);  
        temp = temp.link;  
    }  
    System.out.printf("%d", temp.data);  
}  
    
/*  main program */
public static void main(String args[]) 
{  
    // Create a queue and initialize front and rear  
    CQueue  cq = new CQueue();  
    cq.front = cq.rear =  null;  
    
    // Insert/enqueue elements in Circular Queue  
    enQueue(cq, 2);  
    enQueue(cq, 4);  
    enQueue(cq, 6);  
    
    System.out.print("\nCircular Queue elements after Enqueue Operation:");    
    // Display elements in Circular Queue  
    displayQueue(cq);  
    
    // Delete/dequeue elements from Circular Queue  
    System.out.printf("\nDequeued Item = %d", deQueue(cq));  
    System.out.printf("\nDequeued Item = %d", deQueue(cq));  
    
    System.out.print("\nCircular Queue elements after Dequeue Operation:");
    displayQueue(cq);  
    
    enQueue(cq, 8);  
    enQueue(cq, 10);  
    System.out.print("\nCircular Queue elements after second Enqueue Operation:");
    displayQueue(cq);  
    
}  
}

Output:

Output

The output of the above program is similar to the previous program.

Applications

Let's discuss some of the applications of the circular queue.

  • CPU Scheduling: Operating system process that requires some event to occur or for some other processes to complete for execution is often maintained in a circular queue so that they execute one after the other when all the conditions are met or when all events occur.
  • Memory Management: Use of ordinary queues wastes memory space as already mentioned in our above discussion. Using a circular queue for memory management is beneficial for optimum memory usage.
  • Computer Controlled Traffic Signal System: Computerized traffic signals are often added to a circular queue so that they repeat themselves after the specified time interval has elapsed.

Conclusion

Circular queues fix the major disadvantage of a normal queue wherein we cannot insert elements when the rear pointer is at the end of the queue even when we delete the elements and space is emptied. In a circular queue, elements are arranged in a circular fashion, so that space is not wasted at all.

We have also seen the major operations of the circular queue. Circular queues are mostly useful for scheduling purposes and applications like traffic signal systems where the signals glow in turns.

In our next tutorial, we will learn about the double-ended queues that are simply called “deque”.

=> Visit Here To Learn C++ From Scratch