Circular Queue in Data Structure

In linear queues, insertion occurs at the rear end, while deletion happens at the front end.

Ex:

F=0, R=4

If we want to insert a new element in the queue, it is impossible because the queue is full.

Delete the elements 10 and 20

F=2 R=4

Even though some space is available, we cannot insert a new element because it violates the condition R=MAX-1. This is the major drawback of the linear queue.

To overcome this problem we use the concept of circular queue.

The linear queue in a circle is called a circular queue.

The rules and regulations we apply for queues will also apply to circular queues. In a circular queue, the first index comes right after the last.

How to Implement a Circular Queue Using an Array:

1. Initialize the Circular Queue
   • Step 1: Create an array of fixed-size maxSize to hold the queue elements.
   • Step 2: Set two pointers, Front and Rear, to indicate the start and end of the queue. Initialize both Front and Rear to -1, indicating an empty queue.
2. Check for Queue Overflow
   • Step 3: Ensure the queue is not full before inserting an element. This occurs when (Rear + 1) % maxSize == Front. If true, print “Queue Overflow” and stop the insertion process.
3. Insert an Element
   • Step 4: Update the Rear pointer. If Rear == maxSize – 1, set Rear to 0 (circular wrap-around). Otherwise, increment Rear by 1.
   • Step 5: Insert the new item at Q[Rear].
   • Step 6: If Front is -1 (the queue was empty), set Front to 0 to mark the queue as not empty.
4. Check for Queue Underflow
   • Step 7: Check if the queue is empty before deleting an element. This occurs when Front == -1. If true, print “Queue Underflow” and stop the deletion process.
5. Delete an Element
   • Step 8: Store the item at Q[Front] to be returned.
   • Step 9: Update the Front pointer. If Front == Rear, reset both Front and Rear to -1 (the queue is empty).
   • Step 10: If Front == maxSize – 1, set Front to 0 (circular wrap-around). Otherwise, increment Front by 1.
6. Return the Deleted Element
   • Step 11: Return the item stored from the front of the queue.

Insertion into a Circular Queue Algorithm: 

CQueueInsertion(Q, maxSize, Front, Rear, item) 

Step 1:

• If Rear == maxSize – 1, then
  • Set Rear = 0
• Else,
  • Increment Rear by 1 (Rear = Rear + 1)

Step 2:

• If Front == Rear, then
  • Print “Queue Overflow”
  • Return

Step 3:

• Set Q[Rear] = item

Step 4:

• If Front == 0, then
  • Set Front = 1

Step 5:

• Return

Deletion from Circular Queue Algorithm: 

CQueueDeletion(Q,maxSize,Front,Rear,item) 

Step 1:

• Check for Queue Underflow:
  • If Front == 0, then
    • Print “Queue Underflow”
    • Return
      (If the front index is 0, the queue is empty and there’s nothing to delete.)

Step 2:

• Store the Front Item:
  • Set K = Q[Front]
    (Retrieve the item at the front of the queue.)

Step 3:

• Check if the Queue is Now Empty:
  • If Front == Rear, then
    • Begin
      • Set Front = -1
      • Set Rear = -1
    • End
      (If front equals rear, this is the last item in the queue, so we reset both front and rear to -1, indicating the queue is now empty.)
• Else:
  • Update Front for Circular Movement:
    • If Front == maxSize – 1, then
      • Set Front = 0
        (If the front is at the last position in the array, move it to the beginning, maintaining the circular nature of the queue.)
    • Else
      • Set Front = Front + 1
        (If not, advance the front pointer to the next position.)

Step 4:

• Return the Deleted Item:
  • Return K
    (The queue removes and returns the front element.)

Program Implementation of a Circular Queue:

class CircularQueue:
    def __init__(self, size):
        self.size = size  # Maximum size of the queue
        self.queue = [None] * size  # Initialize the queue with None values
        self.front = self.rear = -1  # Initialize front and rear pointers to -1
    def is_empty(self):
        # Check if the queue is empty
        return self.front == -1
    def is_full(self):
        # Check if the queue is full
        return (self.rear + 1) % self.size == self.front
    def enqueue(self, data):
        # Function to insert an element to the queue
        if self.is_full():
            print("Queue is full!")
            return
        if self.front == -1:
            # If the queue is empty, set front to 0
            self.front = 0
        self.rear = (self.rear + 1) % self.size  # Move rear pointer circularly
        self.queue[self.rear] = data  # Insert data at the rear
    def dequeue(self):
        # Function to delete an element from the queue
        if self.is_empty():
            print("Queue is empty!")
            return
        data = self.queue[self.front]
        if self.front == self.rear:
            # If only one element is present, reset front and rear
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.size  # Move front pointer circularly
        return data  # Return the deleted element
    def print_queue(self):
        # Function to print the elements of the queue
        if self.is_empty():
            print("Queue is empty!")
            return
        if self.rear >= self.front:
            # Print elements from front to rear if rear is ahead
            for i in range(self.front, self.rear + 1):
                print(self.queue[i], end=" ")
            print()
        else:
            # Print elements from front to the end of the array
            for i in range(self.front, self.size):
                print(self.queue[i], end=" ")
            # Print elements from the beginning of the array to rear
            for i in range(0, self.rear + 1):
                print(self.queue[i], end=" ")
            print()
# Example usage
queue = CircularQueue(5)
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)
print("Queue:")
queue.print_queue()  # Output: 1 2 3 4 5
queue.dequeue()
queue.dequeue()
print("Queue after two dequeues:")
queue.print_queue()  # Output: 3 4 5
queue.enqueue(6)
queue.enqueue(7)
print("Queue after two enqueues:")
queue.print_queue()  # Output: 3 4 5 6 7

#include <iostream>
using namespace std;
class CircularQueue {
private:
    int size;         // Maximum size of the queue
    int *queue;      // Array to store queue elements
    int front;        // Index of the front element
    int rear;         // Index of the rear element
public:
    // Constructor
    CircularQueue(int queueSize) : size(queueSize), front(-1), rear(-1) {
        queue = new int[size]; // Allocate memory for the queue array
    }
    // Destructor to free allocated memory
    ~CircularQueue() {
        delete[] queue;
    }
    // Check if the queue is empty
    bool isEmpty() {
        return (front == -1);
    }
    // Check if the queue is full
    bool isFull() {
        return ((rear + 1) % size == front);
    }
    // Enqueue operation: Insert an element at the rear
    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue Overflow\n";
        } else {
            if (isEmpty()) {
                front = rear = 0; // Set both front and rear to 0 if the queue is empty
            } else {
                rear = (rear + 1) % size; // Move rear pointer circularly
            }
            queue[rear] = value; // Insert the value at the rear
            cout << "Inserted " << value << " into the queue.\n";
        }
    }
    // Dequeue operation: Remove an element from the front
    int dequeue() {
        int value;
        if (isEmpty()) {
            cout << "Queue Underflow\n";
            return -1; // Return -1 to indicate underflow
        } else {
            value = queue[front];
            if (front == rear) { // If only one element is present
                front = rear = -1; // Reset front and rear
            } else {
                front = (front + 1) % size; // Move front pointer circularly
            }
            return value;
        }
    }
    // Function to display the elements of the queue
    void display() {
        if (isEmpty()) {
            cout << "Queue is Empty\n";
            return;
        }
        cout << "Elements in Circular Queue are: ";
        int i = front;
        do {
            cout << queue[i] << " ";
            i = (i + 1) % size;
        } while (i != (rear + 1) % size);
        cout << endl;
    }
};
int main() {
    CircularQueue q(5); // Create a circular queue of size 5
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    q.enqueue(5); // Queue is now full: 1 2 3 4 5
    cout << "Queue: ";
    q.display(); // Output: 1 2 3 4 5
    q.dequeue();
    q.dequeue(); // Two elements dequeued
    cout << "Queue after two dequeues: ";
    q.display(); // Output: 3 4 5
    q.enqueue(6);
    q.enqueue(7); // Two elements enqueued
    cout << "Queue after two enqueues: ";
    q.display(); // Output: 3 4 5 6 7
    return 0;
}

class CircularQueue {
    private int size;      // Maximum size of the queue
    private int[] queue;   // Array to store queue elements
    private int front;     // Index of the front element
    private int rear;      // Index of the rear element
    // Constructor
    public CircularQueue(int queueSize) {
        this.size = queueSize;
        this.queue = new int[size];
        this.front = -1;
        this.rear = -1;
    }
    // Check if the queue is empty
    public boolean isEmpty() {
        return (front == -1);
    }
    // Check if the queue is full
    public boolean isFull() {
        return ((rear + 1) % size == front);
    }
    // Enqueue operation: Insert an element at the rear
    public void enqueue(int value) {
        if (isFull()) {
            System.out.println("Queue Overflow");
        } else {
            if (isEmpty()) {
                front = rear = 0; // If the queue is empty, set both front and rear to 0
            } else {
                rear = (rear + 1) % size; // Move rear pointer circularly
            }
            queue[rear] = value; // Insert the value at the rear
            System.out.println("Inserted " + value + " into the queue.");
        }
    }
    // Dequeue operation: Remove an element from the front
    public int dequeue() {
        int value;
        if (isEmpty()) {
            System.out.println("Queue Underflow");
            return -1; // Return -1 to indicate underflow
        } else {
            value = queue[front];
            if (front == rear) { // If only one element is present
                front = rear = -1; // Reset front and rear
            } else {
                front = (front + 1) % size; // Move front pointer circularly
            }
            return value;
        }
    }
    // Function to display the elements of the queue
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is Empty");
            return;
        }
        System.out.print("Elements in Circular Queue are: ");
        int i = front;
        do {
            System.out.print(queue[i] + " ");
            i = (i + 1) % size;
        } while (i != (rear + 1) % size);
        System.out.println();
    }
    public static void main(String[] args) {
        CircularQueue q = new CircularQueue(5); // Create a circular queue of size 5
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);
        q.enqueue(4);
        q.enqueue(5); // Queue is now full: 1 2 3 4 5
        System.out.println("Queue:");
        q.display(); // Output: 1 2 3 4 5
        q.dequeue();
        q.dequeue(); // Two elements dequeued
        System.out.println("Queue after two dequeues:");
        q.display(); // Output: 3 4 5
        q.enqueue(6);
        q.enqueue(7); // Two elements enqueued
        System.out.println("Queue after two enqueues:");
        q.display(); // Output: 3 4 5 6 7
    }
}

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5 // Define the maximum size of the queue
// Structure to represent a circular queue
typedef struct {
    int items[SIZE]; // Array to store queue elements
    int front;       // Index of the front element
    int rear;        // Index of the rear element
} CircularQueue;
// Function to initialize the circular queue
void initializeQueue(CircularQueue *q) {
    q->front = -1;
    q->rear = -1;
}
// Function to check if the queue is empty
int isEmpty(CircularQueue *q) {
    return (q->front == -1);
}
// Function to check if the queue is full
int isFull(CircularQueue *q) {
    return ((q->rear + 1) % SIZE == q->front);
}
// Function to enqueue (insert) an element into the queue
void enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        printf("Queue Overflow\n");
    } else {
        if (isEmpty(q)) {
            q->front = 0; // If the queue is empty, set front to 0
        }
        q->rear = (q->rear + 1) % SIZE; // Move rear pointer circularly
        q->items[q->rear] = value;       // Insert the value at the rear
        printf("Inserted %d into the queue.\n", value);
    }
}
// Function to dequeue (remove) an element from the queue
int dequeue(CircularQueue *q) {
    int value;
    if (isEmpty(q)) {
        printf("Queue Underflow\n");
        return -1; // Return -1 to indicate underflow
    } else {
        value = q->items[q->front];
        if (q->front == q->rear) {
            q->front = q->rear = -1; // Reset front and rear if only one element was present
        } else {
            q->front = (q->front + 1) % SIZE; // Move front pointer circularly
        }
        return value;
    }
}
// Function to display the elements of the queue
void display(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is Empty\n");
    } else {
        int i = q->front;
        printf("Elements in Circular Queue are: ");
        do {
            printf("%d ", q->items[i]);
            i = (i + 1) % SIZE;
        } while (i != (q->rear + 1) % SIZE); // Loop until the rear is reached
        printf("\n");
    }
}
int main() {
    CircularQueue q;
    initializeQueue(&q); // Initialize the queue
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    enqueue(&q, 4);
    enqueue(&q, 5); // Queue is now full: 1 2 3 4 5
    printf("Queue: ");
    display(&q); // Output: 1 2 3 4 5
    dequeue(&q);
    dequeue(&q); // Two elements dequeued
    printf("Queue after two dequeues: ");
    display(&q); // Output: 3 4 5
    enqueue(&q, 6);
    enqueue(&q, 7); // Two elements enqueued
    printf("Queue after two enqueues: ");
    display(&q); // Output: 3 4 5 6 7
    return 0;
}

Output:

Inserted 1 into the queue.
Inserted 2 into the queue.
Inserted 3 into the queue.
Inserted 4 into the queue.
Inserted 5 into the queue.
Queue: Elements in Circular Queue are: 1 2 3 4 5 
Queue after two dequeues: Elements in Circular Queue are: 3 4 5 
Inserted 6 into the queue.
Inserted 7 into the queue.
Queue after two enqueues: Elements in Circular Queue are: 3 4 5 6 7

Complexity Analysis of Circular Queue Using Array

Applications of Circular Queues:

1. CPU Scheduling: Circular queues enable fair and efficient allocation of CPU time to multiple processes, preventing any single process from monopolizing resources.
2. Data Buffering: Circular queues function as temporary data holders in streaming services and multimedia applications, ensuring smooth and uninterrupted playback.
3. Keyboard Buffering: When typing speed exceeds processing speed, circular queues store keystrokes, preventing loss and ensuring they are processed in the correct order.
4. Memory Management: Certain memory allocation strategies utilize circular queues to efficiently manage free memory blocks, optimizing allocation and deallocation processes.
5. Network Packet Handling: Routers frequently use circular queues to handle incoming data packets, ensuring fair and efficient processing and transmission across networks.

Related FAQs