Deque (double-ended queue) — operations, use cases: Worked examples

Before anything else, three words we will lean on constantly — defined in plain English so no symbol sneaks in unearned:

The picture above is our mental model for the array deque: a ring of $C$ slots. front is an arrow pointing at the first live slot; the live region sweeps clockwise to rear. Nothing ever "shifts" — only the arrows move.

The scenario matrix

Every deque exercise falls into one of these cells. Our examples below are labelled with the cell they cover so you can see the whole space is filled.

#	Cell (case class)	What makes it tricky
A	Plain trace, both ends	keeping front→back order straight
B	Circular index, no wrap	$(f r o n t + k) mod C$ when nothing crosses the edge
C	Circular index, front wraps left (the $+ C$ guard)	`push_front` when `front = 0`
D	Circular index, rear wraps right	`push_back` crossing slot $C - 1 \to 0$
E	Degenerate: empty deque	popping when `size = 0` (error/underflow)
F	Degenerate: single element	front == rear, both pops target it
G	Full deque → resize (amortized doubling)	copy into a fresh, un-wrapped array
H	Word problem — palindrome (peel both ends)	loop condition `size > 1`
I	Exam twist — Sliding Window Maximum	monotonic deque of indices
J	Exam twist — 0-1 BFS	which end for weight 0 vs weight 1

We now hit every cell.

Example 1 — Cell A: plain both-ends trace

Steps:

push_back(7) → [7]. Why this step? First element; front and rear are both 7.
push_front(4) → [4, 7]. Why? push_front inserts before everything, so 4 lands left of 7.
push_back(9) → [4, 7, 9]. Why? push_back appends on the right.
push_front(1) → [1, 4, 7, 9]. Why? Again inserts at the far left.
pop_back() removes the rightmost → returns 9, leaves [1, 4, 7].
pop_front() removes the leftmost → returns 1, leaves [4, 7].

Verify: count check — 4 pushes minus 2 pops = 2 elements remaining, matches [4, 7]. The two survivors 4 and 7 were the middle insertions, exactly the elements furthest from both ends. ✓

Example 2 — Cell B: circular index, no wrap

Recall the formula from the parent: the $k$ -th element from the front sits at $(f r o n t + k) mod C$ . Why this formula? The live region marches to the right by one slot per step; $mod C$ only matters if we cross the edge.
Plug in: $(1 + 2) mod 6 = 3 mod 6 = 3$ . Why no wrap? $3 < 6$ , so we never reach the edge; the $mod$ leaves it untouched.

Verify: slot 3 is indeed R, the 3rd live element from the front. Direct read-off agrees. ✓

Example 3 — Cell C: `push_front` wraps left (the $+ C$ guard)

Move front left: $f r o n t \leftarrow (f r o n t - 1 + C) mod C = (0 - 1 + 5) mod 5$ . Why the $- 1$ ? push_front needs a fresh slot to the left of the current front.
Compute: $(0 - 1 + 5) mod 5 = 4 mod 5 = 4$ . Why the $+ 5$ ? Without it we'd have $0 - 1 = - 1$ , an illegal index. Adding $C$ before the $mod$ turns "one step left of slot 0" into "slot $C - 1$ ", the wrap the ring picture demands (look at the red arrow in the figure jumping from slot 0 to slot 4).
Store Z at slot 4, set size = 3.

Verify: array becomes [A, B, _, _, Z], and reading from the new front=4 gives logical order Z, A, B. The naive $0 - 1 = - 1$ would have crashed; $+ C$ rescued it into the valid range $[0, 4]$ . ✓

Example 4 — Cell D: `push_back` wraps right

The next free slot at the rear is one past the last live slot. The last live slot is the $(s i z e - 1)$ -th from front: $(f r o n t + s i z e - 1) mod C$ . The new slot is one further, i.e. $(f r o n t + s i z e) mod C$ . Why $f r o n t + s i z e$ ? Front plus how many live elements = the first empty slot on the rear side.
Compute: $(3 + 2) mod 5 = 5 mod 5 = 0$ . Why does it wrap? $5$ equals the edge value $C$ ; the remainder $0$ sends us back to the very first physical slot (see the mint arrow curving from slot 4 to slot 0 in the figure).
Store K at slot 0, set size = 3.

Verify: array [K, _, _, M, N], reading from front=3: logical order M, N, K. K correctly sits at the rear even though it physically wrapped to slot 0. ✓

Example 5 — Cell E: degenerate empty (underflow)

Check the guard before touching any index: if size == 0, there is no front. Why check first? If you computed an index like $(f r o n t + 0) mod C$ you'd read a stale slot — old data still physically sitting there. That would return a ghost value.
Signal underflow: raise an error / return a sentinel (e.g. None), and do not decrement size below 0. Why not decrement? size = -1 corrupts every later index computation.

Verify: invariant 0 ≤ size ≤ C must always hold. Popping an empty deque with a guard keeps size = 0; without the guard it drops to -1, breaking the invariant. The guard is the fix. ✓

Example 6 — Cell F: single element (front == rear)

Rear index $= (f r o n t + s i z e - 1) mod C = (2 + 1 - 1) mod 4 = 2 mod 4 = 2$ . Why? With a single element the rear is the front — both point at slot 2.
Return the value at slot 2 = S; set size = 0. Why not move front? pop_back removes from the rear, so front stays; only size shrinks. (Had we done pop_front, we'd advance front instead and also reach size = 0.)

Verify: after the pop, size = 0 → the empty case of Example 5. Front and rear formulas both gave slot 2, confirming they coincide for one element. ✓

Example 7 — Cell G: full deque → resize (amortized $O (1)$ )

Detect full: size == C (4 == 4). Must grow. Why grow now? Every physical slot is live; there is nowhere to put e.
Allocate a new array of capacity $2 C = 8$ . Why double, not $+ 1$ ? Doubling makes copies rare: $n$ pushes trigger only $O (lo g n)$ resizes whose copy costs sum to $O (n)$ , so the amortized per-push cost is $O (1)$ (see Dynamic Array Amortized Analysis).
Copy in logical order, starting the new front at 0: read old logical order a, b, c, d and place at new slots 0,1,2,3. Set new front = 0. Why re-lay flat? The copy is the perfect moment to un-wrap the ring, so the new array is contiguous and simple.
Now push_back(e): new rear slot $= (0 + 4) mod 8 = 4$ . Store e, size = 5.

Verify: new array [a, b, c, d, e, _, _, _], front = 0, size = 5, capacity 8. Logical order a, b, c, d, e is preserved and no data was lost. ✓

Example 8 — Cell H: word problem, palindrome peel

Deque: [L, E, V, E, L], size = 5. Loop while size > 1. Why > 1? A single leftover middle character has nothing to compare against — it's automatically fine.
Compare pop_front() vs pop_back(): L vs L → equal. Now [E, V, E], size = 3.
Compare again: E vs E → equal. Now [V], size = 1.
Loop stops (size = 1). All comparisons matched → palindrome. Why a deque? You need to grab the outermost pair each time — front and rear together — which only a deque does in $O (1)$ per side.

Verify: length 5 ⇒ $⌊ 5/2 ⌋ = 2$ comparisons expected; we did exactly 2. String reversed is LEVEL = original, confirming palindrome. ✓

Example 9 — Cell I: exam twist, Sliding Window Maximum

We hold indices; the front index always points to the current window's max. Two rules each step $i$ :

Pop from back while the value at the back index $\leq$ the new value (those can never be the max again).
Pop from front if it slid out of the window (front index $\leq i - k$ ).

$i = 0$ (val 1): deque [0].
$i = 1$ (val 3): back is idx0 (val 1) $\leq 3$ → pop it; push 1 → [1].
$i = 2$ (val -1): back is idx1 (val 3) $> - 1$ → keep; push 2 → [1,2]. Window $[0, 2]$ complete → max = value at front idx1 = 3. Why front? Front holds the largest index-value by construction.
$i = 3$ (val -3): back idx2 (val -1) $> - 3$ → keep; push 3 → [1,2,3]. Front idx1 = $3 = i - k = 0$ ? No, $i - k = 0$ , idx1 $> 0$ stays. Window $[1, 3]$ → max = value at idx1 = 3.
$i = 4$ (val 5): pop back while $\leq 5$ : idx3(-3), idx2(-1), idx1(3) all $\leq 5$ → all popped; push 4 → [4]. Front idx4 = i-k? $i - k = 1$ , idx4 $> 1$ stays. Window $[2, 4]$ → max = idx4 = 5.
$i = 5$ (val 3): back idx4 (val 5) $> 3$ → keep; push 5 → [4,5]. Window $[3, 5]$ → max = front idx4 value = 5.

Verify: brute force windows: $max (1, 3, - 1) = 3$ , $max (3, - 1, - 3) = 3$ , $max (- 1, - 3, 5) = 5$ , $max (- 3, 5, 3) = 5$ . Deque produced [3, 3, 5, 5]. Match. Each index is pushed once and popped once → total work $O (n)$ . ✓ (See Sliding Window Maximum.)

Example 10 — Cell J: exam twist, 0-1 BFS end choice

Pop S from the front (distance 0). Relax its edges. Why a deque, not a Priority Queue? With only two possible weights, we never need a full heap — the deque keeps distances sorted for free.
Weight-0 edge to A: push_front(A) (its distance equals S's, so it belongs at the same front level). Why front? A 0-weight move doesn't increase distance, so A must be processed before anything one step farther.
Weight-1 edge to B: push_back(B) (distance is one more, process later). Why back? Larger distance ⇒ later ⇒ the rear.
Deque now front→back: [A, B]. Next pop from front → A.

Verify: final distances $d (A) = 0$ , $d (B) = 1$ . The deque [A, B] is in nondecreasing distance order (0 then 1), which is exactly the invariant 0-1 BFS needs; popping the front yields A (distance 0) first. ✓ (See 0-1 BFS.)

Coverage check

Recall Did we hit every cell?

A→Ex1, B→Ex2, C→Ex3, D→Ex4, E→Ex5, F→Ex6, G→Ex7, H→Ex8, I→Ex9, J→Ex10. Every row of the matrix has a fully worked, verified example.

Cell A covered?

Yes — Example 1, plain both-ends trace.

Which cells test modular wrap and which direction?

C (front wraps left, the +C guard) and D (rear wraps right past C-1 to 0).

Which example enforces the size invariant on underflow?

Example 5 (empty pop) keeps 0 ≤ size ≤ C.

Why does the resize example re-lay the array flat?

The copy un-wraps the ring so the new capacity-2C array is contiguous with front = 0.

Connections

Parent (Hinglish) — the concept these examples drill
Stack · Queue — restricted deques the traces mimic
Circular Buffer / Ring Buffer — the ring picture behind Cells B–D, G
Doubly Linked List — alternate $O (1)$ backing
Dynamic Array Amortized Analysis — why doubling in Example 7 is $O (1)$
Sliding Window Maximum — Example 9
0-1 BFS — Example 10
Priority Queue — what the deque replaces in 0-1 BFS