Queue

Circular Queue

What is a Circular Queue?

A circular queue takes a regular array-based queue and wraps its rear index back to the beginning once it hits the end: instead of a straight line, the underlying array is treated like a loop.

Key Characteristics

Circular queues have these fundamental properties:

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

How Does It Work?

The array is the same as ever — only the arithmetic changes. Picture the five slots bent into a ring so index 4 hands straight over to index 0. front marks the first element, rear marks the next free slot, and both advance with (i + 1) % capacity:

Start empty. front and rear both sit on index 0.
enqueue(10), enqueue(20), enqueue(30) — each write lands on rear, then rear steps forward.
dequeue() twice — 10 and 20 leave, and front steps forward to index 2. Slots 0 and 1 are now free again.
enqueue(40), enqueue(50) — rear fills index 3, then 4, and wraps back around to index 0.
enqueue(60) — it reuses slot 0, freed way back by the first dequeue. Now (rear + 1) % 5 === front, so the queue reports full.

Occupied slotFree slot

Step 5 is what a linear array queue cannot do. There, once rear reached the end the queue was "full" even with two empty slots at the start, and the only fix was shifting every element down. Here rear simply wraps to index 0 and reuses that space in constant time.

It also shows why one slot is always sacrificed: front and rear landing on the same index has to mean something definite. Kept as "empty", a full queue must stop one slot short — which is why capacity 5 holds at most 4 elements.

Implementation Details

Key implementation aspects:

Pointer Movement:
- front = (front + 1) % capacity
- rear = (rear + 1) % capacity
Full/Empty Conditions:
- Full: (rear + 1) % capacity == front
- Empty: front == rear
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)

The modulo keeps every operation to a single index update, with no shifting and no scanning, so the cost never grows with the queue:

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

That one change fixes the biggest annoyance with a plain array queue: slots freed up by earlier dequeues no longer go to waste. It keeps every operation running in constant time, which is why circular queues show up so often in fixed-size buffers, like the ones used in low-level or real-time systems.

Daily DSA Challenge by Scale Engineer

Circular Queue Visualiser (Fixed Capacity)

Capacity:

Circular queue is empty

Test Your Knowledge before moving forward!

Circular Queue Quiz

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)

Circular 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

Done With the Learning

Mark Circular Queue as done and view it on your dashboard

Explore Other Types

Single Ended Queue

Double Ended Queue

Multiple Queue

Priority Queue