Linear
Deque Double-Ended Queue
O(1) add and remove at both front AND back. A Deque can be a stack (LIFO), a queue (FIFO), or both at once — and it's the backbone of monotonic deque problems like Sliding Window Maximum.
Foundations · Array · Linked List · Stack · Queue · Deque · HashMap · Binary Tree · BST · Heap · Trie · Graph · Sorting
01
Section One · Foundation
What is a Deque?
A deque (pronounced "deck," short for double-ended queue) supports insertion and removal at both the front and back in O(1). A stack only allows operations at one end; a queue allows add-at-back and remove-from-front. A deque does all four: addFirst, addLast, removeFirst, removeLast — all in constant time. In Java, ArrayDeque is the recommended implementation: it's faster than LinkedList (contiguous memory = better cache performance), faster than Stack (no synchronisation overhead), and implements both the Deque and Queue interfaces. In interviews, a deque appears in three contexts: (1) as a drop-in replacement for both Stack and Queue (use ArrayDeque for everything), (2) as the foundation for the monotonic deque pattern (Sliding Window Maximum, LC 239), and (3) in problems that need efficient front+back access (palindrome checking on a character deque, BFS with 0/1 edge weights using 0-1 BFS).
Analogy: A train where passengers can board and exit from both the front and rear doors. A regular queue only lets people join at the back and leave from the front. A stack only uses one door. A deque opens both doors for both operations — maximum flexibility, same O(1) speed.
02
Section Two · Mental Model
How It Thinks
ArrayDeque uses a circular (ring) buffer — head and tail wrap around
▶
No shifting needed for front insertions/removals — just move the head pointer backward (wrapping). This is why addFirst is O(1), unlike ArrayList which shifts everything
The deque doubles its backing array when full (amortised O(1) resize)
▶
Same growth strategy as ArrayList. Most operations are O(1); occasional resize is O(n) but amortised over n insertions = O(1) per operation
A deque can be restricted to behave as a stack (one end) or queue (two ends, one direction)
▶
Java's official recommendation: use ArrayDeque instead of Stack class (legacy, synchronized) and instead of LinkedList as Queue (cache-unfriendly, extra allocation per node)
Monotonic deque maintains elements in sorted order from front to back
▶
Front always holds the current answer (max or min). Back is where new elements enter, popping anything they dominate. Each element enters and exits once → O(n) total for the entire sweep
ArrayDeque does NOT allow null elements
▶
It uses null internally as the "empty slot" sentinel. If you need to store nulls, use LinkedList instead — but this almost never comes up in interviews
ArrayDeque is NOT thread-safe
▶
No synchronisation overhead = faster than Stack and Vector. For concurrent access, use ConcurrentLinkedDeque — but interviews don't test this
03
Section Three · Operations
Core Operations
| Operation | Throws Exception | Returns Special Value | Time | Description |
|---|---|---|---|---|
| Insert front | addFirst(e) | offerFirst(e) | O(1)* | Add element at front |
| Insert back | addLast(e) | offerLast(e) | O(1)* | Add element at back |
| Remove front | removeFirst() | pollFirst() | O(1) | Remove and return front element |
| Remove back | removeLast() | pollLast() | O(1) | Remove and return back element |
| Peek front | getFirst() | peekFirst() | O(1) | View front without removing |
| Peek back | getLast() | peekLast() | O(1) | View back without removing |
| Size | size() | O(1) | Number of elements | |
| Search | contains(o) | O(n) | Linear scan — deque is not indexed | |
* Amortised O(1) — occasional O(n) resize when backing array is full.
Circular buffer — head and tail wrap around the array
04
Section Four · Implementations
ArrayDeque vs LinkedList
ArrayDeque
Circular Array — ✓ Preferred
- Contiguous memory → cache-friendly
- No per-node Object allocation
- ~3× faster than LinkedList in benchmarks
- Amortised O(1) — occasional resize
- Does NOT allow null elements
- NOT thread-safe (no sync overhead)
LinkedList
Doubly-Linked Nodes
- True O(1) — no resize ever
- Each node = separate heap allocation
- Poor cache locality — pointer chasing
- 16+ bytes overhead per node
- Allows null elements
- Also implements List interface
Interview rule:
- Always use
ArrayDequeunless the problem specifically requires null storage or iterator-based middle removal. - The Java docs themselves state: "This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue."
05
Section Five · Stack & Queue
Deque as Stack and Queue
In interviews, use ArrayDeque for both stack and queue operations. Map the abstract operations to deque methods:
| Behaviour | Abstract Op | Deque Method | End Used |
|---|---|---|---|
| Stack (LIFO) | push | push(e) / addFirst(e) | Front |
| pop | pop() / removeFirst() | Front | |
| peek | peek() / peekFirst() | Front | |
| Queue (FIFO) | enqueue | offer(e) / addLast(e) | Back |
| dequeue | poll() / removeFirst() | Front | |
| peek | peek() / peekFirst() | Front |
Java — ArrayDeque as Stack and Queue
// ── Stack (LIFO) ────────────────────────── Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // addFirst(1)
stack.push(2); // addFirst(2) → [2, 1]
stack.pop(); // removeFirst() → 2
stack.peek(); // peekFirst() → 1 // ── Queue (FIFO) ───────────────────────── Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); // addLast(1)
queue.offer(2); // addLast(2) → [1, 2]
queue.poll(); // removeFirst() → 1
queue.peek(); // peekFirst() → 2
Common Mistake: Using Java's
Stack class. It extends Vector, which means every operation is synchronized — unnecessary overhead for single-threaded interview code. The Java docs explicitly recommend ArrayDeque over Stack. Use Deque<Integer> stack = new ArrayDeque<>();.
06
Section Six · Monotonic Deque
Monotonic Deque — Sliding Window Maximum
The monotonic deque is the killer application of a deque. It maintains indices in decreasing order of their values (for maximum queries). The front always holds the index of the current window's maximum. When a new element enters, pop all back elements that are smaller — they can never be the answer because the new element is both larger AND newer. When the front element falls outside the window, pop it from the front. Each element enters and exits the deque at most once → O(n) total.
Sliding Window Maximum (LC 239)
Given an array and window size k, return the maximum value in each window position.
Pseudocode
function maxSlidingWindow(arr, k):
deque = [] // stores indices, not values
result = []
for i = 0 to arr.length - 1:
// ① Remove front if outside window if deque not empty and deque.front < i - k + 1:
deque.removeFirst()
// ② Remove back elements smaller than arr[i] while deque not empty and arr[deque.back] < arr[i]:
deque.removeLast()
// ③ Add current index
deque.addLast(i)
// ④ Record answer once window is full if i >= k - 1:
result.add(arr[deque.front]) // front = index of max return result // O(n) total
Monotonic deque for [1, 3, -1, -3, 5, 3, 6, 7], k=3
Monotonic deque vs monotonic stack:
- A monotonic stack finds next greater/smaller element.
- A monotonic deque finds the max/min in a sliding window.
- The deque needs front-removal (to expire old elements) which a stack can't do — that's why it's a deque, not a stack.
07
Section Seven · When to Use
When to Reach for a Deque
| Signal | Use As | Example |
|---|---|---|
| Need stack operations (push/pop/peek) | Stack via push/pop/peek | Valid Parentheses, Daily Temperatures |
| Need queue operations (FIFO) | Queue via offer/poll/peek | BFS traversal, task scheduling |
| "sliding window max/min" | Monotonic deque | Sliding Window Maximum (LC 239) |
| "max/min in a range that slides" | Monotonic deque | Shortest Subarray with Sum ≥ K (LC 862) |
| 0-1 BFS (edges with weight 0 or 1) | Full deque (addFirst for 0-weight, addLast for 1-weight) | Minimum Cost to Make at Least One Valid Path (LC 1368) |
| Palindrome check on characters | Full deque (compare front and back) | Check palindrome after deletions |
Default to ArrayDeque:
- In interviews, declare
Deque<Integer> dq = new ArrayDeque<>();for ALL stack and queue needs. - Only reach for
PriorityQueuewhen you need heap ordering, orLinkedListwhen you need null storage or iterator-based removal.
08
Section Eight · Implementation
Build It Once
Build the sliding window maximum once — it's the only deque-specific algorithm you need. For stack/queue usage, just use ArrayDeque with the right method names.
Java — Sliding Window Maximum
// Sliding Window Maximum — O(n) with monotonic deque int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>(); // stores indices for (int i = 0; i < n; i++) {
// remove expired front if (!dq.isEmpty() && dq.peekFirst() < i - k + 1)
dq.pollFirst();
// remove smaller from back while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i])
dq.pollLast();
dq.offerLast(i);
if (i >= k - 1)
result[i - k + 1] = nums[dq.peekFirst()];
}
return result;
}
Deque — Full Implementation
Java — Deque patterns
import java.util.*;
public class DequePatterns {
// ═══ 1. Sliding Window Maximum ═══════════ O(n) static int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.peekFirst() < i - k + 1)
dq.pollFirst();
while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i])
dq.pollLast();
dq.offerLast(i);
if (i >= k - 1)
res[i - k + 1] = nums[dq.peekFirst()];
}
return res;
}
// ═══ 2. Sliding Window Minimum ═══════════ O(n) static int[] minSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.peekFirst() < i - k + 1)
dq.pollFirst();
while (!dq.isEmpty() && nums[dq.peekLast()] > nums[i])
dq.pollLast(); // flip to > for minimum
dq.offerLast(i);
if (i >= k - 1)
res[i - k + 1] = nums[dq.peekFirst()];
}
return res;
}
// ═══ 3. Deque as Stack ══════════════════ O(1) per op static void stackDemo() {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 3 System.out.println(stack.peek()); // 2
}
// ═══ 4. Deque as Queue ══════════════════ O(1) per op static void queueDemo() {
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll()); // 1 System.out.println(queue.peek()); // 2
}
// ═══ 5. Palindrome check with Deque ═════ O(n) static boolean isPalindrome(String s) {
Deque<Character> dq = new ArrayDeque<>();
for (char c : s.toCharArray())
if (Character.isLetterOrDigit(c))
dq.offerLast(Character.toLowerCase(c));
while (dq.size() > 1)
if (!dq.pollFirst().equals(dq.pollLast()))
return false;
return true;
}
// ═══ Main ═══════════════════════════════════ public static void main(String[] args) {
int[] arr = {1,3,-1,-3,5,3,6,7};
System.out.println("Max window: "
+ Arrays.toString(maxSlidingWindow(arr, 3)));
// [3, 3, 5, 5, 6, 7] stackDemo();
queueDemo();
System.out.println("Palindrome: "
+ isPalindrome("A man, a plan, a canal: Panama"));
// true
}
}
Python — Deque patterns (collections.deque)
from collections import deque
# ═══ 1. Sliding Window Maximum ═══════════ O(n) def max_sliding_window(nums, k):
dq = deque() # stores indices
result = []
for i, v in enumerate(nums):
if dq and dq[0] < i - k + 1:
dq.popleft()
while dq and nums[dq[-1]] < v:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
# ═══ 2. Deque as Stack ══════════════════ O(1)
stack = deque()
stack.append(1) # push
stack.append(2)
stack.pop() # pop → 2
stack[-1] # peek → 1 # ═══ 3. Deque as Queue ══════════════════ O(1)
queue = deque()
queue.append(1) # enqueue (right)
queue.append(2)
queue.popleft() # dequeue (left) → 1
queue[0] # peek → 2 # ═══ 4. Palindrome check ════════════════ O(n) def is_palindrome(s):
dq = deque(c.lower() for c in s if c.isalnum())
while len(dq) > 1:
if dq.popleft() != dq.pop():
return False return True # Python note: collections.deque is implemented as a doubly-linked # list of fixed-size blocks — O(1) append/popleft, O(n) index access. # For stack-only use, list() is faster (contiguous array). # Demo
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]
print(is_palindrome("A man, a plan, a canal: Panama"))
# True
09
Section Nine · Java Reference
Use It In Java
IN JAVA — java.util.ArrayDeque<E>
Import
import java.util.ArrayDeque; / import java.util.Deque; Declare
Deque<Integer> dq = new ArrayDeque<>(); — always use interface type Initial capacity
new ArrayDeque<>(capacity) — optional, default 16, doubles when full | Method | Behaviour | On Empty | Use as |
|---|---|---|---|
push(e) | addFirst(e) | — | Stack push |
pop() | removeFirst() | throws | Stack pop |
offer(e) | addLast(e) | — | Queue enqueue |
poll() | removeFirst() | null | Queue dequeue |
peek() | peekFirst() | null | Both peek |
offerFirst(e) | Insert at front | — | Deque-specific |
offerLast(e) | Insert at back | — | Deque-specific |
pollFirst() | Remove from front | null | Deque-specific |
pollLast() | Remove from back | null | Deque-specific |
peekFirst() | View front | null | Deque-specific |
peekLast() | View back | null | Deque-specific |
⚠ Gotcha:
push() adds to the FRONT (it's a stack method — LIFO). offer() adds to the BACK (it's a queue method — FIFO). If you use both on the same deque, elements go to different ends. Pick one convention: push/pop/peek for stack, offer/poll/peek for queue, offerFirst/offerLast/pollFirst/pollLast for full deque.
⚠ Gotcha:
ArrayDeque does NOT implement the List interface — no get(index), no set(index, value). It's a sequential-access structure. If you need indexed access, use an ArrayList. Deque is for end-operations only.
10
Section Ten · Practice
Problems To Solve
Most "deque" interview problems are actually monotonic deque problems — sliding window maximum and its variants. The remaining uses are as a cleaner stack/queue replacement. If you master Sliding Window Maximum, you've covered 80% of deque interviews.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Hard | mono-deque | Sliding Window Maximum — LC 239 | Decreasing monotonic deque of indices. Front = current window max. Pop expired front, pop smaller back. O(n). |
| Hard | mono-deque | Shortest Subarray with Sum ≥ K — LC 862 | Prefix sum + monotonic deque. Deque maintains increasing prefix sums. Pop front when current prefix minus front prefix ≥ K. |
| Medium | deque | Design Circular Deque — LC 641 | Implement a fixed-capacity circular deque with insertFront, insertLast, deleteFront, deleteLast. Circular array with head/tail pointers. |
| Hard | mono-deque | Constrained Subsequence Sum — LC 1425 | DP + monotonic deque. dp[i] = max(dp[j]) + nums[i] for j in [i-k, i-1]. Deque maintains max dp values in the sliding window. |
| Medium | deque | Design Front Middle Back Queue — LC 1670 | Two deques: front half and back half. Balance sizes after every operation to maintain O(1) middle access. |
| Easy | stack/queue | Implement Queue using Stacks — LC 232 | Use two ArrayDeques as stacks. Push to one, lazy-transfer to the other on poll. Amortised O(1). |
Interview Pattern:
- When you see "maximum/minimum in a sliding window" or "optimise DP with a sliding window constraint," think monotonic deque.
- The template is always: (1) pop expired indices from the front, (2) pop dominated values from the back, (3) push current index, (4) front is the answer.
- For everything else,
ArrayDequeis just your default stack/queue implementation.