Back to Study Material Data Structures and Algorithms

Deque

A deque, pronounced deck, is short for double-ended queue. It generalizes both the stack and the queue by allowing insertions and deletions at both the fro...

Deque

Double-Ended Queue: Insertions and Deletions at Both Ends

A deque, pronounced deck, is short for double-ended queue. It generalizes both the stack and the queue by allowing insertions and deletions at both the front and the rear. A stack is a deque that only uses rear insertions and rear deletions. A queue is a deque that uses rear insertions and front deletions. The deque abstracts both into a single data structure.

The four fundamental operations are addFront, addRear, removeFront, and removeRear, each running in O(1) time. PeekFront and peekRear read without removing and are also O(1). isEmpty and size are O(1) if a count is maintained.

Implementing a deque efficiently requires access to both ends in O(1) time. A doubly linked list achieves this naturally: each node has both a next and a previous pointer. addFront creates a new node and links it before the current head. addRear creates a new node and links it after the current tail. removeFront reads and unlinks the head node, advancing the head pointer. removeRear reads and unlinks the tail node, retreating the tail pointer. All four operations touch only the boundary nodes and do not traverse the interior.

A circular array can also implement a deque by maintaining both a front and rear index with modulo wraparound. addRear increments rear with modulo. addFront decrements front with modulo (in languages using modulo with positive results for negative numbers, use (front - 1 + capacity) modulo capacity to avoid negative indices). The circular array implementation has better cache locality than a doubly linked list because elements reside in contiguous memory.

Time complexity for all four modification operations is O(1). Space complexity is O(n).

Worked example: start with empty deque. addRear(3): deque [3]. addFront(1): deque [1, 3]. addRear(5): deque [1, 3, 5]. removeFront: returns 1, deque [3, 5]. removeRear: returns 5, deque [3]. peekFront: returns 3, deque unchanged.

Interview tip: when a problem requires a sliding window maximum or minimum, recognize that it likely needs a deque to efficiently maintain the best candidate while both adding new elements at the rear and expiring old elements at the front. State this connection before coding.

Sliding Window Maximum Using a Deque

The sliding window maximum problem asks: given an array of integers and a window size k, for each position of the window as it slides from left to right, find the maximum element within the window. A brute-force approach scans every element in each window position, giving O(n times k) time. A deque-based solution achieves O(n) time.

The deque stores indices of array elements and maintains a monotonic decreasing order of values from front to rear. This means the front of the deque always holds the index of the current window's maximum element.

Process each element from left to right. First, remove from the front of the deque any index that is outside the current window (index less than i minus k plus one). Then, remove from the rear of the deque any index whose corresponding value is less than or equal to the current element, because those elements can never be the maximum for the current or any future window while the current element exists. Add the current index to the rear. After processing the first k elements, the front of the deque is the maximum for the current window. Append it to the results.

Each element is added to the deque once and removed at most once, giving O(n) total operations and O(n) time complexity. The deque holds at most k elements at any time, so space complexity is O(k).

Worked example: array [1, 3, -1, -3, 5, 3, 6, 7], k = 3. Windows and maxima: [1,3,-1] max 3, [3,-1,-3] max 3, [-1,-3,5] max 5, [-3,5,3] max 5, [5,3,6] max 6, [3,6,7] max 7. Result: [3, 3, 5, 5, 6, 7]. Tracing the deque: at index 1 (value 3), remove index 0 (value 1 < 3) from rear, push 1. Front is 1. Continue similarly throughout.

Interview tip: this problem is a benchmark for deque pattern recognition. If you see a problem mentioning a sliding window combined with maximum or minimum, state immediately that a monotonic deque gives O(n) time, then explain the invariant the deque maintains before writing the loop.

Deque Applications in Palindrome Checking and Undo History

Beyond sliding windows, deques appear in problems that require symmetric access to a sequence from both ends simultaneously. Palindrome checking and bounded undo history with both undo and redo at arbitrary ends are two practical examples.

A palindrome is a string that reads the same forward and backward. The classic approach reverses the string and compares, or uses two pointers. A deque provides a third approach that is instructive for understanding deque semantics. Load all characters into a deque. Then repeatedly removeFront and removeRear and compare the two characters. If they ever differ, the string is not a palindrome. If the deque becomes empty or holds exactly one character (for odd-length strings), it is a palindrome. This runs in O(n) time and O(n) space for the deque, which is not better than the two-pointer approach in complexity but demonstrates deque usage clearly.

A bounded history system maintains both forward and backward navigation of at most m states. When the user performs an action, the new state is added to the rear and the front is removed if the history exceeds m states, ensuring constant memory. When the user navigates backward, states are moved from the history rear to a future deque at the front. When navigating forward, states move from the future deque back to the history. This is a generalization of the browser back-forward model to a fixed-capacity bounded history.

Deques also implement the steal operation in work-stealing schedulers. Each thread maintains a deque of tasks. The owner thread adds and removes tasks from the rear (LIFO for data locality). Idle threads steal tasks from the front of other threads' deques (FIFO to minimize contention). Lock-free deques make this coordination efficient on modern multi-core processors.

Worked example for palindrome check with deque: string racecar. Load [r, a, c, e, c, a, r]. RemoveFront r, removeRear r, match. RemoveFront a, removeRear a, match. RemoveFront c, removeRear c, match. One element e remains, deque has one item, it is a palindrome.

Interview tip: for palindrome problems, explain the two-pointer approach as your primary solution since it uses O(1) space, then mention the deque approach as an alternative that generalizes naturally to streams where you cannot index into the data directly.