Circular Queue Data Structure

Introduction to Circular Queue

A circular queue is a linear data structure that follows the First In First Out (FIFO) principle, similar to a regular queue. However, in a circular queue, the last position is connected back to the first position to form a circle. This circular arrangement allows for efficient use of space, as it enables the queue to utilize any free space created by dequeue operations without shifting elements.

alt text

Circular Queue Operations

Enqueue: Add an element to the back of the queue.
Dequeue: Remove the element from the front of the queue.
Peek: Retrieve the element at the front of the queue without removing it.
isEmpty: Check if the queue is empty.
isFull: Check if the queue is full.
Size: Get the number of elements in the queue.

Pseudocode

Basic Operations

Enqueue:

function enqueue(circularQueue, element):
     if isFull(circularQueue):
          return "Queue Overflow"
     circularQueue.rear = (circularQueue.rear + 1) % circularQueue.size
     circularQueue.elements[circularQueue.rear] = element

Dequeue:

function dequeue(circularQueue):
     if isEmpty(circularQueue):
          return "Queue Underflow"
     frontElement = circularQueue.elements[circularQueue.front]
     circularQueue.front = (circularQueue.front + 1) % circularQueue.size
     return frontElement

Peek:

function peek(circularQueue):
     if isEmpty(circularQueue):
          return "Queue is empty"
     return circularQueue.elements[circularQueue.front]

isEmpty:

function isEmpty(circularQueue):
     return circularQueue.front == circularQueue.rear

isFull:

function isFull(circularQueue):
     return (circularQueue.rear + 1) % circularQueue.size == circularQueue.front

Size:

function size(circularQueue):
     return (circularQueue.rear - circularQueue.front + circularQueue.size) % circularQueue.size

Implementation in Python, C++, and Java

Python Implementation

class CircularQueue:
     def __init__(self, size):
          self.size = size
          self.elements = [None] * size
          self.front = 0
          self.rear = 0

     def enqueue(self, element):
          if self.is_full():
               return "Queue Overflow"
          self.rear = (self.rear + 1) % self.size
          self.elements[self.rear] = element

     def dequeue(self):
          if self.is_empty():
               return "Queue Underflow"
          frontElement = self.elements[self.front]
          self.front = (self.front + 1) % self.size
          return frontElement

     def peek(self):
          if self.is_empty():
               return "Queue is empty"
          return self.elements[self.front]

     def is_empty(self):
          return self.front == self.rear

     def is_full(self):
          return (self.rear + 1) % self.size == self.front

     def size(self):
          return (self.rear - self.front + self.size) % self.size

# Example usage
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
print(cq.dequeue())  # Output: 10
print(cq.peek())     # Output: 20
print(cq.is_empty()) # Output: False
print(cq.size())     # Output: 1

C++ Implementation

#include <iostream>
using namespace std;

class CircularQueue {
private:
     int *elements;
     int front, rear, size;

public:
     CircularQueue(int size) {
          this->size = size;
          elements = new int[size];
          front = rear = 0;
     }

     void enqueue(int element) {
          if (is_full()) {
               cout << "Queue Overflow" << endl;
               return;
          }
          rear = (rear + 1) % size;
          elements[rear] = element;
     }

     int dequeue() {
          if (is_empty()) {
               cout << "Queue Underflow" << endl;
               return -1; // Indicating underflow
          }
          int frontElement = elements[front];
          front = (front + 1) % size;
          return frontElement;
     }

     int peek() {
          if (is_empty()) {
               cout << "Queue is empty" << endl;
               return -1; // Indicating empty
          }
          return elements[front];
     }

     bool is_empty() {
          return front == rear;
     }

     bool is_full() {
          return (rear + 1) % size == front;
     }

     int size_of_queue() {
          return (rear - front + size) % size;
     }

     ~CircularQueue() {
          delete[] elements;
     }
};

// Example usage
int main() {
     CircularQueue cq(5);
     cq.enqueue(10);
     cq.enqueue(20);
     cout << cq.dequeue() << endl;  // Output: 10
     cout << cq.peek() << endl;      // Output: 20
     cout << boolalpha << cq.is_empty() << endl; // Output: false
     cout << cq.size_of_queue() << endl; // Output: 1
     return 0;
}

Java Implementation

public class CircularQueue {
     private int[] elements;
     private int front, rear, size;

     public CircularQueue(int size) {
          this.size = size;
          elements = new int[size];
          front = rear = 0;
     }

     public void enqueue(int element) {
          if (is_full()) {
               System.out.println("Queue Overflow");
               return;
          }
          rear = (rear + 1) % size;
          elements[rear] = element;
     }

     public int dequeue() {
          if (is_empty()) {
               System.out.println("Queue Underflow");
               return -1; // Indicating underflow
          }
          int frontElement = elements[front];
          front = (front + 1) % size;
          return frontElement;
     }

     public int peek() {
          if (is_empty()) {
               System.out.println("Queue is empty");
               return -1; // Indicating empty
          }
          return elements[front];
     }

     public boolean is_empty() {
          return front == rear;
     }

     public boolean is_full() {
          return (rear + 1) % size == front;
     }

     public int size_of_queue() {
          return (rear - front + size) % size;
     }

     // Example usage
     public static void main(String[] args) {
          CircularQueue cq = new CircularQueue(5);
          cq.enqueue(10);
          cq.enqueue(20);
          System.out.println(cq.dequeue());  // Output: 10
          System.out.println(cq.peek());      // Output: 20
          System.out.println(cq.is_empty());  // Output: false
          System.out.println(cq.size_of_queue()); // Output: 1
     }
}

C Implementation

#include <stdio.h>

#define SIZE 5

int items[SIZE];
int front = -1, rear = -1;

// Check if the queue is full
int isFull() {
    return (front == (rear + 1) % SIZE) || (front == 0 && rear == SIZE - 1);
}

// Check if the queue is empty
int isEmpty() {
    return front == -1;
}

// Add an element to the queue
void enQueue(int element) {
    if (isFull()) {
        printf("\nQueue is full!!\n");
    } else {
        if (isEmpty()) {
            front = 0;
        }
        rear = (rear + 1) % SIZE;
        items[rear] = element;
        printf("\nInserted -> %d", element);
    }
}

// Remove an element from the queue
int deQueue() {
    if (isEmpty()) {
        printf("\nQueue is empty!!\n");
        return -1;
    } else {
        int element = items[front];
        if (front == rear) { // Queue has only one element
            front = -1;
            rear = -1;
        } else {
            front = (front + 1) % SIZE;
        }
        printf("\nDeleted element -> %d\n", element);
        return element;
    }
}

// Display the elements in the queue
void display() {
    if (isEmpty()) {
        printf("\nEmpty Queue\n");
    } else {
        printf("\nFront -> %d\n", front);
        printf("Items -> ");
        for (int i = front; i != rear; i = (i + 1) % SIZE) {
            printf("%d ", items[i]);
        }
        printf("%d ", items[rear]); // Print the last element
        printf("\nRear -> %d\n", rear);
    }
}

int main() {
    deQueue(); // Attempt to dequeue from an empty queue

    enQueue(1);
    enQueue(2);
    enQueue(3);
    enQueue(4);
    enQueue(5);

    enQueue(6); // Attempt to enqueue into a full queue

    display(); // Display the queue

    deQueue(); // Dequeue one element
    display(); // Display the queue again

    enQueue(7); // Enqueue one element to test circular queue functionality
    display(); // Display the queue

    enQueue(8); // Attempt to enqueue into a full queue

    return 0;
}

Complexity

Time Complexity:
- Enqueue: $O(1)$
- Dequeue: $O(1)$
- Peek: $O(1)$
- isEmpty: $O(1)$
- isFull: $O(1)$
- Size: $O(1)$
Space Complexity: $O(n)$ , where $n$ is the number of elements that can be stored in the circular queue.

Example

Consider a circular queue with the following operations:

Enqueue 10
Enqueue 20
Dequeue
Peek
Check if empty
Get size

Operations:

Enqueue 10: Queue becomes [10, _, _, _, _]
Enqueue 20: Queue becomes [10, 20, _, _, _]
Dequeue: Removes 10, Queue becomes [_, 20, _, _, _]
Peek: Returns 20, Queue remains [_, 20, _, _, _]
isEmpty: Returns false
Size: Returns 1

Conclusion

A circular queue is an efficient data structure that improves the utilization of space in scenarios where a standard linear queue might lead to wasted memory due to the shifting of elements. It is widely used in applications such as CPU scheduling, resource sharing, and buffering tasks in operating systems. Understanding and implementing a circular queue can significantly enhance performance and memory management in various algorithms and systems.

Introduction to Circular Queue​

Circular Queue Operations​

Pseudocode​

Basic Operations​

Implementation in Python, C++, and Java​

Python Implementation​

C++ Implementation​

Java Implementation​

C Implementation​

Complexity​

Example​

Conclusion​