Design Circular Queue

Medium Design Data Structures Queue / Circular Buffer Original on LeetCode

Design Circular Queue is a medium design data structures problem solved with the queue / circular buffer pattern. The best approach, optimal (ring buffer with head and count), runs in O(1) for every operation time and O(k) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (shifting list) up.

Problem

Implement MyCircularQueue, a FIFO queue with a fixed capacity k that reuses the slots freed at the front (a ring buffer), so it never needs to shift elements.

enQueue(value) adds value at the rear and returns true, or returns false if the queue is full. deQueue() removes the front element and returns true, or returns false if the queue is empty. Front() and Rear() return the first and last element, or -1 when the queue is empty. isEmpty() and isFull() report whether the queue holds 0 or k elements.

Examples

Example 1

Input
MyCircularQueue(2), enQueue(4), enQueue(9), enQueue(1), Rear(), isFull(), deQueue(), enQueue(1), Front(), Rear()
Output
true, true, false, 9, true, true, true, 9, 1
Why
The third enQueue fails because the queue already holds 2 items. After removing 4, there is room for 1, which wraps around to the freed slot.

Example 2

Input
MyCircularQueue(1), Front(), deQueue(), isEmpty(), enQueue(6), Front(), Rear(), isEmpty()
Output
-1, false, true, true, 6, 6, false
Why
On an empty queue Front returns -1 and deQueue fails. With one item, it is both the front and the rear.

Constraints

  • 1 <= k <= 1000
  • 0 <= value <= 1000
  • At most 3000 calls in total to enQueue, deQueue, Front, Rear, isEmpty and isFull.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (shifting list)O(k) for deQueue, O(1) otherwiseO(k)
Optimal (ring buffer with head and count)O(1) for every operationO(k)

1Brute force (shifting list)

TimeO(k) for deQueue, O(1) otherwiseRemoving the first element moves up to k - 1 elements.
SpaceO(k)At most k elements are stored.

Store the elements in a dynamic list in queue order and refuse to grow past k. Removing from the front shifts every remaining element one step left.

  1. enQueue: if size == k return false, else append and return true.
  2. deQueue: if empty return false, else remove index 0 and return true.
  3. Front / Rear: first / last element, or -1 if empty.
  4. isEmpty / isFull: compare size with 0 and k.
class MyCircularQueue {
    private final List<Integer> items = new ArrayList<>();
    private final int capacity;

    public MyCircularQueue(int k) {
        capacity = k;
    }

    public boolean enQueue(int value) {
        if (items.size() == capacity) return false;
        items.add(value);
        return true;
    }

    public boolean deQueue() {
        if (items.isEmpty()) return false;
        items.remove(0);
        return true;
    }

    public int Front() {
        return items.isEmpty() ? -1 : items.get(0);
    }

    public int Rear() {
        return items.isEmpty() ? -1 : items.get(items.size() - 1);
    }

    public boolean isEmpty() {
        return items.isEmpty();
    }

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

2Optimal (ring buffer with head and count)

TimeO(1) for every operationEach operation is a little index arithmetic and one array access.
SpaceO(k)The array has exactly k slots.

Allocate an array of exactly k slots. Track head (index of the front element) and count (how many elements are stored). Indices wrap with % k, so freed slots at the start are reused without moving anything. Keeping count separately makes full (count == k) and empty (count == 0) unambiguous.

  1. enQueue: if full return false; write the value at (head + count) % k, increment count.
  2. deQueue: if empty return false; move head to (head + 1) % k, decrement count.
  3. Front: data[head]; Rear: data[(head + count - 1) % k]; both -1 when empty.
  4. isEmpty: count == 0; isFull: count == k.
class MyCircularQueue {
    private final int[] data;
    private int head = 0, count = 0;

    public MyCircularQueue(int k) {
        data = new int[k];
    }

    public boolean enQueue(int value) {
        if (isFull()) return false;
        data[(head + count) % data.length] = value;
        count++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % data.length;
        count--;
        return true;
    }

    public int Front() {
        return isEmpty() ? -1 : data[head];
    }

    public int Rear() {
        return isEmpty() ? -1 : data[(head + count - 1) % data.length];
    }

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

    public boolean isFull() {
        return count == data.length;
    }
}

Edge cases to test

  • Capacity 1: the same slot is both front and rear
  • Front/Rear/deQueue on an empty queue
  • enQueue on a full queue must fail and change nothing
  • Many wrap-arounds: filling and emptying the queue repeatedly
  • Telling full and empty apart when the head and tail indices coincide

Hints

Hint 1

A plain list where you remove from the front works, but removing from the front shifts every element.

Hint 2

Use a fixed array of size k with a head index and a count. The tail slot is (head + count) % k, and the rear element is at (head + count - 1) % k.

FAQ

What is the best time complexity for Design Circular Queue?

Optimal (ring buffer with head and count) runs in O(1) for every operation time and O(k) extra space. Each operation is a little index arithmetic and one array access.

Which pattern does Design Circular Queue use?

It is a design data structures problem that uses the queue / circular buffer pattern. Other problems with the same pattern: Design Hit Counter, First Unique Number, Design Snake Game.

Is there a brute force solution for Design Circular Queue?

Yes. Brute force (shifting list) takes O(k) for deQueue, O(1) otherwise time and O(k) space. Store the elements in a dynamic list in queue order and refuse to grow past k.

Which edge cases should I test for Design Circular Queue?

Capacity 1: the same slot is both front and rear; Front/Rear/deQueue on an empty queue; enQueue on a full queue must fail and change nothing; Many wrap-arounds: filling and emptying the queue repeatedly; Telling full and empty apart when the head and tail indices coincide.