Circular Queue

What is a Circular Queue?

A Circular Queue is an advanced version of a linear queue that connects the end of the queue back to the front, forming a circle. This efficient structure prevents memory wastage and allows better utilization of fixed-size buffers.

Key Characteristics

Circular queues have these fundamental properties:

  1. Fixed capacity: Size is predetermined at creation
  2. Two pointers:
    • Front: Points to the first element
    • Rear: Points to the last element
  3. Circular behavior: When pointers reach the end, they wrap around to the start
  4. Efficient space utilization: Reuses empty spaces created after dequeues

Visual Example (Size=5)

Operation sequence on an empty circular queue:

  1. enqueue(10): [10, _, _, _, _] (F=0, R=0)
  2. enqueue(20): [10, 20, _, _, _] (F=0, R=1)
  3. enqueue(30): [10, 20, 30, _, _] (F=0, R=2)
  4. dequeue(): Returns 10 → [_, 20, 30, _, _] (F=1, R=2)
  5. enqueue(40): [_, 20, 30, 40, _] (F=1, R=3)
  6. enqueue(50): [_, 20, 30, 40, 50] (F=1, R=4)
  7. enqueue(60): [60, 20, 30, 40, 50] (F=1, R=0) ← Wraps around!

Implementation Details

Key implementation aspects:

  1. Pointer Movement:
    • front = (front + 1) % capacity
    • rear = (rear + 1) % capacity
  2. Full/Empty Conditions:
    • Full: (rear + 1) % capacity == front
    • Empty: front == rear
  3. Always one empty slot:
    • Needed to distinguish between full and empty states

Time Complexity

  • enqueue(): O(1)
  • dequeue(): O(1)
  • peekFront(): O(1)
  • peekRear(): O(1)
  • isEmpty(): O(1)
  • isFull(): O(1)

Applications

Circular queues are used in:

  • CPU Scheduling: Round-robin scheduling algorithms
  • Memory Management: Circular buffers in memory systems
  • Traffic Systems: Controlling the flow of traffic signals
  • Data Streams: Handling continuous data streams (audio/video buffers)
  • Producer-Consumer Problems: Where producers and consumers operate at different rates

Advantages Over Linear Queue

  • Better memory utilization: Reuses empty spaces
  • Efficient operations: No need to shift elements
  • Fixed memory footprint: Predictable memory usage
  • Real-time systems friendly: Bounded execution time

The circular queue is an essential data structure for systems requiring efficient, fixed-size buffers with constant-time operations. Its circular nature solves the memory wastage problem of linear queues while maintaining simple and predictable performance characteristics, making it ideal for low-level system programming and real-time applications.

Visualize Circular Queue Operations

Queue is empty
Front: NoneRear: None
Queue is empty

Test Your Knowledge before moving forward!

Queue Quiz Challenge

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Double Ended Queue Implementation

// Circular Queue Implementation (JavaScript)
class CircularQueue {
  constructor(capacity) {
    this.queue = new Array(capacity);
    this.capacity = capacity;
    this.front = -1;
    this.rear = -1;
    this.size = 0;
  }

  // Check if queue is full
  isFull() {
    return this.size === this.capacity;
  }

  // Check if queue is empty
  isEmpty() {
    return this.size === 0;
  }

  // Add element to the queue
  enqueue(item) {
    if (this.isFull()) {
      console.log("Queue is full");
      return false;
    }
    
    if (this.isEmpty()) {
      this.front = 0;
    }
    
    this.rear = (this.rear + 1) % this.capacity;
    this.queue[this.rear] = item;
    this.size++;
    return true;
  }

  // Remove element from the queue
  dequeue() {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return null;
    }
    
    const item = this.queue[this.front];
    this.queue[this.front] = null;
    
    if (this.front === this.rear) {
      this.front = -1;
      this.rear = -1;
    } else {
      this.front = (this.front + 1) % this.capacity;
    }
    
    this.size--;
    return item;
  }

  // Get front element without removing it
  peek() {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return null;
    }
    return this.queue[this.front];
  }

  // Print queue contents
  print() {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return;
    }
    
    let i = this.front;
    let output = [];
    
    while (true) {
      output.push(this.queue[i]);
      if (i === this.rear) break;
      i = (i + 1) % this.capacity;
    }
    
    console.log("Queue contents:", output.join(' -> '));
    console.log("Front index:", this.front, "Rear index:", this.rear);
  }
}

// Usage
const queue = new CircularQueue(5);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
queue.enqueue(50);
queue.print(); // 10 -> 20 -> 30 -> 40 -> 50
console.log("Dequeued:", queue.dequeue()); // 10
queue.enqueue(60);
queue.print(); // 20 -> 30 -> 40 -> 50 -> 60
console.log("Front element:", queue.peek()); // 20

Explore Other Types

Single Ended Queue

Double Ended Queue

Multiple Queue

Priority Queue