Queue Design

Circular Queue

A fixed-size queue using an array with front and rear pointers that wrap around (using modulo). When rear reaches the end, it wraps to index 0. Full when (rear+1) % size == front.

O(1) per op

O(n)

say this out loud

A fixed capacity ring, so I keep head and tail with modular arithmetic and one extra flag or slot to tell full apart from empty.

How It Works

A circular queue implements FIFO on a fixed array by letting the front and rear positions wrap around with modulo arithmetic. Enqueue writes at the rear and advances it by (rear + 1) mod capacity; dequeue reads at the front and advances it the same way. Wrapping means dequeued slots at the start of the array get reused, so the structure never shifts elements. Every operation is O(1) with zero allocation after construction.

The subtle design question is telling full from empty, since front == rear describes both. Standard fixes: keep an explicit size counter, or allocate one extra slot and declare the queue full when (rear + 1) mod capacity == front. This layout is called a ring buffer in systems code.

Step-by-Step Visualization

A circular queue of capacity 4, backed by a fixed array

size0

1/8

Code

Java

class CircularQueue {
  int[] arr;
  int front = 0, rear = -1, size = 0, cap;

  CircularQueue(int k) { arr = new int[k]; cap = k; }

  boolean enqueue(int val) {
    if (size == cap) return false;
    rear = (rear + 1) % cap;
    arr[rear] = val;
    size++;
    return true;
  }

  boolean dequeue() {
    if (size == 0) return false;
    front = (front + 1) % cap;
    size--;
    return true;
  }
}

Tips & Gotchas

1Use an array with front and rear pointers that wrap around

2Modular arithmetic: next = (pos + 1) % capacity

3Track size or use a gap to distinguish full from empty

Practice Problems

1Design Circular Queue
2Design Circular Deque
3Moving Average from Data Stream

About the Queue Design Pattern

Classic design problems that test your understanding of how queues work internally.

Key insight

BFS = queue. If you need shortest path in an unweighted graph or level-order traversal, reach for a queue. Monotonic deques solve sliding window extremes in O(n).

Common Queue / Deque Interview Problems

Binary Tree Level Order Traversal
Sliding Window Maximum
Rotting Oranges
Shortest Path in Binary Matrix
Implement Queue using Stacks

Frequently Asked Questions

Which full-versus-empty strategy should I pick in an interview?

The size counter is easiest to reason about and makes isEmpty and isFull trivial, at the cost of one extra field. The sacrificial-slot trick avoids the counter but wastes one array cell and produces trickier conditions. Either is accepted; just state the ambiguity you are resolving.

Why choose a ring buffer over a dynamic list or linked queue?

Bounded memory and cache-friendly O(1) operations with no per-element allocation. Real systems (IO buffers, producer-consumer channels, schedulers) use ring buffers precisely because the fixed capacity doubles as natural backpressure.