Deque (Double-Ended Queue)

What Is a Deque?

A deque (double-ended queue, pronounced "deck") is a linear data structure that supports insertion and removal at both the front and the back in O(1) time. It generalises both a queue (FIFO) and a stack (LIFO) into a single structure.

A queue restricts to:       rear ← enqueue  |  dequeue → front
A stack restricts to:       top  ← push     |  pop → top
A deque supports both:      front ← addFront | removeFront → front
                            back  ← addBack  | removeBack  → back

Deque operations diagram:

  addFront(X) →  ┌────┬────┬────┐  ← addBack(X)
                 │ F  │ ...│ B  │
  removeFront ←  └────┴────┴────┘  → removeBack

  Every operation at BOTH ENDS is O(1).
  Middle access (by index) is O(n) for linked implementations,
  O(1) for array-backed implementations.

Deque vs Queue vs Stack

                  Queue     Stack     Deque
Add to front:     ✗         ✗         ✓  O(1)
Add to back:      ✓  O(1)   ✓  O(1)   ✓  O(1)
Remove from front:✓  O(1)   ✗         ✓  O(1)
Remove from back: ✗         ✓  O(1)   ✓  O(1)
Peek front:       ✓  O(1)   ✗         ✓  O(1)
Peek back:        ✗         ✓  O(1)   ✓  O(1)

A Deque can simulate a Queue (use addBack + removeFront only)
A Deque can simulate a Stack (use addBack + removeBack only)

Complete Deque Implementation

Doubly Linked List Backend

A doubly linked list gives true O(1) at both ends — no amortized cost, no capacity limit.

Output:
Deque (front→back): [10, 20, 30, 40]
peekFirst: 10
peekLast:  40
removeFirst: 10
removeLast:  40
Deque (front→back): [20, 30]

Dry Run: Doubly Linked Deque Operations

head=null, tail=null, size=0

addLast(20):
  node(20), head==null → head=node(20), tail=node(20)
  head → [20] ← tail

addLast(30):
  node(30), tail not null → tail.next=node(30), node(30).prev=tail, tail=node(30)
  head → [20] ↔ [30] ← tail

addFirst(10):
  node(10), head not null → node(10).next=head, head.prev=node(10), head=node(10)
  head → [10] ↔ [20] ↔ [30] ← tail

addLast(40):
  head → [10] ↔ [20] ↔ [30] ↔ [40] ← tail

removeFirst():
  value = head.data = 10
  head != tail → head = head.next = node(20), head.prev = null
  head → [20] ↔ [30] ↔ [40] ← tail   returns 10

removeLast():
  value = tail.data = 40
  head != tail → tail = tail.prev = node(30), tail.next = null
  head → [20] ↔ [30] ← tail   returns 40

Single-element edge case (important!):
  If after removeLast head == tail is reached:
  Check head == tail BEFORE the pointer updates,
  then set both head = null AND tail = null.
  Missing either creates a dangling pointer.

The Sliding Window Maximum Problem

Problem: Given an array and a window size k, find the maximum element in each sliding window of size k.

Brute force: For each window, find the max in O(k). Total: O(n × k).

Monotonic deque: O(n) — each element is added and removed at most once across all windows.

Key insight: Maintain a monotonic decreasing deque of indices. The front is always the index of the current window's maximum. When a new element arrives:

• ›Pop from the back any indices whose elements are ≤ the new element (they can never be the max as long as the new element is in the window)
• ›Pop from the front any index that has fallen outside the window
• ›Push the new index to the back

nums = [1, 3, -1, -3, 5, 3, 6, 7],  k = 3

Window 1: [1, 3, -1]  → max = 3
Window 2: [3, -1, -3] → max = 3
Window 3: [-1, -3, 5] → max = 5
Window 4: [-3, 5, 3]  → max = 5
Window 5: [5, 3, 6]   → max = 6
Window 6: [3, 6, 7]   → max = 7

Output:
[3, 3, 5, 5, 6, 7]
[1, -1]
[9, 8, 7]

Dry Run: Sliding Window Maximum [1, 3, -1, -3, 5, 3, 6, 7], k=3

result=[], dq=[]   (dq stores indices, values shown as nums[idx])

i=0, nums[0]=1:
  No expired front (dq empty).
  No smaller back (dq empty).
  Push 0.  dq=[0]   values=[1]
  i < k-1=2 → no result yet.

i=1, nums[1]=3:
  No expired (0 ≥ 1-3+1=-1).
  nums[dq.back()=0]=1 ≤ 3 → pop 0.  dq=[]
  Push 1.  dq=[1]   values=[3]
  i < 2 → no result yet.

i=2, nums[2]=-1:
  No expired (1 ≥ 0).
  nums[1]=3 > -1 → no pop.
  Push 2.  dq=[1,2]   values=[3,-1]
  i=2 ≥ k-1=2 → result.append(nums[dq[0]]=nums[1]=3)   result=[3]

i=3, nums[3]=-3:
  No expired (1 ≥ 3-3+1=1).
  nums[2]=-1 > -3 → no pop.
  Push 3.  dq=[1,2,3]   values=[3,-1,-3]
  result.append(nums[1]=3)   result=[3,3]

i=4, nums[4]=5:
  Expired? front=1 < 4-3+1=2 → pop 1.  dq=[2,3]
  nums[3]=-3 ≤ 5 → pop 3.  dq=[2]
  nums[2]=-1 ≤ 5 → pop 2.  dq=[]
  Push 4.  dq=[4]   values=[5]
  result.append(nums[4]=5)   result=[3,3,5]

i=5, nums[5]=3:
  No expired (4 ≥ 5-3+1=3).
  nums[4]=5 > 3 → no pop.
  Push 5.  dq=[4,5]   values=[5,3]
  result.append(nums[4]=5)   result=[3,3,5,5]

i=6, nums[6]=6:
  No expired (4 ≥ 6-3+1=4).
  nums[5]=3 ≤ 6 → pop 5.  dq=[4]
  nums[4]=5 ≤ 6 → pop 4.  dq=[]
  Push 6.  dq=[6]
  result.append(nums[6]=6)   result=[3,3,5,5,6]

i=7, nums[7]=7:
  No expired (6 ≥ 7-3+1=5).
  nums[6]=6 ≤ 7 → pop 6.  dq=[]
  Push 7.  dq=[7]
  result.append(nums[7]=7)   result=[3,3,5,5,6,7] ✓

Why store indices, not values?
  The expiry check (i - k + 1) needs to compare with the INDEX.
  Storing only values loses the position — we cannot tell if
  the maximum has slid out of the window.

Why the Monotonic Deque Is O(n)

Each element is processed EXACTLY TWICE:
  1. Pushed to the back of the deque (once per element)
  2. Removed — either:
     a. Popped from the back when a larger element arrives, OR
     b. Popped from the front when it expires from the window

Total operations: 2n pushes/pops = O(n)

The inner while loops may run many iterations for a single i —
but across ALL iterations of the outer loop, the total number
of back-pops is bounded by n (each element popped at most once).

Same amortised argument as the monotonic stack.

Other Deque Problems

First Negative Number in Every Window of Size k

Variant: Instead of the maximum, find the first negative number in each window.

Output:
[-8, -6, -6, -6]
[-1, -1, -7, -15, -15, 0]

Deque as Both Stack and Queue

A deque can directly simulate both data structures — useful when a problem needs to switch between LIFO and FIFO behaviour, or when you want to confirm an implementation is correct.

Output:
Stack pop order: 30 20 10
Queue pop order: 10 20 30
'racecar' palindrome: true
'hello' palindrome:   false

Operation Complexity Summary

Common Mistakes

Forgetting to update prev when removing from the back. In a doubly linked deque, removeLast() moves tail = tail.prev. The new tail's next must be set to null — otherwise the old tail is still reachable from the deque's tail, causing a memory leak (C++) or keeping the node alive (Java/Python GC). Always: tail = tail.prev; tail.next = null.

Not handling the single-element case in remove operations. When head == tail (one element), both removeFirst() and removeLast() remove the same node — both head and tail must be set to null. Missing either creates a dangling pointer for the next enqueue.

Storing values instead of indices in the sliding window deque. The expiry check dq.peekFirst() < i - k + 1 compares against the position in the array. Storing values loses this information — you cannot detect when the maximum has slid out of the window. Always store indices.

Wrong expiry condition: < i - k instead of < i - k + 1. The window [i-k+1, i] has k elements. Index i - k + 1 is the leftmost valid index. An index < i - k + 1 is out of the window. Using < i - k leaves one extra expired index at the front.

Using Array.shift() for deque operations in JavaScript. shift() is O(n) — not O(1). For true O(1) deque operations in JavaScript, use the Map-based doubly-indexed approach or implement with a doubly linked list.

Interview Questions

Q: Why does the sliding window maximum need a deque rather than just a max-heap?

A max-heap gives O(log k) per window update — O(n log k) total. A monotonic deque gives O(1) amortised per element — O(n) total. The heap must handle lazy deletion (marking expired elements) which adds complexity. The deque avoids this because its front-expiry check gives O(1) removal. Additionally, the deque maintains its structure through both front removal (expiry) and back removal (maintaining monotonicity) — two separate ends serving two separate purposes, which is exactly what a deque enables.

Q: Why does the monotonic deque for sliding window maximum store indices rather than values?

To detect window expiry. When the window slides right, elements at positions older than i - k + 1 must be removed from the front. This requires knowing the position (index) of the front element. If only values were stored, we could compare values but could not determine whether the maximum has slid out of the current window.

Q: In a doubly linked deque, how many pointer updates does addFirst require?

Three or four, depending on whether the deque is empty. If empty: two updates (head = newNode; tail = newNode). If non-empty: three updates — newNode.next = head (point forward), head.prev = newNode (point old head backward), head = newNode (update head). Always three assignments for non-empty, two for empty.

FAQs

What is the difference between a deque and a priority queue?

A deque removes elements by position — either the front or the back, in insertion order. A priority queue removes elements by priority — the element with the highest (or lowest) priority is always removed next, regardless of insertion order. A deque is O(1) for both-end operations; a heap-backed priority queue is O(log n) for enqueue and dequeue. Use a deque for sliding windows, palindrome checking, and BFS/DFS. Use a priority queue for greedy algorithms, Dijkstra's algorithm, and k-th largest/smallest problems.

Can a deque be used as both a stack and a queue simultaneously?

Yes. This is the deque's defining property. In the same data structure, you can mix LIFO and FIFO operations: use addLast/removeLast for LIFO (stack) and addLast/removeFirst for FIFO (queue). The underlying linked list or circular array supports both simultaneously. This is why Java's Deque<E> implements both the Queue<E> and the Stack-like interface, and why Python's collections.deque is used for both queue and stack patterns.

What makes the monotonic deque "monotonic"?

The elements stored in the deque are always in monotonically decreasing (or increasing) order by value. Before inserting a new element at the back, all elements smaller (or larger) than it are removed. This ensures the front always holds the maximum (or minimum) among the current deque elements. The monotonic invariant is maintained by the back-pop step.

Quick Quiz

Question 1: In the sliding window maximum with nums=[2,1,3] and k=2, what is the deque content (indices) after processing index 2 (value 3)?

• ›A) [0, 1, 2] — all indices
• ›B) [2] — only index 2
• ›C) [1, 2] — indices of 1 and 3
• ›D) [] — deque is empty

Answer: B) [2]. Processing i=2 (value=3): first remove expired front (index 0 < 2-2+1=1, so pop 0 if present; it was popped at i=1 already). Then pop back while nums[back] ≤ 3 — pop index 1 (value=1), pop... wait: at i=1, index 0 was popped because nums[0]=2 ≤ nums[1]=1? No — nums[0]=2 > 1, so index 0 stays. At i=2: dq=[0,1] after i=1. Expiry: 0 < 2-2+1=1 → pop 0. dq=[1]. Back pop: nums[1]=1 ≤ 3 → pop 1. dq=[]. Push 2. dq=[2]. Result: nums[2]=3.

Question 2: When removing the last element from a doubly linked deque, which pointers must be updated?

• ›A) Only tail = tail.prev
• ›B) tail = tail.prev AND tail.next = null
• ›C) tail = tail.prev AND head.next = null
• ›D) Only tail.data = null

Answer: B) Two updates: advance tail and null out its forward pointer. After tail = tail.prev, the new tail still has next pointing to the removed node. Setting tail.next = null detaches the removed node — otherwise it remains reachable from the deque's tail, preventing garbage collection (Java/Python) or causing a memory leak (C++).

Question 3: The sliding window maximum deque maintains what invariant?

• ›A) Elements are in sorted order from front to back
• ›B) The front always holds the index of the current window's maximum
• ›C) All elements in the deque are within the current window
• ›D) Both B and C

Answer: D) Both B and C. The deque maintains two invariants simultaneously: (1) all stored indices are within the current window [i-k+1, i] — enforced by front expiry; (2) values are in decreasing order from front to back — enforced by back removal. Together, these guarantee that the front index points to the maximum element in the current window.

Question 4: Using addLast only for enqueueing and removeFirst only for dequeueing makes a deque behave as:

• ›A) A stack (LIFO)
• ›B) A queue (FIFO)
• ›C) A priority queue
• ›D) A circular queue

Answer: B) A queue (FIFO). addLast adds to the back; removeFirst removes from the front — elements exit in the order they entered (first in, first out). Using addLast and removeLast instead would give LIFO (stack) behaviour.

Summary

A deque generalises both queue and stack into one structure — O(1) insert and remove at both ends.

Core operations:

• ›addFirst / addLast — O(1); linked: always; array: amortized
• ›removeFirst / removeLast — O(1)
• ›peekFirst / peekLast — O(1)
• ›Single-element edge case: when head == tail, both removeFirst and removeLast must set both head = null AND tail = null

The monotonic deque is the key interview pattern:

• ›Store indices (not values) — position needed for window expiry
• ›Front removal: expiry check dq.peekFirst() < i - k + 1 — O(1)
• ›Back removal: monotonic invariant nums[dq.peekLast()] <= nums[i] — amortized O(1)
• ›Total: O(n) — each element pushed once, popped at most once
• ›Applications: sliding window maximum/minimum, first negative in window, longest subarray with sum ≤ k

Deque used as both:

• ›Queue: addLast + removeFirst
• ›Stack: addFirst/addLast + corresponding removeFirst/removeLast
• ›Palindrome check: removeFirst and removeLast simultaneously, compare values

In the next topic, you will explore Priority Queue — the heap-backed queue that dequeues by priority rather than arrival order, powering Dijkstra's algorithm and k-th largest/smallest problems.