Design Circular Deque
Understanding the Problem
We need to build a double-ended queue with a fixed maximum capacity, and it must wrap around, meaning the underlying storage behaves like a ring. Unlike a regular queue where you only add at one end and remove from the other, a deque lets you insert and delete from both the front and the rear.
The "circular" part is the real design challenge. When the front pointer reaches the beginning of the array, it should wrap to the end. When the rear pointer reaches the end, it should wrap to the beginning. This way, we never waste space from previous deletions, as long as the deque is not full.
Modular arithmetic handles the wrap-around. (index + 1) % capacity moves a pointer forward and (index - 1 + capacity) % capacity moves it backward, and neither expression ever goes out of bounds.
Key Constraints:
1 <= k <= 1000→ The deque capacity is small. Any reasonable approach works performance-wise.0 <= value <= 1000→ Values are non-negative integers, so returning -1 as a sentinel for "empty" is safe and unambiguous.- At most
2000calls → Small enough that even O(n) shifting would pass, but the point of the problem is to support every operation in O(1), and both approaches below do.
Approach 1: Circular Array
Intuition
A fixed-size array with two pointers, front and rear, implements the deque directly. When a pointer moves past the end of the array, the modulo operator wraps it back to the beginning. When it moves before the beginning, it wraps to the end.
The convention matters: front points to the current front element, and rear points to the position after the last element (the next free slot at the back). A separate size counter tells us whether the deque is empty or full.
The size counter is not optional bookkeeping. With this convention, rear sits exactly size steps ahead of front (mod capacity), so front == rear occurs in two different situations: when the deque is empty and when the pointers have wrapped all the way around to meet at full capacity. The pointers alone cannot distinguish those cases. Tracking size resolves the ambiguity.
A size counter is not the only way to break the front == rear ambiguity. The classic alternative allocates k + 1 slots and treats the deque as full when (rear + 1) % (k + 1) == front, deliberately wasting one slot so that empty (front == rear) and full never look the same. It works, but every modulus in the code becomes k + 1 instead of k, and the wasted slot buys nothing that a size counter does not provide. The size counter is the simpler convention.
Algorithm
- Allocate an array of size
kand initializefront = 0,rear = 0,size = 0. - insertFront: If full, return false. Otherwise, move
frontbackward by one (wrapping with modulo), place the value atfront, increment size. - insertLast: If full, return false. Otherwise, place the value at
rear, then moverearforward by one (wrapping), increment size. - deleteFront: If empty, return false. Otherwise, move
frontforward by one (wrapping), decrement size. - deleteLast: If empty, return false. Otherwise, move
rearbackward by one (wrapping), decrement size. - getFront/getRear: If empty, return -1. Otherwise, return the element at
frontor at(rear - 1 + capacity) % capacity. - isEmpty/isFull: Check whether size is 0 or size equals capacity.
Example Walkthrough
Code
- Time Complexity: O(1) per operation. Every method does a constant number of arithmetic operations and array accesses, with no loops and no element shifting.
- Space Complexity: O(k). We allocate an array of exactly k elements, where k is the requested capacity.
The circular array packs everything into one allocation, but it asks you to keep three separate (x - 1 + capacity) % capacity expressions consistent. A doubly linked list reaches the same O(1) bounds with no index arithmetic at all.
Approach 2: Doubly Linked List
Intuition
A doubly linked list stores each element in a node with prev and next pointers. Inserting at the front adds a node before the head, inserting at the back adds a node after the tail, and deleting from either end relinks two pointers. A size counter enforces the capacity limit, since the list itself has no built-in bound.
The trade against the circular array: each element costs a heap allocation plus two pointers of overhead, and the nodes are scattered in memory instead of packed in one cache-friendly block. In exchange, there is no modular arithmetic to get wrong, and the empty-versus-full ambiguity from Approach 1 disappears entirely. An empty deque is head == null, a full one is size == capacity, and the two conditions can never be confused.
Algorithm
- Create a
Nodeclass withval,prev, andnextfields. - Initialize
head = null,tail = null,size = 0,capacity = k. - insertFront: If full, return false. Create a new node. If the deque is empty, set both head and tail to this node. Otherwise, link it before the current head and update head. Increment size.
- insertLast: If full, return false. Create a new node. If the deque is empty, set both head and tail to this node. Otherwise, link it after the current tail and update tail. Increment size.
- deleteFront: If empty, return false. If size is 1, set both head and tail to null. Otherwise, move head to
head.nextand set the new head'sprevto null. Decrement size. - deleteLast: If empty, return false. If size is 1, set both head and tail to null. Otherwise, move tail to
tail.prevand set the new tail'snextto null. Decrement size. - getFront/getRear: Return
head.valortail.val, or -1 if empty.
Example Walkthrough
Code
- Time Complexity: O(1) per operation. Each method does a constant number of pointer operations. No traversal of the list is needed since we always operate at the head or tail.
- Space Complexity: O(k). At most k nodes are stored in the list, each with a constant amount of data (value + two pointers).