How to implement a circular queue in C++

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

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; 
}