Skip to main content
CodePeetCodePeet
CodePeet 250

Design Circular Queue

MEDIUMProblemSolveExternal Links

Description

Design and implement a circular queue data structure. A circular queue (also known as a "Ring Buffer") is a variation of a standard queue where the last position wraps around and connects back to the first position, forming a circle.

In a regular queue backed by an array, once elements are dequeued from the front, those positions become permanently wasted — even if there is free space at the beginning of the array, new elements can only be added at the end. A circular queue solves this by reusing those vacated positions through modular arithmetic.

You need to implement the MyCircularQueue class with the following operations:

  • MyCircularQueue(k) — Initialize the queue with a maximum capacity of k elements.
  • enQueue(value) — Insert an element at the rear of the queue. Return true if successful, false if the queue is full.
  • deQueue() — Remove the element from the front of the queue. Return true if successful, false if the queue is empty.
  • Front() — Retrieve the front element. Return -1 if the queue is empty.
  • Rear() — Retrieve the rear element. Return -1 if the queue is empty.
  • isEmpty() — Return true if the queue contains no elements.
  • isFull() — Return true if the queue has reached its maximum capacity.

You must implement this without using any built-in queue data structure.

Examples

Example 1

Input:

["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]

Output: [null, true, true, true, false, 3, true, true, true, 4]

Explanation:

  • MyCircularQueue(3) — Create a queue with capacity 3.
  • enQueue(1) — Insert 1. Queue becomes [1]. Return true.
  • enQueue(2) — Insert 2. Queue becomes [1, 2]. Return true.
  • enQueue(3) — Insert 3. Queue becomes [1, 2, 3]. Return true.
  • enQueue(4) — Queue is already full (3 elements = capacity). Return false.
  • Rear() — The last element is 3. Return 3.
  • isFull() — The queue has 3 elements and capacity is 3. Return true.
  • deQueue() — Remove front element 1. Queue becomes [2, 3]. Return true.
  • enQueue(4) — Now there is room. Insert 4. Queue becomes [2, 3, 4]. Return true. Notice how the vacated slot from deQueue is reused.
  • Rear() — The last element is 4. Return 4.

Example 2

Input:

["MyCircularQueue", "enQueue", "deQueue", "enQueue", "Front", "isEmpty"]
[[2], [5], [], [7], [], []]

Output: [null, true, true, true, 7, false]

Explanation:

  • MyCircularQueue(2) — Create a queue with capacity 2.
  • enQueue(5) — Insert 5. Queue becomes [5]. Return true.
  • deQueue() — Remove front element 5. Queue becomes []. Return true.
  • enQueue(7) — Insert 7. Queue becomes [7]. Return true. The element 7 is placed at a position that wraps around in the internal array.
  • Front() — The front element is 7. Return 7.
  • isEmpty() — Queue has 1 element. Return false.

Constraints

  • 1 ≤ k ≤ 1000
  • 0 ≤ value ≤ 1000
  • At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull

Editorial

Brute Force

Intuition

The simplest way to implement a queue is to use a dynamic list (like Python's list or Java's ArrayList). When we enqueue, we append to the end. When we dequeue, we remove from the front and shift all remaining elements one position to the left.

Imagine a line of people at a ticket counter. When the person at the front is served and leaves, everyone behind them physically takes one step forward to fill the gap. This is exactly what happens in the brute force approach — every dequeue triggers a shift of all remaining elements.

We also track the current number of elements (count) to enforce the capacity limit. If count equals the capacity k, enqueue operations are rejected.

Step-by-Step Explanation

Let's trace through a queue with capacity k = 3:

Step 1: Initialize an empty list and set count = 0, capacity = 3.

  • data = [], count = 0

Step 2: enQueue(1) — count (0) < capacity (3), so append 1.

  • data = [1], count = 1. Return true.

Step 3: enQueue(2) — count (1) < capacity (3), so append 2.

  • data = [1, 2], count = 2. Return true.

Step 4: enQueue(3) — count (2) < capacity (3), so append 3.

  • data = [1, 2, 3], count = 3. Return true.

Step 5: enQueue(4) — count (3) == capacity (3). Queue is full. Return false.

Step 6: deQueue() — count > 0, so remove data[0] (which is 1). Shift remaining elements left.

  • data = [2, 3], count = 2. Return true.
  • This shift operation costs O(n) because every remaining element moves one position.

Step 7: enQueue(4) — count (2) < capacity (3), so append 4.

  • data = [2, 3, 4], count = 3. Return true.

Step 8: Rear() — Return the last element: data[count - 1] = data[2] = 4.

Brute Force Queue — Shifting on Dequeue — Watch how every dequeue forces all remaining elements to shift left by one position, which is costly for large queues.

Algorithm

  1. Initialize an empty list data and set count = 0, capacity = k.
  2. enQueue(value): If count == capacity, return false. Otherwise, append value to data and increment count. Return true.
  3. deQueue(): If count == 0, return false. Otherwise, remove the element at index 0 (which shifts all subsequent elements left by one), decrement count. Return true.
  4. Front(): If count == 0, return -1. Otherwise, return data[0].
  5. Rear(): If count == 0, return -1. Otherwise, return data[count - 1].
  6. isEmpty(): Return count == 0.
  7. isFull(): Return count == capacity.

Code

class MyCircularQueue {
private:
    vector<int> data;
    int capacity;
    int count;

public:
    MyCircularQueue(int k) {
        capacity = k;
        count = 0;
    }

    bool enQueue(int value) {
        if (count == capacity) return false;
        data.push_back(value);
        count++;
        return true;
    }

    bool deQueue() {
        if (count == 0) return false;
        // Erase from front causes O(n) shift
        data.erase(data.begin());
        count--;
        return true;
    }

    int Front() {
        if (count == 0) return -1;
        return data[0];
    }

    int Rear() {
        if (count == 0) return -1;
        return data[count - 1];
    }

    bool isEmpty() {
        return count == 0;
    }

    bool isFull() {
        return count == capacity;
    }
};
class MyCircularQueue:
    def __init__(self, k: int):
        self.data = []
        self.capacity = k
        self.count = 0

    def enQueue(self, value: int) -> bool:
        if self.count == self.capacity:
            return False
        self.data.append(value)
        self.count += 1
        return True

    def deQueue(self) -> bool:
        if self.count == 0:
            return False
        # Pop from front causes O(n) shift
        self.data.pop(0)
        self.count -= 1
        return True

    def Front(self) -> int:
        if self.count == 0:
            return -1
        return self.data[0]

    def Rear(self) -> int:
        if self.count == 0:
            return -1
        return self.data[self.count - 1]

    def isEmpty(self) -> bool:
        return self.count == 0

    def isFull(self) -> bool:
        return self.count == self.capacity
import java.util.ArrayList;
import java.util.List;

class MyCircularQueue {
    private List<Integer> data;
    private int capacity;
    private int count;

    public MyCircularQueue(int k) {
        data = new ArrayList<>();
        capacity = k;
        count = 0;
    }

    public boolean enQueue(int value) {
        if (count == capacity) return false;
        data.add(value);
        count++;
        return true;
    }

    public boolean deQueue() {
        if (count == 0) return false;
        // Remove from front causes O(n) shift
        data.remove(0);
        count--;
        return true;
    }

    public int Front() {
        if (count == 0) return -1;
        return data.get(0);
    }

    public int Rear() {
        if (count == 0) return -1;
        return data.get(count - 1);
    }

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

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

Complexity Analysis

Time Complexity:

  • enQueue: O(1) — appending to the end of a list is constant time.
  • deQueue: O(n) — removing from the front requires shifting all n-1 remaining elements one position to the left. This is the bottleneck.
  • Front, Rear, isEmpty, isFull: O(1) — direct index access or comparison.

With up to 3000 calls and each dequeue potentially shifting up to 1000 elements, the worst case is around 3 × 10⁶ operations — acceptable for these constraints but fundamentally inefficient.

Space Complexity: O(k)

We store at most k elements in the list. No additional data structures are used beyond the list itself.

Why This Approach Is Not Efficient

The brute force approach has an O(n) dequeue operation because removing the front element from an array or list forces every subsequent element to shift left by one position. For a queue with 1000 elements, every single dequeue moves 999 elements.

The core problem is that we treat the front of the queue as always being at index 0. When the front element leaves, we physically move everything to maintain this invariant. But what if we simply remembered where the front is instead of forcing it to always be at position 0?

This is the key insight: instead of moving data to match a fixed front position, we move the front pointer to match the data. If the front element was at index 0 and gets removed, the new front is simply at index 1 — no shifting needed. And when the rear reaches the end of the array, it wraps around to the beginning using modular arithmetic: rear = (front + count) % capacity. This "wrap-around" behavior is what makes it a circular queue, and it makes every operation O(1).

Optimal Approach - Circular Array with Modular Arithmetic

Intuition

Picture a circular track with k parking spots numbered 0 through k-1. Cars enter from one spot (the rear) and leave from another (the front). When a car leaves the front spot, we do not ask all other cars to move up — we simply update our sign to point to the next occupied spot. When the rear pointer reaches spot k-1 and needs to go further, it wraps around to spot 0 (if that spot is now free because a car already left from there).

We maintain three pieces of information:

  1. front — the index of the front element in the fixed-size array.
  2. count (or size) — how many elements are currently in the queue.
  3. arr — a fixed-size array of length k.

The rear index is computed on the fly as (front + count) % k rather than stored separately. This elegant formula handles the wrap-around automatically:

  • If front = 2, count = 3, k = 5, then rear = (2 + 3) % 5 = 0 — the next insertion goes to index 0, wrapping around.
  • The modulo operator % is the mathematical tool that creates the circular behavior.

With this design, both enqueue and dequeue become O(1): enqueue places an element at the computed rear index and increments count; dequeue advances front by one (with wrap-around) and decrements count. No elements are ever moved.

Step-by-Step Explanation

Let's trace through the same operations with a circular queue of capacity k = 3. Our array has indices [0, 1, 2].

Step 1: Initialize: arr = [_, _, _], front = 0, count = 0.

Step 2: enQueue(1): count (0) < k (3). Compute rear = (0 + 0) % 3 = 0. Place 1 at arr[0]. Increment count to 1.

  • arr = [1, _, _], front = 0, count = 1.

Step 3: enQueue(2): count (1) < k (3). Compute rear = (0 + 1) % 3 = 1. Place 2 at arr[1]. Count becomes 2.

  • arr = [1, 2, _], front = 0, count = 2.

Step 4: enQueue(3): count (2) < k (3). Compute rear = (0 + 2) % 3 = 2. Place 3 at arr[2]. Count becomes 3.

  • arr = [1, 2, 3], front = 0, count = 3.

Step 5: enQueue(4): count (3) == k (3). Queue is full. Return false.

Step 6: deQueue(): count (3) > 0. The front element is arr[0] = 1. Advance front = (0 + 1) % 3 = 1. Decrement count to 2.

  • arr = [_, 2, 3], front = 1, count = 2. (Index 0 is now logically empty.)

Step 7: enQueue(4): count (2) < k (3). Compute rear = (1 + 2) % 3 = 0. Place 4 at arr[0] — the slot freed by the earlier dequeue! Count becomes 3.

  • arr = [4, 2, 3], front = 1, count = 3. The wrap-around in action!

Step 8: Rear(): Compute rear index = (front + count - 1) % k = (1 + 3 - 1) % 3 = 0. Return arr[0] = 4.

Circular Queue — Modular Arithmetic Wrap-Around — Watch how front and rear pointers move through the fixed-size array using modular arithmetic, wrapping around without ever shifting elements.

Algorithm

  1. Initialize: Allocate a fixed-size array of length k. Set front = 0 and count = 0.
  2. enQueue(value):
    • If count == k, return false (queue is full).
    • Compute rear = (front + count) % k.
    • Set arr[rear] = value.
    • Increment count.
    • Return true.
  3. deQueue():
    • If count == 0, return false (queue is empty).
    • Advance front = (front + 1) % k (wrap-around).
    • Decrement count.
    • Return true.
  4. Front():
    • If count == 0, return -1.
    • Return arr[front].
  5. Rear():
    • If count == 0, return -1.
    • Compute rear_index = (front + count - 1) % k.
    • Return arr[rear_index].
  6. isEmpty(): Return count == 0.
  7. isFull(): Return count == k.

Code

class MyCircularQueue {
private:
    vector<int> arr;
    int front;
    int count;
    int capacity;

public:
    MyCircularQueue(int k) {
        arr.resize(k);
        capacity = k;
        front = 0;
        count = 0;
    }

    bool enQueue(int value) {
        if (count == capacity) return false;
        int rear = (front + count) % capacity;
        arr[rear] = value;
        count++;
        return true;
    }

    bool deQueue() {
        if (count == 0) return false;
        front = (front + 1) % capacity;
        count--;
        return true;
    }

    int Front() {
        if (count == 0) return -1;
        return arr[front];
    }

    int Rear() {
        if (count == 0) return -1;
        int rearIndex = (front + count - 1) % capacity;
        return arr[rearIndex];
    }

    bool isEmpty() {
        return count == 0;
    }

    bool isFull() {
        return count == capacity;
    }
};
class MyCircularQueue:
    def __init__(self, k: int):
        self.arr = [0] * k
        self.capacity = k
        self.front = 0
        self.count = 0

    def enQueue(self, value: int) -> bool:
        if self.count == self.capacity:
            return False
        rear = (self.front + self.count) % self.capacity
        self.arr[rear] = value
        self.count += 1
        return True

    def deQueue(self) -> bool:
        if self.count == 0:
            return False
        self.front = (self.front + 1) % self.capacity
        self.count -= 1
        return True

    def Front(self) -> int:
        if self.count == 0:
            return -1
        return self.arr[self.front]

    def Rear(self) -> int:
        if self.count == 0:
            return -1
        rear_index = (self.front + self.count - 1) % self.capacity
        return self.arr[rear_index]

    def isEmpty(self) -> bool:
        return self.count == 0

    def isFull(self) -> bool:
        return self.count == self.capacity
class MyCircularQueue {
    private int[] arr;
    private int front;
    private int count;
    private int capacity;

    public MyCircularQueue(int k) {
        arr = new int[k];
        capacity = k;
        front = 0;
        count = 0;
    }

    public boolean enQueue(int value) {
        if (count == capacity) return false;
        int rear = (front + count) % capacity;
        arr[rear] = value;
        count++;
        return true;
    }

    public boolean deQueue() {
        if (count == 0) return false;
        front = (front + 1) % capacity;
        count--;
        return true;
    }

    public int Front() {
        if (count == 0) return -1;
        return arr[front];
    }

    public int Rear() {
        if (count == 0) return -1;
        int rearIndex = (front + count - 1) % capacity;
        return arr[rearIndex];
    }

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

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

Complexity Analysis

Time Complexity: O(1) for ALL operations

  • enQueue: One modular arithmetic computation, one array write, one increment. All O(1).
  • deQueue: One modular arithmetic computation, one decrement. O(1). No element shifting is required because we simply advance the front pointer.
  • Front, Rear: One modular arithmetic computation and one array read. O(1).
  • isEmpty, isFull: One comparison. O(1).

Every single operation is constant time regardless of how many elements are in the queue. This is a significant improvement over the brute force O(n) dequeue.

Space Complexity: O(k)

We allocate a fixed-size array of length k. The three integer variables (front, count, capacity) use O(1) additional space. Total space is O(k) where k is the queue capacity.