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
- Use a fixed array of size
kplus a head index and a count of stored elements. - The insertion position is
(head + count) % k; the rear is at(head + count - 1) % k. - Tracking
count(rather than a separate tail pointer) removes the classic ambiguity between "empty" and "full" when head equals tail. - 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
headandtailwithout a count: whenhead == tailit 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
NonefromFront/Rearon 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.