⚡Flashcard Drill➔
NeetCode #335LC-622MediumLinked ListNC 250
← Back to All Problems

#335 · #622 · Design Circular Queue(设计循环队列)

📌 Problem Statement & Constraints

Design a circular queue with a fixed capacity k, supporting enQueue(value), deQueue(), Front(), Rear(), isEmpty() and isFull(). Return -1 where the API specifies it for invalid access. Constraints: 1 <= k <= 1000; at most 2000 calls.

💡 Core Algorithmic Approaches

  1. Use a fixed array of size k plus a head index and a count of stored elements.
  2. The insertion position is (head + count) % k; the rear is at (head + count - 1) % k.
  3. Tracking count (rather than a separate tail pointer) removes the classic ambiguity between "empty" and "full" when head equals tail.
  4. Both operations are O(1) with no shifting.

💻 Benchmark Python3 Implementation

class MyCircularQueue:
    def __init__(self, k: int):
        self.q = [0] * k
        self.k = k
        self.head = 0
        self.count = 0                     # avoids the empty/full ambiguity

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.q[(self.head + self.count) % self.k] = value
        self.count += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.head = (self.head + 1) % self.k
        self.count -= 1
        return True

    def Front(self) -> int:
        return -1 if self.isEmpty() else self.q[self.head]

    def Rear(self) -> int:
        return -1 if self.isEmpty() else self.q[(self.head + self.count - 1) % self.k]

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

    def isFull(self) -> bool:
        return self.count == self.k

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) for every operation.
💾 Space Complexity
O(k) for the backing array.

⚠️ Interview Pitfalls & Follow-ups

  • Tracking head and tail without a count: when head == tail it is ambiguous whether the queue is empty or full, and you would need to waste one slot to disambiguate.
  • Shifting elements on deQueue: O(k) per call; the modular head avoids this.
  • Forgetting the modulo on the insertion index: it would run off the end of the array.
  • Returning None from Front/Rear on an empty queue: the API specifies -1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems