Design Circular Queue

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Implement a queue with a fixed capacity k on top of an array, reusing slots as items leave. Support enQueue(value) (false if full), deQueue() (false if empty), Front() and Rear() (−1 if empty), isEmpty() and isFull(), all in O(1) time without moving elements.

    The ring buffer behind this question is everywhere in real systems: network card queues, log buffers, audio streams, producer/consumer pipelines. That is why it is often followed by "now make it thread-safe". Original problem: LeetCode 622.

    Example

    With capacity 3, the fourth value is refused until one leaves; then 4 is written into the freed slot 0.
    With capacity 3, the fourth value is refused until one leaves; then 4 is written into the freed slot 0.
    MyCircularQueue(3)
    enQueue(1) -> true; enQueue(2) -> true; enQueue(3) -> true
    enQueue(4) -> false       # full
    Rear()     -> 3
    deQueue()  -> true        # removes 1
    enQueue(4) -> true        # goes into slot 0
    Front()    -> 2
    Rear()     -> 4

    Constraints (assumed)

    • 1 ≤ k ≤ 1,000; up to 3,000 calls; values are non-negative (so −1 can mean "empty").

    What this question tests

    • Modular arithmetic for wrapping indices.
    • Choosing a state (head + count, or head + tail) that tells "empty" and "full" apart.
    • Clean API design and, as a follow-up, thread safety.

    Questions to ask first

    1. What should operations return when they fail? (Here: false, or −1 for Front/Rear on empty.)
    2. Can I use a built-in deque? (No; the point is the array.)
    3. Will several threads use it? (Here: no; the blocking version is a follow-up.)
    4. Should a full queue overwrite the oldest item instead? (Here: no. That is the "ring buffer for logs" variant.)