Design Circular Queue

LeetCode 622 • Medium • Design

Design a circular queue with enQueue, deQueue, Front, Rear, isEmpty, isFull in O(1).
Fixed-size array. front/rear indices wrap with modulo. One extra slot to distinguish full from empty.
Input: capacity=3, enQueue(1), enQueue(2), enQueue(3), enQueue(4)=false, rear=3, deQueue(), enQueue(4), rear=4

EnQueueO(1)append at rear

DeQueueO(1)advance front

SpaceO(k)k=capacity

Step0/10

front=0 rear=0 Array: [ _, _, _ ]

Ready

Press Play or Step. Circular array with front/rear. (rear+1)%(k+1)==front means full. front==rear means empty.

Speed:

✎ Whiteboard

Size:3

⌨ Type It

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ CIRCULAR QUEUE — FIXED ARRAY ═══

PATTERN ▸ front, rear, (k+1) slots O(1) · O(k)

① ENQUEUE

if isFull(): return False

arr[rear] = value; rear = (rear+1) % (k+1)

② DEQUEUE

if isEmpty(): return False

front = (front+1) % (k+1)

③ FRONT / REAR

return arr[front] or arr[(rear-1+k+1)%(k+1)]

④ FULL / EMPTY

full: (rear+1)%(k+1)==front

empty: front==rear

Verify your solution: