Circular Queue Data Structure

Last Updated: 16 November, 2024 🕓 4 Mins Read

A Queue is a linear data structure to store and manipulate the data elements. A queue follows the concept of "First in, First out" (FIFO), where the first element inserted into the queue is the first one to be deleted from the queue.

A queue is open at both ends which enables insert operations to be performed at one end called REAR or TAIL and delete operations to be performed at another end called FRONT or HEAD.

What is Circular Queue in Data Structure?

A Circular Queue is another type of queue; it also follows the principle of First in, First out" (FIFO). In the circular queue, the last element is connected to the first element of the queue, forming a circle.

A circular queue solves the major limitation of a normal queue. In a normal queue, once a queue is full, we cannot insert a new element, even if there is a space in front of the queue.

A circular queue allows us to keep on inserting an element; if it reaches the end of the queue, then again insert from the start. Such types of queues are very efficient and useful for tasks like buffering data in a computer system, managing waiting lists, and making sure no memory space is wasted.

Circular Queue Representation

Operations on Circular Queue:

Example: Circular Queue Implementation in Java

  
  // Java Program to implement a Circular Queue
  public class CircularQueue {
    
    int queue_size;       // size of the queue
    int[] queueArray;     // Array to store the circular queue elements
    int front;            // Index of the front element
    int rear;             // Index of the rear element
    
    // Constructor
    public CircularQueue(int size) {
      queue_size = size;
      queueArray = new int[queue_size];
      // Initializing front and rear with -1
      front = -1;
      rear = -1;
    }
    
    // Method to enqueue (add) an element in circular queue
    void enqueue(int item) {
      if (isEmpty()) {
        front = 0;
        rear = 0;
        queueArray[rear] = item;
      } else {
        // Circular increment of rear index
        rear = (rear + 1) % queue_size;
        if (rear == front) {
          System.out.println("Queue is full so Enqueue is not possible.");
          
          // Reset rear to its previous value
          rear = (rear - 1 + queue_size) % queue_size;
        } else {
          queueArray[rear] = item;
        }
      }
    }
    
    // Method to Dequeue (remove) an element from the circular queue
    int dequeue() {
      int item = -1; // Assuming -1 represents an empty value
      
      if (!isEmpty()) {
        item = queueArray[front];
        if (front == rear) {
          // Reset front and rear to -1 to indicate an empty queue
          front = -1;
          rear = -1;
        } else {
          // Circular increment of front index
          front = (front + 1) % queue_size;
        }
      } else {
        System.out.println("Queue is empty so Dequeue is not possible.");
      }
      
      return item;
    }
    
    // Method to peek at the front element of the circular queue
    int peek() {
      if (!isEmpty()) {
        return queueArray[front];
      } else {
        System.out.println("Queue is empty");
        return -1; // Assuming -1 represents an empty value
      }
    }
    
    // Method to check circular queue is empty
    public boolean isEmpty() {
      return front == -1 && rear == -1;
    }
    
    public static void main(String[] args) {
      // Create a Circular Queue
      CircularQueue circularQueue = new CircularQueue(5);
      
      // Adding elements in the circular queue
      circularQueue.enqueue(50);
      circularQueue.enqueue(20);
      circularQueue.enqueue(60);
      circularQueue.enqueue(30);
      
      // Peek element from the circular queue
      System.out.println("Front element: " + circularQueue.peek());
      
      // Delete element from the circular queue
      System.out.println("Dequeue: " + circularQueue.dequeue());
      
      // Peek element after dequeue operation
      System.out.println("Peek after dequeue: " + circularQueue.peek());
      
      // Adding more elements in the circular queue
      circularQueue.enqueue(90);
      circularQueue.enqueue(66);
      circularQueue.enqueue(72);
    }
  }

Applications of Circular Queue

Circular queues provide a biggest advantages in terms of space utilization and can improve performance in certain scenarios. However, they have some limitations, such as fixed size and slightly more complex implementation.

Advantages of Circular Queue

Effectively utilize the available array space.

Minimize memory wastage, especially when dealing with fixed-size buffers.

Improved Performance

No Need for Shifting Elements

Useful in situations where cyclical resource management is required.

Consistent Time Complexity O(1) for Enqueue and dequeue operations.

Implementation is simple and understandable.