Intuition The one core ideaA deque is just a line of items you can add to or remove from at both ends , and every operation stays fast because you only ever touch the two edges — never the middle. Everything on this page exists to make that one sentence rock-solid: what "both ends" means, what "fast" (O ( 1 )
Before you can read the parent note Deque , you must own every symbol it throws at you. Below, each idea is built from nothing, drawn as a picture, and justified — why does the topic need this?
The most basic object here is a sequence : items sitting in a row, left to right.
Definition Front and back
The front is the leftmost end of the line.
The back (also called rear ) is the rightmost end.
Both words name positions , not items. The item there can change; the position stays "the left edge" / "the right edge".
Intuition Why the topic needs thisA stack only pokes one end. A queue pokes one end to add and the other to remove. A deque pokes both ends for both actions . So "front" and "back" are the two doors of the whole structure — every operation is named after the door it uses (push_front, pop_back, ...).
Everywhere in this topic you see the letter n
n n the number of items currently in the structure . If the line is [3, 5, 8], then n = 3 push, n pop, n
Why a single letter? Because we want to talk about cost for any size at once . Saying "if there are n
This is the symbol the whole topic is bragging about ("O ( 1 )
Intuition The picture: how does work grow as the line grows?Imagine feeding your structure more and more items and timing one operation each time. Draw the timing on a graph: horizontal axis = n shape of that curve is what Big-O names.
O ( 1 ) not grow when n flat horizontal line (the blue line above).
O ( n ) n straight slanted line rising with n
O ( nk ) O ( n 2 )
O ( nk ) two sizes multiplied — here n k O ( n 2 ) n × n times itself — the steep red curve. This is what happens if you shift a whole array on every insert.
Intuition Why the topic needs Big-OThe entire selling point of a deque is "both ends in O ( 1 ) . Without the flat-line meaning of O ( 1 ) precisely because it is O ( n ) O ( n 2 )
O ( 1 ) Why it feels right: the "1" looks like a count.
Why it's wrong: O ( 1 ) bounded by a constant — could be 3 steps or 300, as long as it doesn't grow with n Fix: read O ( 1 )
The parent says push is "amortized O ( 1 )
Most pushes are cheap (O ( 1 ) Occasionally the array is full, so you allocate a bigger array and copy everything — that one push costs O ( n ) Amortized asks: spread that rare big cost over all the cheap pushes — what's the average?
Definition Amortized costThe total cost of a long run of operations, divided by the number of operations. Even though a few pushes are expensive, doing n O ( n ) total , so the average per push is O ( n ) / n = O ( 1 )
Intuition Why the topic needs itThe circular-array deque doubles capacity when full. If we only quoted worst-case, push would look like O ( n ) typical cost is still flat. The full argument lives in Dynamic Array Amortized Analysis .
The fast implementation is an array, so we nail its three symbols.
Definition Array, index, capacity
An array is a fixed row of numbered slots in memory.
An index is the slot's number. We count from 0 : the first slot is index 0 1 2 C 0 C − 1
==C
Common mistake Off-by-one: "C Why it wrong: counting from 0, the last valid index is C − 1 C C Fix: remember "0-based": C 0 … C − 1
This is the single most important piece of arithmetic in the array deque, so we earn it slowly.
a mod C a mod C a C 7 mod 5 = 2 7 = 1 × 5 + 2
Why does this build a ring ? Watch what mod 5
0 , 1 , 2 , 3 , 4 , → 0 5 , → 1 6 , → 2 7 , …
The moment you reach the capacity 5 wraps back to 0 . So counting "past the end" of the array silently lands you at the beginning — exactly a circle.
Intuition Why the topic chosemod if check
We could write if (index == C) index = 0;. But mod any overshoot in one clean formula, including jumps and negative steps. It answers the exact question the deque keeps asking: "I walked off the edge — which real slot am I on?" That is why the parent's index formula is index ( k ) = ( f r o n t + k ) mod C
The other implementation uses nodes and pointers.
Definition Node and pointer
A node is a little box holding one item plus arrows to its neighbours.
A pointer is an arrow that says "the next box lives here in memory." Following it is one instant step.
A doubly linked list gives every node two pointers: next (to the right neighbour) and prev (to the left neighbour).
doubly — why the topic insists on prev
To pop_back, you must reach the node just before the last one, so you can rewire it as the new last. With only next arrows, you'd start at the front and walk all the way — that's O ( n ) prev arrow lets you step backwards one hop, giving O ( 1 ) Doubly Linked List .
LIFO = "Last In, First Out." The most recent arrival leaves first — like a stack of plates. This is a Stack .FIFO = "First In, First Out." The earliest arrival leaves first — like a checkout line. This is a Queue .
Intuition Why the topic needs bothA deque is the superset : lock it to one end and you get a stack; add at one end, remove at the other, and you get a queue. Knowing LIFO/FIFO is how you recognise "oh, this deque is just being used as a stack here."
Sequence with front and back
What do "front" and "back" name — items or positions? Positions: the left edge and right edge of the line; the item sitting there can change.
What does the symbol n The current number of items in the structure.
In one phrase, what does O ( 1 ) A flat horizontal line — work does not grow with n
In one phrase, what does O ( n ) A straight slanted line rising in proportion to n
Does O ( 1 ) No — it means bounded by a constant that doesn't grow with n
What does "amortized O ( 1 ) Total cost over n O ( n ) O ( 1 )
For an array of capacity C 0 C − 1
Compute 7 mod 5 2 7 ÷ 5
Why add + C mod C f r o n t − 1 − 1 C
Move front left once from 0 C = 5 ( 0 − 1 + 5 ) mod 5 = 4
Why must the linked-list deque be doubly linked? pop_back needs the node before the last instantly; the prev pointer gives it in O ( 1 ) O ( n )
What do LIFO and FIFO stand for? Last-In-First-Out (stack) and First-In-First-Out (queue).
Parent: Deque — the topic these foundations serveStack — the LIFO restriction of a dequeQueue — the FIFO restriction of a dequeCircular Buffer / Ring Buffer — where the mod C Doubly Linked List — where prev/next pointers are builtDynamic Array Amortized Analysis — the full amortized-O ( 1 ) 
