Design Circular Queue

NeetCode: Design Circular Queue · LeetCode: 622. Design Circular Queue · Difficulty: Medium

Design a queue with a fixed capacity k that reuses freed space. Implement MyCircularQueue(k), enQueue(value) (returns true if inserted, false if full), deQueue() (returns true if removed, false if empty), Front() and Rear() (the first and last items, or -1 if empty), isEmpty() and isFull().

Example

Text

MyCircularQueue(3)
enQueue(1) enQueue(2) enQueue(3) -> true true true
enQueue(4)                       -> false   (full)
Rear()                           -> 3
isFull()                         -> true
deQueue()                        -> true
enQueue(4)                       -> true
Rear()                           -> 4

Brute force: an ArrayList with remove(0)

Keep the items in an ArrayList<Integer> and enforce the capacity by hand. add and get(size - 1) are O(1), but deQueue calls remove(0), which shifts every remaining element one slot to the left. The "circular" part is only a length check, and dequeue costs O(k).

The method names follow LeetCode's Java class: enQueue, deQueue, Front, Rear, isEmpty, isFull.

Java

import java.util.ArrayList;
import java.util.List;

class MyCircularQueue {
    private final List<Integer> items;
    private final int cap;

    public MyCircularQueue(int k) {
        items = new ArrayList<>(k);
        cap = k;
    }

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

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        items.remove(0); // O(k): shifts everything left
        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() == cap;
    }
}

public class Main {
    public static void main(String[] args) {
        MyCircularQueue q = new MyCircularQueue(3);
        System.out.println(q.enQueue(1) + " " + q.enQueue(2) + " " + q.enQueue(3));
        System.out.println(q.enQueue(4));
        System.out.println(q.Rear());
        System.out.println(q.isFull());
        System.out.println(q.deQueue());
        System.out.println(q.enQueue(4));
        System.out.println(q.Rear());
        System.out.println("front " + q.Front());

        MyCircularQueue empty = new MyCircularQueue(1);
        System.out.println(empty.Front() + " " + empty.Rear() + " " + empty.deQueue());
    }
}

Output

true true true
false
3
true
true
true
4
front 2
-1 -1 false

items.remove(0) calls remove(int index) because 0 is an int. With an Integer argument the call would be remove(Object) and would remove by value.

Time: enQueue, Front, Rear, isEmpty, isFull are O(1); deQueue is O(k). Space: O(k).

Optimal: a fixed ring buffer

Allocate an int[] of exactly k slots once. Track head (index of the front item) and size (how many items are stored). All other operations are arithmetic modulo the capacity:

the rear item lives at (head + size - 1) % k,
a new item goes to (head + size) % k,
dequeue moves head = (head + 1) % k and decrements size; nothing is shifted or erased.

Storing size instead of a separate tail index avoids the ambiguity where head == tail could mean either empty or full. The empty check comes before the size - 1 arithmetic, so the index is never negative. Java's % keeps the sign of the dividend, so a negative index would stay negative, but here head + size - 1 is at least 0 when the queue is not empty. A capacity of 0 is always full, so no modulo by zero occurs. LeetCode guarantees k >= 1.

Java

class MyCircularQueue {
    private final int[] buf;
    private int head;
    private int size;

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

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

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

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

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

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

    public boolean isFull() {
        return size == buf.length;
    }
}

public class Main {
    public static void main(String[] args) {
        MyCircularQueue q = new MyCircularQueue(3);
        System.out.println(q.enQueue(1) + " " + q.enQueue(2) + " " + q.enQueue(3));
        System.out.println(q.enQueue(4));
        System.out.println(q.Rear());
        System.out.println(q.isFull());
        System.out.println(q.deQueue());
        System.out.println(q.enQueue(4));
        System.out.println(q.Rear());
        System.out.println("front " + q.Front());

        MyCircularQueue empty = new MyCircularQueue(1);
        System.out.println(empty.Front() + " " + empty.Rear() + " " + empty.deQueue());
    }
}

Output

true true true
false
3
true
true
true
4
front 2
-1 -1 false

Time: every operation is O(1). Space: O(k), allocated once.