Deque (double-ended queue) — operations, use cases: Visual walkthrough

This page has ONE goal: to show you, picture by picture, why a deque — and only a deque — turns the "maximum of every window" problem from slow into $O (n)$ . We build the whole idea from nothing. If you have never seen a deque, start here; the parent Deque topic note is your home base.

Step 1 — What the problem even is

WHAT. We are given a row of numbers, written left to right. Think of them as boxes on a shelf. A window is a small viewing frame that covers exactly $k$ boxes at once (here $k$ is just "how wide the frame is"). We slide the frame one box to the right at a time, and each time we must say the largest number the frame currently covers.

WHY this matters. The lazy method — look at all $k$ boxes and pick the max every single time — costs $k$ glances per position. With $n$ boxes total there are about $n$ positions, so that is $n \times k$ glances. When $k$ is large this is painfully slow. We want to reuse work between neighbouring windows.

PICTURE. Below, the array is $[1, 3, - 1, - 3, 5, 3, 6, 7]$ and the window width is $k = 3$ . The teal frame is over the first three boxes; its maximum is the orange box.

Figure — Deque (double-ended queue) — operations, use cases

Notation we just earned:

$n$ ::: the total count of numbers in the array.
$k$ ::: the fixed number of boxes each window covers.

Step 2 — The wasteful method, so we know what to beat

WHAT. For every window position, scan all $k$ boxes and keep the biggest. Move one step right, repeat.

WHY show it. You cannot appreciate the deque trick until you feel the waste. Watch the two frames below: when the window slides from position 1 to position 2, the boxes $3$ and $- 1$ are looked at again — we already knew them last time. That re-looking is the whole cost we will delete.

PICTURE. The overlapping frames share the plum boxes. Every plum box is a wasted second glance.

Step 3 — The key insight: most numbers are hopeless

WHAT. Look at two boxes inside the current window: a smaller one sitting to the left of a bigger one. The smaller-left box can never be the answer again.

WHY. Any future window that still contains the small box must also contain the big box — because the big one is to its right, closer to the incoming edge, so it leaves the window later. A bigger number that outlives you makes you permanently useless. We can throw the small-left box away forever.

PICTURE. Box value $3$ (orange) dominates the $1$ to its left. Anywhere the $1$ survives, the $3$ survives too and is larger. So $1$ is crossed out — it will never be a maximum again.

Step 4 — Storing the survivors: why a deque and nothing else

WHAT. We keep the survivors — the not-yet-dominated candidates — in decreasing order of value. This list of survivors needs three different edits, and each happens at a different end.

WHY a deque. List the three edits and where each happens:

Edit we need	Which end	Reason
A new box arrives	the back	it is the newest, right-most candidate
Smaller candidates die	the back	the newcomer dominates them (Step 3)
The window's left edge moves past a candidate	the front	the oldest, left-most candidate expires

Three operations, two ends, all must be $O (1)$ . A Stack gives one end; a Queue gives one-in-one-out; only a deque gives fast poking at both ends. That is the entire reason it appears here.

PICTURE. The deque drawn as a horizontal box, with the three arrows showing exactly where each edit strikes.

Step 5 — The two rules, executed on one new box

WHAT. When a new box at position $i$ arrives, do two things in order:

Pop from the back every candidate whose value is $\leq$ the new value (they are now dominated — Step 3).
Push the new index $i$ onto the back.

WHY this order. We must clear the dominated small ones before the newcomer sits down, otherwise the decreasing order breaks. After this, the front of the deque always holds the index of the window's current maximum.

PICTURE. New value $5$ arrives. It is bigger than $- 3$ and $- 1$ sitting at the back, so both are popped (plum, falling away), then $5$ joins as the new back.

Step 6 — Retiring the front when the window slides past it

WHAT. After placing the new index, check the front. If the front index is too far left — outside the current window — remove it with pop_front.

WHY. A candidate is only valid while it lives inside the frame. The window covering positions $i - k + 1 \dots i$ has left edge $i - k + 1$ . Any stored index smaller than that has slid off the shelf's left side and must retire, even if it was the maximum a moment ago.

PICTURE. The window's left edge (teal dashed line) has moved right of the front candidate. That front box is greyed and popped off the left.

Step 7 — Reading the answer, every step, in $O (1)$

WHAT. Once the window is a full $k$ wide (i.e. $i \geq k - 1$ ), the answer for this position is simply $value [deque.front]$ — no scanning.

WHY it is the max. The deque is always strictly decreasing front-to-back (Step 3 guarantees it), so its front holds the largest surviving value, and Step 6 guarantees every survivor is inside the window. Largest-and-valid = the window maximum.

PICTURE. The full run on $[1, 3, - 1, - 3, 5, 3, 6, 7]$ , $k = 3$ . Each row is one window; the orange box is the front-of-deque answer.

The maxima come out as $[3, 3, 5, 5, 6, 7]$ .

Worked example Full trace,

$k = 3$ , array $[1, 3, - 1, - 3, 5, 3, 6, 7]$ Deque holds indices; I show the values in brackets.

$i$	value	after evict-back	after push	after expire-front	answer
0	1	[1]	[1]	[1]	—
1	3	[] (1 popped)	[3]	[3]	—
2	-1	[3]	[3,-1]	[3,-1]	3
3	-3	[3,-1]	[3,-1,-3]	[3,-1,-3]	3
4	5	[] (all popped)	[5]	[5]	5
5	3	[5]	[5,3]	[5,3]	5
6	6	[] (all popped)	[6]	[6]	6
7	7	[] (6 popped)	[7]	[7]	7

Why at $i = 4$ everything is popped? $5$ dominates $3, - 1, - 3$ — all $\leq 5$ , all to its left. They vanish, leaving only $5$ .

Step 8 — Edge and degenerate cases (never leave a gap)

WHAT & WHY, one row each:

$k = 1$ . Every window is a single box, so the answer is the box itself. The deque holds exactly one index at a time: each newcomer evicts the previous (it is $\leq$ or not, but the front expires immediately anyway). Output equals the input array.
$k = n$ . One window covering everything; the answer is the global maximum. The front never expires (no index is ever $\leq i - k$ while $i < n$ ), so the deque just accumulates the decreasing survivors and the front is the global max.
All equal, e.g. $[4, 4, 4, 4]$ . Because we evict on $\leq$ , each new $4$ pops the previous $4$ ; deque length stays $1$ . Answer is $4$ everywhere. (Using $<$ instead would grow the deque needlessly — still correct, but wasteful.)
Strictly increasing $[1, 2, 3, 4]$ . Every newcomer evicts all survivors; deque length stays $1$ ; the front is always the newest, biggest box. Answer tracks the right edge.
Strictly decreasing $[4, 3, 2, 1]$ . Nothing is ever dominated, so nothing is evicted from the back; the front expires one at a time as the window slides. The deque holds up to $k$ items.
Empty array or $k = 0$ . No windows exist; output is empty. Guard this before the loop.

PICTURE. The two extremes drawn side by side: increasing (deque stays length 1) vs decreasing (deque grows to $k$ ).

The one-picture summary

The single diagram fuses the loop: a newcomer arrives at the back, dominated smaller boxes are evicted from the back, expired boxes retire from the front, and the front is read off as the answer — decreasing order maintained throughout.

Recall Feynman retelling in plain words

Picture a row of kids of different heights and a rope frame that shows exactly three kids at a time, sliding right one kid per step. You must call out the tallest kid inside the frame each step. Trick: keep a short "shortlist" of kids who could still be the tallest, tallest-first. When a new kid walks in on the right, any shorter kids already at the end of the shortlist are useless (the new taller kid will outlast them), so they leave. If the kid at the front of the shortlist has slid out the left side of the frame, they leave too. Then the front of the shortlist is always the tallest kid still in view — you just read their height, no counting. Each kid joins the shortlist once and leaves once, so the whole parade is done in one smooth pass. That is Sliding Window Maximum, and it needs poking at both ends of the shortlist at once — which is exactly, and only, what a deque gives you.

Connections

Deque — Hinglish topic note — the parent home base
Sliding Window Maximum — the algorithm this page derives
Stack — one end only
Queue — FIFO only
Circular Buffer / Ring Buffer — how to store the deque in an array
Doubly Linked List — the pointer implementation
Dynamic Array Amortized Analysis — the "each index touched twice" logic
0-1 BFS — another deque application
Priority Queue — what the deque replaces here