Circular queue

Overview

A circular queue (ring buffer) stores a queue in a fixed-size array and wraps indexes around with modulo arithmetic. When the back reaches the end of the array, it continues at index 0, reusing slots freed by dequeues.

It gives O(1) enqueue and dequeue with no memory allocation after creation, which is why it is used in audio pipelines, network drivers, logging systems, and anywhere memory must be predictable.

When to use it

• The maximum size is known in advance.
• You need O(1) queue operations with no allocations (real-time or embedded systems).
• You want to keep only the last k items: recent logs, moving averages.
• Round-robin problems where positions wrap around (circular arrays).

Problem patterns it solves

Where it is used in real software

Key terms

Capacity

Fixed number of slots k.

front / head

Index of the oldest element.

count

Number of stored elements; distinguishes full from empty.

Wrap-around

next = (index + 1) % capacity.

rear

(front + count - 1) % capacity, the index of the newest element.

Operations using front and count

1. 1
   Allocate

   data = new Array(k), front = 0, count = 0.

2. 2
   enQueue(x)

   If count === k, it is full. Otherwise write data[(front + count) % k] = x and count++.

3. 3
   deQueue()

   If count === 0, it is empty. Otherwise front = (front + 1) % k and count--.

4. 4
   Front()

   data[front] when not empty.

5. 5
   Rear()

   data[(front + count - 1) % k] when not empty.

Operation trace (capacity 3)

front = 0, count = 0

Tracking count avoids the classic ambiguity where front === rear could mean either full or empty.

Implementation

1class MyCircularQueue {2  constructor(k) {3    this.data = new Array(k);4    this.capacity = k;5    this.front = 0;6    this.count = 0;7  }8  enQueue(value) {9    if (this.isFull()) return false;10    this.data[(this.front + this.count) % this.capacity] = value;11    this.count++;12    return true;13  }14  deQueue() {15    if (this.isEmpty()) return false;16    this.front = (this.front + 1) % this.capacity;17    this.count--;18    return true;19  }20  Front() { return this.isEmpty() ? -1 : this.data[this.front]; }21  Rear() {22    return this.isEmpty() ? -1 : this.data[(this.front + this.count - 1) % this.capacity];23  }24  isEmpty() { return this.count === 0; }25  isFull() { return this.count === this.capacity; }26}27 28// Circular array trick: iterate 2n times with i % n29function nextGreaterElements(nums) {30  const n = nums.length;31  const result = new Array(n).fill(-1);32  const stack = [];33  for (let i = 0; i < 2 * n; i++) {34    const idx = i % n;35    while (stack.length && nums[stack.at(-1)] < nums[idx]) {36      result[stack.pop()] = nums[idx];37    }38    if (i < n) stack.push(idx);39  }40  return result;41}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Ambiguous full vs empty when using only front and rear.

  Fix: Track count, or leave one slot always empty.

• Negative modulo in JavaScript and Java.

  Fix: (-1) % 4 is -1. Use (i - 1 + k) % k when moving backward.

• Reading slots of dequeued items.

  Fix: Only read indexes within [front, front + count).

Interview questions

Practice problems