Circular Queues

November 19, 2025
#circular-queue #ring-buffer #queue #data-structures #algorithms

Table of Contents

Introduction

A circular queue (also called a ring buffer) is a linear data structure that uses a fixed-size array in a circular manner. Unlike a regular queue where dequeued elements leave wasted space at the front, a circular queue reuses that space by wrapping around to the beginning when reaching the end of the array.

Think of it like a circular track where runners keep going around—when you reach the end, you simply continue from the start. This makes circular queues incredibly efficient for fixed-size buffers in streaming applications, producer-consumer problems, and resource management systems.

If you’re new to queues, review Queues, Arrays, and Big-O Notation first.

What is a circular queue?

A circular queue is a queue implementation that:

  1. Uses a fixed-size array to store elements
  2. Maintains front and rear pointers that wrap around
  3. Reuses space freed by dequeue operations
  4. Efficiently handles a bounded number of elements

Core operations:

  1. Enqueue: Add an element at the rear (if not full)
  2. Dequeue: Remove an element from the front (if not empty)
  3. Peek: View the front element without removing it
  4. isEmpty: Check if the queue is empty
  5. isFull: Check if the queue is full
  6. size: Get the current number of elements

Why use a circular queue?

Choose a circular queue when:

  1. You have a fixed-size buffer requirement
  2. You need to avoid memory waste in array-based queues
  3. You’re implementing producer-consumer patterns with bounded buffers
  4. You’re working with streaming data (audio, video, network packets)
  5. You need predictable memory usage (no dynamic allocation)
  6. You’re building resource pools (connection pools, thread pools)

Avoid a circular queue when:

  • You need unlimited growth (use a linked list queue)
  • You need access to arbitrary elements (use an array)
  • You need operations at both ends (use a deque)

Real-world applications

Circular queues are used extensively:

  • Audio/Video buffers: Streaming media players use ring buffers to handle data
  • Keyboard buffers: Storing keystrokes before processing
  • Network traffic management: Packet buffers in routers and switches
  • CPU scheduling: Round-robin scheduling algorithms
  • Circular logging: Log files that overwrite oldest entries when full
  • Connection pools: Managing fixed-size database connection pools
  • Memory management: Circular buffer for inter-process communication
  • Game development: Managing fixed-size event queues

Circular Queue vs Regular Queue

Feature Circular Queue Regular Queue (Array) Regular Queue (Linked List)
Memory usage Fixed, efficient Fixed, wasteful space Dynamic, overhead per node
Enqueue O(1) O(1) O(1)
Dequeue O(1) O(n) (shift) or O(1) (wasteful) O(1)
Space reuse ✅ Yes ❌ No ✅ Yes (via GC)
Capacity Fixed Fixed or resizable Unlimited
Cache locality ✅ Excellent ✅ Excellent ❌ Poor
Memory predictability ✅ Guaranteed ✅ Guaranteed ❌ Variable

How circular queues work

The key insight is using modular arithmetic to wrap indices:

nextIndex = (currentIndex + 1) % capacity

Visual representation:

Initial empty queue (capacity = 5):
[_, _, _, _, _]
 ↑
 front=rear=0

After enqueue(10, 20, 30):
[10, 20, 30, _, _]
 ↑          ↑
 front=0    rear=3

After dequeue() twice:
[_, _, 30, _, _]
       ↑   ↑
       front=2, rear=3

After enqueue(40, 50, 60):
[60, _, 30, 40, 50]
     ↑  ↑
     rear=1, front=2

Wrapping around!

Core operations and complexity

All circular queue operations are constant time:

  • Enqueue: O(1) — add element at rear (if not full)
  • Dequeue: O(1) — remove element from front (if not empty)
  • Peek: O(1) — view front element
  • isEmpty: O(1) — check if empty
  • isFull: O(1) — check if full
  • size: O(1) — get current size
  • Space: O(n) — fixed capacity n

Circular queue implementation

Method 1: Using an extra variable for size

class CircularQueue {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.capacity = capacity;
    this.front = 0;
    this.rear = 0;
    this.size = 0;
  }

  enqueue(element) {
    if (this.isFull()) {
      throw new Error("Queue is full");
    }
    this.items[this.rear] = element;
    this.rear = (this.rear + 1) % this.capacity;
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    const element = this.items[this.front];
    this.items[this.front] = undefined; // Optional: clear reference
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return element;
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.front];
  }

  isEmpty() {
    return this.size === 0;
  }

  isFull() {
    return this.size === this.capacity;
  }

  getSize() {
    return this.size;
  }

  display() {
    if (this.isEmpty()) {
      return [];
    }
    const result = [];
    let count = this.size;
    let index = this.front;
    while (count > 0) {
      result.push(this.items[index]);
      index = (index + 1) % this.capacity;
      count--;
    }
    return result;
  }
}

// Example usage
const cq = new CircularQueue(5);
cq.enqueue(10);
cq.enqueue(20);
cq.enqueue(30);
console.log(cq.display());      // [10, 20, 30]
console.log(cq.dequeue());      // 10
cq.enqueue(40);
cq.enqueue(50);
cq.enqueue(60);
console.log(cq.display());      // [20, 30, 40, 50, 60]
console.log(cq.isFull());       // true

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

    def enqueue(self, element):
        if self.is_full():
            raise Exception("Queue is full")
        self.items[self.rear] = element
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            return None
        element = self.items[self.front]
        self.items[self.front] = None  # Optional: clear reference
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return element

    def peek(self):
        if self.is_empty():
            return None
        return self.items[self.front]

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.capacity

    def get_size(self):
        return self.size

    def display(self):
        if self.is_empty():
            return []
        result = []
        count = self.size
        index = self.front
        while count > 0:
            result.append(self.items[index])
            index = (index + 1) % self.capacity
            count -= 1
        return result

# Example usage
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
print(cq.display())       # [10, 20, 30]
print(cq.dequeue())       # 10
cq.enqueue(40)
cq.enqueue(50)
cq.enqueue(60)
print(cq.display())       # [20, 30, 40, 50, 60]
print(cq.is_full())       # True

public class CircularQueue {
    private int[] items;
    private int capacity;
    private int front;
    private int rear;
    private int size;

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

    public void enqueue(int element) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        items[rear] = element;
        rear = (rear + 1) % capacity;
        size++;
    }

    public Integer dequeue() {
        if (isEmpty()) {
            return null;
        }
        int element = items[front];
        front = (front + 1) % capacity;
        size--;
        return element;
    }

    public Integer peek() {
        if (isEmpty()) {
            return null;
        }
        return items[front];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public int getSize() {
        return size;
    }

    public void display() {
        if (isEmpty()) {
            System.out.println("[]");
            return;
        }
        System.out.print("[");
        int count = size;
        int index = front;
        while (count > 0) {
            System.out.print(items[index]);
            if (count > 1) System.out.print(", ");
            index = (index + 1) % capacity;
            count--;
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        CircularQueue cq = new CircularQueue(5);
        cq.enqueue(10);
        cq.enqueue(20);
        cq.enqueue(30);
        cq.display();           // [10, 20, 30]
        System.out.println(cq.dequeue());  // 10
        cq.enqueue(40);
        cq.enqueue(50);
        cq.enqueue(60);
        cq.display();           // [20, 30, 40, 50, 60]
        System.out.println(cq.isFull());   // true
    }
}

Method 2: Sacrificing one slot (without size variable)

An alternative approach uses one empty slot to distinguish between full and empty states:

  • Empty: front == rear
  • Full: (rear + 1) % capacity == front
class CircularQueueAlt {
  constructor(capacity) {
    this.items = new Array(capacity + 1); // Extra slot
    this.capacity = capacity + 1;
    this.front = 0;
    this.rear = 0;
  }

  enqueue(element) {
    if (this.isFull()) {
      throw new Error("Queue is full");
    }
    this.items[this.rear] = element;
    this.rear = (this.rear + 1) % this.capacity;
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    const element = this.items[this.front];
    this.front = (this.front + 1) % this.capacity;
    return element;
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.front];
  }

  isEmpty() {
    return this.front === this.rear;
  }

  isFull() {
    return (this.rear + 1) % this.capacity === this.front;
  }

  size() {
    return (this.rear - this.front + this.capacity) % this.capacity;
  }
}

// Example usage
const cq = new CircularQueueAlt(5);
cq.enqueue(10);
cq.enqueue(20);
console.log(cq.size());    // 2
console.log(cq.dequeue()); // 10

class CircularQueueAlt:
    def __init__(self, capacity):
        self.items = [None] * (capacity + 1)  # Extra slot
        self.capacity = capacity + 1
        self.front = 0
        self.rear = 0

    def enqueue(self, element):
        if self.is_full():
            raise Exception("Queue is full")
        self.items[self.rear] = element
        self.rear = (self.rear + 1) % self.capacity

    def dequeue(self):
        if self.is_empty():
            return None
        element = self.items[self.front]
        self.front = (self.front + 1) % self.capacity
        return element

    def peek(self):
        if self.is_empty():
            return None
        return self.items[self.front]

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

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

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

# Example usage
cq = CircularQueueAlt(5)
cq.enqueue(10)
cq.enqueue(20)
print(cq.size())     # 2
print(cq.dequeue())  # 10

public class CircularQueueAlt {
    private int[] items;
    private int capacity;
    private int front;
    private int rear;

    public CircularQueueAlt(int capacity) {
        this.items = new int[capacity + 1]; // Extra slot
        this.capacity = capacity + 1;
        this.front = 0;
        this.rear = 0;
    }

    public void enqueue(int element) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        items[rear] = element;
        rear = (rear + 1) % capacity;
    }

    public Integer dequeue() {
        if (isEmpty()) {
            return null;
        }
        int element = items[front];
        front = (front + 1) % capacity;
        return element;
    }

    public Integer peek() {
        if (isEmpty()) {
            return null;
        }
        return items[front];
    }

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

    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

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

    public static void main(String[] args) {
        CircularQueueAlt cq = new CircularQueueAlt(5);
        cq.enqueue(10);
        cq.enqueue(20);
        System.out.println(cq.size());     // 2
        System.out.println(cq.dequeue());  // 10
    }
}

Common circular queue problems

1. Design circular buffer for producer-consumer

Implement a thread-safe circular buffer:

class ProducerConsumerBuffer {
  constructor(capacity) {
    this.queue = new CircularQueue(capacity);
  }

  produce(item) {
    if (this.queue.isFull()) {
      console.log(`Buffer full. Dropping item: ${item}`);
      return false;
    }
    this.queue.enqueue(item);
    console.log(`Produced: ${item}`);
    return true;
  }

  consume() {
    if (this.queue.isEmpty()) {
      console.log("Buffer empty. Nothing to consume.");
      return null;
    }
    const item = this.queue.dequeue();
    console.log(`Consumed: ${item}`);
    return item;
  }
}

// Example usage
const buffer = new ProducerConsumerBuffer(3);
buffer.produce(1);
buffer.produce(2);
buffer.produce(3);
buffer.produce(4); // Buffer full
buffer.consume();
buffer.produce(4);

class ProducerConsumerBuffer:
    def __init__(self, capacity):
        self.queue = CircularQueue(capacity)

    def produce(self, item):
        if self.queue.is_full():
            print(f"Buffer full. Dropping item: {item}")
            return False
        self.queue.enqueue(item)
        print(f"Produced: {item}")
        return True

    def consume(self):
        if self.queue.is_empty():
            print("Buffer empty. Nothing to consume.")
            return None
        item = self.queue.dequeue()
        print(f"Consumed: {item}")
        return item

# Example usage
buffer = ProducerConsumerBuffer(3)
buffer.produce(1)
buffer.produce(2)
buffer.produce(3)
buffer.produce(4)  # Buffer full
buffer.consume()
buffer.produce(4)

public class ProducerConsumerBuffer {
    private CircularQueue queue;

    public ProducerConsumerBuffer(int capacity) {
        this.queue = new CircularQueue(capacity);
    }

    public boolean produce(int item) {
        if (queue.isFull()) {
            System.out.println("Buffer full. Dropping item: " + item);
            return false;
        }
        queue.enqueue(item);
        System.out.println("Produced: " + item);
        return true;
    }

    public Integer consume() {
        if (queue.isEmpty()) {
            System.out.println("Buffer empty. Nothing to consume.");
            return null;
        }
        int item = queue.dequeue();
        System.out.println("Consumed: " + item);
        return item;
    }

    public static void main(String[] args) {
        ProducerConsumerBuffer buffer = new ProducerConsumerBuffer(3);
        buffer.produce(1);
        buffer.produce(2);
        buffer.produce(3);
        buffer.produce(4); // Buffer full
        buffer.consume();
        buffer.produce(4);
    }
}

2. Moving average from data stream

Calculate the moving average of the last N elements:

class MovingAverage {
  constructor(size) {
    this.queue = new CircularQueue(size);
    this.sum = 0;
  }

  next(val) {
    if (this.queue.isFull()) {
      this.sum -= this.queue.dequeue();
    }
    this.queue.enqueue(val);
    this.sum += val;
    return this.sum / this.queue.getSize();
  }
}

// Example usage
const ma = new MovingAverage(3);
console.log(ma.next(1));  // 1.0
console.log(ma.next(10)); // 5.5
console.log(ma.next(3));  // 4.666...
console.log(ma.next(5));  // 6.0

class MovingAverage:
    def __init__(self, size):
        self.queue = CircularQueue(size)
        self.sum = 0

    def next(self, val):
        if self.queue.is_full():
            self.sum -= self.queue.dequeue()
        self.queue.enqueue(val)
        self.sum += val
        return self.sum / self.queue.get_size()

# Example usage
ma = MovingAverage(3)
print(ma.next(1))   # 1.0
print(ma.next(10))  # 5.5
print(ma.next(3))   # 4.666...
print(ma.next(5))   # 6.0

public class MovingAverage {
    private CircularQueue queue;
    private double sum;

    public MovingAverage(int size) {
        this.queue = new CircularQueue(size);
        this.sum = 0;
    }

    public double next(int val) {
        if (queue.isFull()) {
            sum -= queue.dequeue();
        }
        queue.enqueue(val);
        sum += val;
        return sum / queue.getSize();
    }

    public static void main(String[] args) {
        MovingAverage ma = new MovingAverage(3);
        System.out.println(ma.next(1));   // 1.0
        System.out.println(ma.next(10));  // 5.5
        System.out.println(ma.next(3));   // 4.666...
        System.out.println(ma.next(5));   // 6.0
    }
}

Common pitfalls

  • Off-by-one errors: Carefully handle modular arithmetic with front and rear pointers
  • Full vs empty confusion: Distinguish between full and empty states correctly (use size or sacrifice one slot)
  • Not checking bounds: Always verify isFull() before enqueue and isEmpty() before dequeue
  • Incorrect size calculation: When using the sacrificed-slot method, size formula is (rear - front + capacity) % capacity
  • Integer overflow: In languages with fixed-size integers, ensure indices don’t overflow

When to prefer other data structures

  • Need unlimited capacity → Use linked list queue
  • Need both-end operations → Use deque
  • Need LIFO → Use stack
  • Need random access → Use array

Practice problems

  1. Implement a circular queue that automatically doubles capacity when full
  2. Design a circular buffer that tracks the maximum element in O(1) time
  3. Implement a circular queue with priority (multiple circular queues)
  4. Solve the “Design Hit Counter” problem using a circular queue
  5. Implement a circular buffer for audio processing with fade-in/fade-out
  6. Design a rate limiter using a circular queue
  7. Create a circular queue that supports bulk enqueue/dequeue operations
  8. Implement a circular log buffer that overwrites oldest entries
  9. Design a packet buffer for network simulation with circular queue
  10. Solve “Design Circular Deque” on LeetCode

Complexity summary

  • 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 fixed capacity

Circular queues provide the efficiency of array-based access with optimal space utilization, making them perfect for bounded buffers and fixed-size streaming applications.

Thanks for visiting
We are actively updating content to this site. Thanks for visiting! Please bookmark this page and visit again soon.
Sponsor