{"id":116229,"date":"2020-03-02T11:06:05","date_gmt":"2020-03-02T11:06:05","guid":{"rendered":"https:\/\/www.softwaretestinghelp.com\/?page_id=116229"},"modified":"2025-04-01T08:29:15","modified_gmt":"2025-04-01T08:29:15","slug":"cpp-circular-queue-data-structure","status":"publish","type":"page","link":"https:\/\/www.softwaretestinghelp.com\/cpp-circular-queue-data-structure\/","title":{"rendered":"C++ Circular Queue Data Structure: Implementation & Applications"},"content":{"rendered":"\n

This Tutorial on C++ Circular Queue Data Structure Explains What is Circular Queue, What are the Basic Operations along with Implementations & Applications:<\/strong><\/p>\n\n\n\n

A circular queue is an extension of the basic queue that we have discussed earlier. It is also known as \u201cRing buffer\u201d.<\/p>\n\n\n\n

What is Circular Queue in C++?<\/strong><\/p>\n\n\n\n

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.<\/p>\n\n\n\n

=> Look For The Entire C++ Training Series Here<\/a><\/strong><\/p>\n\n\n\n

\"C++<\/a><\/figure>\n\n\n\n

<\/p>\n\n\n\n

Circular Queue In C++<\/h2>\n\n\n\n

The following diagram shows a circular queue.<\/strong><\/p>\n\n\n\n

\"circular<\/a><\/figure>\n\n\n\n

<\/p>\n\n\n\n

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\u2019t go wasted as it happens in a linear queue.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

In the next section, we will learn about the basic operations of the circular queue.<\/p>\n\n\n\n

Basic Operations<\/span><\/h3>\n\n\n\n

Some of the basic operations of the circular queue are as follows:<\/strong><\/p>\n\n\n\n

Front: <\/strong>Returns the front position in the circular queue.<\/span><\/p>\n\n\n\n

Rear: <\/strong>Returns the rear position in the circular queue.<\/span><\/p>\n\n\n\n

Enqueue: <\/strong>Enqueue (value) is used to insert an element in the circular queue. The element is always inserted at the rear end of the queue.<\/span><\/p>\n\n\n\n

We follow the following sequence of steps to insert a new element in the circular queue.<\/strong><\/span><\/p>\n\n\n\n

#1)<\/strong> Check if the circular queue is full: test ((rear == SIZE-1 && front == 0) || (rear == front-1)), where \u2018SIZE\u2019 is the size of the circular queue.<\/span><\/p>\n\n\n\n

#2)<\/strong> If the circular queue is full then it displays a message as \u201cQueue is full\u201d. If queue is not full then, check if (rear == SIZE \u2013 1 && front != 0). If it is true then set rear=0 and insert element.<\/span><\/p>\n\n\n\n

Dequeue: <\/strong><\/span>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.<\/p>\n\n\n\n

Steps:<\/strong><\/p>\n\n\n\n

#1)<\/strong> Check if the circular queue is Empty: check if (front==-1).<\/p>\n\n\n\n

#2)<\/strong> If it is empty then display the message \u201cQueue is empty\u201d. If queue is not empty then perform step 3.<\/p>\n\n\n\n

#3)<\/strong> 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.<\/p>\n\n\n\n

Illustration<\/span><\/h3>\n\n\n\n

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

Consider the following circular queue of 5 elements as shown below:<\/strong><\/p>\n\n\n\n

\"circular<\/a><\/figure>\n\n\n\n

<\/p>\n\n\n\n

Next, we insert item 1 in the queue.<\/p>\n\n\n\n

\"insert<\/a><\/figure>\n\n\n\n

<\/p>\n\n\n\n

Next, we insert an item with value 3.<\/p>\n\n\n\n

\"insert<\/a><\/figure>\n\n\n\n

<\/p>\n\n\n\n

When we insert the elements to make a queue full, the representation will be as shown below.<\/p>\n\n\n\n

\"insert<\/a><\/figure>\n\n\n\n

<\/p>\n\n\n\n

Now we delete the two elements i.e. item 1 and item 3 from the queue as shown below.<\/p>\n\n\n\n

\"delete<\/a><\/figure>\n\n\n\n

<\/p>\n\n\n\n

Next, we insert or enqueue element 11 in the circular queue as represented below.<\/p>\n\n\n\n

\"insert<\/a><\/figure>\n\n\n\n

<\/p>\n\n\n\n

Again let us insert element 13 in the circular queue. The queue will look as shown below.<\/p>\n\n\n\n

\"us<\/a><\/figure>\n\n\n\n

<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

Implementation<\/span><\/h3>\n\n\n\n

Let’s implement the circular queue using C++.<\/p>\n\n\n

\n#include<iostream> \nusing namespace std; \n   \nclass Queue { \n    public:\n    \/\/ Initialize front and rear \n    int rear, front; \n   \n    \/\/ Circular Queue \n    int size; \n    int *circular_queue; \n   \n    Queue(int sz) { \n       front = rear = -1; \n       size = sz; \n       circular_queue = new int[sz]; \n    } \n   void enQueue(int elem); \n    int deQueue(); \n    void displayQueue(); \n}; \n   \n\/* Function to create Circular queue *\/\nvoid Queue::enQueue(int elem) \n{ \n    if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1)))  { \n        cout<<"\\nQueue is Full"; \n        return; \n    } \n    else if (front == -1) {     \/* Insert First Element *\/\n         front = rear = 0; \n        circular_queue[rear] = elem; \n    } \n   else if (rear == size-1 && front != 0) { \n        rear = 0; \n        circular_queue[rear] = elem; \n    } \n    else {  \n        rear++; \n        circular_queue[rear] = elem; \n    } \n}\n\/\/ Function to delete element from Circular Queue \nint Queue::deQueue() \n{ \n    if (front == -1)  { \n        cout<<"\\nQueue is Empty"; \n        return -1; \n    } \n   \n    int data = circular_queue[front]; \n    circular_queue[front] = -1; \n    if (front == rear)  { \n        front = -1; \n        rear = -1; \n    } \n    else if (front == size-1) \n        front = 0; \n    else\n        front++; \n   \n    return data; \n} \n  \n\/\/display elements of Circular Queue \nvoid Queue::displayQueue() \n{ \n    if (front == -1) { \n        cout<<"\\nQueue is Empty"<<endl; \n        return; \n    } \n    cout<<"\\nCircular Queue elements: "; \n    if (rear >= front) { \n        for (int i = front; i <= rear; i++) \n            cout<<circular_queue[i]<<" "; \n    } \n    Else  { \n        for (int i = front; i < size; i++) \n            cout<<circular_queue[i]<<" "; \n   \n        for (int i = 0; i <= rear; i++) \n            cout<<circular_queue[i]<<" "; \n    } \n} \n   \n\/\/main program\nint main() \n{ \n    Queue pq(5); \n   \n    \/\/ Insert elements in Circular Queue \n    pq.enQueue(2); \n    pq.enQueue(4); \n    pq.enQueue(6); \n    pq.enQueue(8); \n   \n    \/\/ Display elements present in Circular Queue \n    pq.displayQueue(); \n   \n    \/\/ Delete elements from Circular Queue \n    cout<<"\\nElement Dequeued = "<<pq.deQueue(); \n    cout<<"\\nElement Dequeued = "<<pq.deQueue(); \n   \n    pq.displayQueue(); \n   \n    pq.enQueue(10); \n    pq.enQueue(12); \n    pq.enQueue(14); \n   \n    pq.displayQueue(); \n   \n    pq.enQueue(10); \n    return 0; \n}\n<\/pre><\/div>\n\n\n
Output:<\/strong><\/p>\n\n\n\n
\"Circular<\/a><\/figure>\n\n\n\n
<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
Linked List Implementation<\/span><\/h3>\n\n\n\n
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.<\/p>\n\n\n\n
The output shows the circular queue after enqueue operation, dequeue and also after the second enqueue operation.<\/strong><\/p>\n\n\n
\n#include<iostream> \nusing namespace std; \n   \nstruct Node \n{ \n    int data; \n    struct Node* link; \n}; \n   \nstruct PQueue \n{ \n    struct Node *front, *rear; \n}; \n   \n\/* this functions performs enqueue operation for circular queue *\/\nvoid enQueue(PQueue *pq,int elem) \n{ \n     \n   struct Node *temp = new Node; \n    temp->data = elem; \n    if (pq->front == NULL) \n        pq->front = temp; \n    else\n        pq->rear->link = temp; \n   \n    pq->rear = temp; \n    pq->rear->link = pq->front; \n}\n\/\/ This function performs dequeue operation for Circular Queue \nint deQueue(PQueue *pq) \n{ \n   if (pq->front == NULL) \n    { \n        cout<<"Queue is empty!!"; \n        return -1; \n    } \n   \n    int elem; \/\/ item to be dequeued\n    \/\/ item is the last node to be deleted \n    if (pq->front == pq->rear) \n    { \n        elem = pq->front->data; \n        free(pq->front); \n        pq->front = NULL; \n        pq->rear = NULL; \n    } \n    else  \/\/more than one nodes \n    { \n        struct Node *temp = pq->front; \n        elem = temp->data; \n        pq->front = pq->front->link; \n        pq->rear->link= pq->front; \n        free(temp); \n    } \n   \n    return elem ; \n} \n  \n\/\/display elements of Circular Queue \nvoid displayQueue(struct PQueue *pq) \n{ \n    struct Node *temp = pq->front; \n    while (temp->link != pq->front) \n    { \n        cout<<temp->data<<" "; \n        temp = temp->link; \n    } \n    cout<<temp->data;\n} \n   \n\/\/main program\nint main() \n{ \n    \/\/ Create a circular queue and initialize front and rear \n    PQueue *pq = new PQueue; \n    pq->front = pq->rear = NULL; \n   \n    \/\/ Insert\/enqueue elements in Circular Queue \n    enQueue(pq, 1); \n    enQueue(pq, 3); \n    enQueue(pq, 5); \n   \n    cout<<"\\nCircular Queue elements after enqueue operation: "; \n    \/\/ Display elements in Circular Queue \n    displayQueue(pq); \n   \n    \/\/ Delete\/dequeue elements from Circular Queue \n    cout<<"\\nDequeued Item: "<<deQueue(pq); \n    cout<<"\\nDequeued Item: "<<deQueue(pq); \n   \n    cout<<"\\nCircular Queue elements after two dequeue operation: "; \n    \/\/ Remaining elements in Circular Queue after dequeue\n    displayQueue(pq); \n   \n    enQueue(pq, 7); \n    enQueue(pq, 9); \n    cout<<"\\nCircular Queue elements after two enqueue operations: "; \n    displayQueue(pq); \n   \n    return 0; \n}\n<\/pre><\/div>\n\n\n
Output:<\/strong><\/p>\n\n\n\n
\"Linked<\/a><\/figure>\n\n\n\n
<\/p>\n\n\n\n
Next implementation is a Java program to demonstrate circular queue using the linked list.<\/p>\n\n\n
\nimport java.util.* ; \n   \nclass Main \n{ \n\/\/ Node structure \nstatic class Node  {  \n    int data;  \n     Node  link;  \n} \n     \nstatic class CQueue {  \n     Node  front,  rear;  \n} \n     \n\/\/ Enqueue operation for circular queue  \nstatic void enQueue(CQueue  cq, int value)  {  \n     Node  temp = new Node();  \n    temp .data = value;  \n    if (cq .front ==  null)  \n        cq .front = temp;  \n    else\n        cq .rear .link = temp;  \n     \n    cq .rear = temp;  \n    cq .rear .link = cq .front;  \n}  \n     \n\/\/ Dequeue operation for Circular Queue  \nstatic  int deQueue(CQueue  cq)  {  \n    if (cq .front ==  null)  {  \n        System.out.printf (\"Queue is empty!!\");  \n        return Integer.MIN_VALUE;  \n    }  \n     int value; \/\/ Value to be dequeued  \n    \/\/ the last node to be deleted\n    if (cq.front == cq.rear)   {  \n        value = cq.front.data;  \n        cq.front =  null;  \n        cq.rear =  null;  \n    }  \n    else   {         \/\/ There are more than one nodes    \n         Node  temp = cq.front;  \n        value = temp.data;  \n        cq.front = cq.front.link;  \n        cq.rear.link= cq.front;  \n    }  \n    return value ;  \n}  \n \/\/ display the elements of Circular Queue  \nstatic void displayQueue( CQueue  cq)  \n{  \n     Node  temp = cq.front;  \n    while (temp.link != cq.front)  \n    {  \n        System.out.printf(\"%d \", temp.data);  \n        temp = temp.link;  \n    }  \n    System.out.printf(\"%d\", temp.data);  \n}  \n     \n\/*  main program *\/\npublic static void main(String args[]) \n{  \n    \/\/ Create a queue and initialize front and rear  \n    CQueue  cq = new CQueue();  \n    cq.front = cq.rear =  null;  \n     \n    \/\/ Insert\/enqueue elements in Circular Queue  \n    enQueue(cq, 2);  \n    enQueue(cq, 4);  \n    enQueue(cq, 6);  \n     \n    System.out.print(\"\\nCircular Queue elements after Enqueue Operation:\");    \n    \/\/ Display elements in Circular Queue  \n    displayQueue(cq);  \n     \n    \/\/ Delete\/dequeue elements from Circular Queue  \n    System.out.printf(\"\\nDequeued Item = %d\", deQueue(cq));  \n    System.out.printf(\"\\nDequeued Item = %d\", deQueue(cq));  \n     \n    System.out.print(\"\\nCircular Queue elements after Dequeue Operation:\");\n    displayQueue(cq);  \n     \n    enQueue(cq, 8);  \n    enQueue(cq, 10);  \n    System.out.print(\"\\nCircular Queue elements after second Enqueue Operation:\");\n    displayQueue(cq);  \n     \n}  \n}\n<\/pre><\/div>\n\n\n
Output:<\/strong><\/p>\n\n\n\n
\"Output\"<\/a><\/figure>\n\n\n\n
<\/p>\n\n\n\n
The output of the above program is similar to the previous program.<\/p>\n\n\n\n
Applications<\/span><\/h3>\n\n\n\n
Let’s discuss some of the applications of the circular queue.<\/strong><\/p>\n\n\n\n