Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

circular
queue
c++

How to implement a circular queue in C++

Educative Answers Team

A circular queue is a linear data structure in which operations are performed based on the FIFO (First In First Out) principle; t​he last position is connected back to the first position to make a circle.

svg viewer

In a queue, we can insert elements until the queue becomes full; but once it is full, we cannot insert an element even if there is a space in front of it.

Once your entire circular queue is filled, ​if you delete some data, you’ll be able to put in more data as the rear variable will start repeating itself. In other words, once the value of your rear variable is n - 1 (the upper bound) and you delete some data from the front, more data will be able to be added into that vacated space.

svg viewer
svg viewer

Implementation

The simplest way to implement a circular queue is by using arrays. A circular queue has 2 key methods:

  • enqueue()
  • dequeue()

enqueue()

  • Check whether the queue is full. A queue is full when the front is next to the rear. For example, with a queue of size 6, if front is 0 and rear is 5, or if front is 2 and rear is 1, it means that the queue is full.

  • If it is full, then display "Queue is full"; if the queue is not full, then check if rear is the last index. If it is, set rear to 0; if it is not, increment rear and add the value at that index.

dequeue()

  • Check whether the queue is empty (i.e., if front/rear has a value of -1).

  • If it is empty, then it will display "Queue is empty". If the queue is not empty, then check if the queue has only one value (i.e., front == rear). If it does have only one value, set both rear and front to -1; if it does not, check if front is the last index of the queue and, if so, set front to 0; otherwise, increment front.

Code

#include<bits/stdc++.h> 
using namespace std; 
  
struct Queue 
{ 
    // Initialize front and rear 
    int rear, front; 
  
    // Circular Queue 
    int size; 
    int *arr; 
  
    Queue(int s) 
    { 
       front = rear = -1; 
       size = s; 
       arr = new int[s]; 
    } 
  
    void enQueue(int value); 
    int deQueue(); 
    void displayQueue(); 
}; 
  
  
/* Function to create Circular queue */
void Queue::enQueue(int value) 
{ 
    if ((front == 0 && rear == size-1) || 
            (rear == (front-1)%(size-1))) 
    { 
        printf("\nQueue is Full"); 
        return; 
    } 
  
    else if (front == -1) /* Insert First Element */
    { 
        front = rear = 0; 
        arr[rear] = value; 
    } 
  
    else if (rear == size-1 && front != 0) 
    { 
        rear = 0; 
        arr[rear] = value; 
    } 
  
    else
    { 
        rear++; 
        arr[rear] = value; 
    } 
} 
  
// Function to delete element from Circular Queue 
int Queue::deQueue() 
{ 
    if (front == -1) 
    { 
        printf("\nQueue is Empty"); 
        return INT_MIN; 
    } 
  
    int data = arr[front]; 
    arr[front] = -1; 
    if (front == rear) 
    { 
        front = -1; 
        rear = -1; 
    } 
    else if (front == size-1) 
        front = 0; 
    else
        front++; 
  
    return data; 
} 

void Queue::displayQueue() 
{ 
    if (front == -1) 
    { 
        printf("\nQueue is Empty"); 
        return; 
    } 
    printf("\nElements in Circular Queue are: "); 
    if (rear >= front) 
    { 
        for (int i = front; i <= rear; i++) 
            printf("%d ",arr[i]); 
    } 
    else
    { 
        for (int i = front; i < size; i++) 
            printf("%d ", arr[i]); 
  
        for (int i = 0; i <= rear; i++) 
            printf("%d ", arr[i]); 
    } 
} 
  
/* Driver of the program */
int main() 
{ 
    Queue q(5); 
  
    // Inserting elements in Circular Queue 
    q.enQueue(10); 
    q.enQueue(8); 
    q.enQueue(-6); 
    q.enQueue(16); 
  
    // Display elements present in Circular Queue 
    q.displayQueue(); 
  
    // Deleting elements from Circular Queue 
    printf("\nDeleted value = %d", q.deQueue()); 
    printf("\nDeleted value = %d", q.deQueue()); 
  
    q.displayQueue(); 
  
    q.enQueue(12); 
    q.enQueue(20); 
    q.enQueue(5); 
  
    q.displayQueue(); 
  
    q.enQueue(20); 
    return 0; 
} 

RELATED TAGS

circular
queue
c++
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring