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

4 is in the middle and inserted first, so it is the seed. Then 7 must land to its left (front) and 9 to its right (back).

1. push_back(4) → [4]
2. push_front(7) → [7, 4]
3. push_back(9) → [7, 4, 9] ✅ Why: push_front always inserts before everything, push_back after everything. So to grow on both sides of a seed you use one of each.

push_back adds at the rear, pop_front removes from the front → the first thing you put in is the first thing out. This is a Queue (FIFO). Contrast: push_back+pop_back would be a Stack (LIFO), because you remove from the same end you added.

front() returns the leftmost = 3. back() returns the rightmost = 8. Peek does not remove, so the deque is unchanged: [3, 5, 8]. Why it matters: pop_front() would have returned 3 and left [5, 8]. Peek is look-only.

Walk it one poke at a time, always asking "which tip does this touch?"

• Step 1 — push_front(2): the deque is empty, so front and back are the same slot. The result is [2]. Nothing returned — pushes never return.
• Step 2 — push_back(6): push_back glues 6 onto the right tip, after the existing 2. So 6 lands to the right of 2 → [2, 6]. This is why order matters: had we called push_front(6) instead, we'd have gotten [6, 2].
• Step 3 — push_front(1): push_front glues 1 onto the left tip, before everything. So 1 lands left of 2 → [1, 2, 6].
• Step 4 — pop_back(): removes and returns the rightmost element. The rightmost is 6, so it returns 6 and the deque shrinks from the right → [1, 2].
• Step 5 — push_back(9): glues 9 onto the right tip again → [1, 2, 9]. Nothing returned.
• Step 6 — pop_front(): removes and returns the leftmost element. The leftmost is 1, so it returns 1 and the deque shrinks from the left → [2, 9].

Collecting the picture into a table (each row is just the sentence above):

Final deque: [2, 9]. Returned in order: 6, then 1. The one habit to internalize: the word front always means the left tip and back always means the right tip — decide which tip an operation touches first, and the row writes itself.

The formula from the parent note (move front left, guard the wrap): $front\leftarrow (front-1+C)\mathrm{mod}C=(0-1+6)\mathrm{mod}6=5\mathrm{mod}6=5$ Store X at index 5, set size = 4. Layout (_ = empty), indices 0..5: [a, b, c, _, _, X]. Logical order front→back starts at index 5: X, a, b, c. Why +C? Without it, 0 - 1 = -1, an illegal index. Adding C before the mod sends front off the left edge and wraps it to the right edge — exactly the red arrow in the figure above, which lands on slot 5.

$\text{index}(k)=(front+k)\mathrm{mod}C=(6+3)\mathrm{mod}8=9\mathrm{mod}8=1$ So the $k=3$ element sits at physical index 1. It wrapped: positions walked are $6,7,0,1$ → the third step lands past the edge onto slot 1. Sanity: the 5 elements occupy indices $6,7,0,1,2$. Element index-1 is indeed the 4th listed = $k=3$ (zero-based). ✅

pop_back() is $O(n)$, not $O(1)$. Why: removing the last node requires updating the second-to-last node's next to null. With only next pointers you cannot jump backward from tail; you must walk from the head until you find the node whose next is tail — that walk is $n-1$ steps = $O(n)$. Fix: give each node a prev pointer (Doubly Linked List). Then tail.prev is the predecessor instantly → $O(1)$. This is the whole reason the parent note insists on doubly linked.

The $i$-th push_front shifts the $i-1$ elements already present. Total work: ${\sum }_{i=1}^n(i-1)=0+1+2+\cdots +(n-1)=\frac{n(n-1)}{2}=O(n^2)$ So $n$ front-inserts cost $O(n^2)$, not $O(n)$. Why this kills the deque's promise: a deque exists to give $O(1)$ at both ends. Shifting turns one end into $O(n)$ per op, defeating the purpose. Fix: Circular Buffer / Ring Buffer — move the front pointer instead of the data.

Capacity doubles at sizes $1,2,4,8$ (the copies happen right before growing past these). Elements copied at each resize: $1+2+4+8=15$ Total copy work $=15<16=n$. In general the geometric sum $1+2+\cdots +2^k$ is $2^{k+1}-1<2n$, i.e. $O(n)$ total copying across all $n$ pushes. Amortized meaning: spread that $O(n)$ total over $n$ pushes = $O(1)$ average per push, even though one individual push (the one triggering a resize) is $O(n)$. See Dynamic Array Amortized Analysis.

while size > 1:
    if pop_front() != pop_back():
        return False
return True   # 0 or 1 element left in the middle

Invariant: everything already popped in matching pairs was equal, and the remaining deque is the untested middle substring. Trace on L E V E L:

• pop_front L, pop_back L → equal, deque E V E
• pop_front E, pop_back E → equal, deque V
• size == 1 → loop ends → True (palindrome). Middle V never needs a partner. Why a deque? You must peel from both ends at once in $O(1)$ — a stack alone can't reach the front cheaply, a queue can't reach the back.

The deque holds indices, and we maintain one promise: the values they point to strictly decrease from front to back, so the front index is always the current window's maximum. Watch the four rules fire as we advance i one step at a time.

• i=0, A[0]=1: deque empty, just push_back(0) → [0]. No window yet (need 3 elements).
• i=1, A[1]=3: before pushing, check the back: A[0]=1 <= A[1]=3, so index 0 can never be a future max (a bigger, newer value shadows it) → pop it. Now push_back(1) → [1]. Still no full window.
• i=2, A[2]=-1: back is index 1, A[1]=3 > -1, so -1 does not shadow it → keep, then push_back(2) → [1, 2]. Now i = 2 = k-1, first window [1,3,-1] is complete. Its max is A[front] = A[1] = 3.
• i=3, A[3]=-3: back index 2, A[2]=-1 > -3 → keep, push_back(3) → [1, 2, 3]. Window is [3,-1,-3]; before reading the max, check front-expiry: front is index 1, is 1 <= i-k = 0? No. So max = A[1] = 3.
• i=4, A[4]=5: 5 is huge — pop the back while it's <= 5: A[3]=-3≤5 pop, A[2]=-1≤5 pop, A[1]=3≤5 pop. Deque empties, then push_back(4) → [4]. Window [-1,-3,5], max = A[4] = 5.
• i=5, A[5]=3: back index 4, A[4]=5 > 3 → keep, push_back(5) → [4, 5]. Window [-3,5,3], front 4 still in window (4 > i-k = 2), max = A[4] = 5.

Same walk in table form (each row is one bullet above):

Answers (window maxima): 3, 3, 5, 5. Why $O(n)$? Each index is pushed once and popped once → total deque operations $\le 2n$. The two "why deque" moments are visible above: newer bigger values evict from the back, and expired indices leave from the front — two different ends, both $O(1)$. See Sliding Window Maximum.

• Edge of weight 0 → push_front(neighbor): same distance as the current node, so it belongs at the cheapest end, processed next.
• Edge of weight 1 → push_back(neighbor): distance is one greater, so it belongs behind everything at the current distance. Invariant maintained: the deque always holds nodes of at most two distinct distances, $d$ (front region) and $d+1$ (back region), non-decreasing front→back. Popping from the front therefore always yields the smallest tentative distance — exactly what a priority queue would, but in $O(1)$ instead of $O(\log n)$.

Keep two stacks, L (its top = the deque's front) and R (its top = the deque's back).

• push_front → push onto L; push_back → push onto R.
• pop_front → pop L. If L is empty, rebalance: move half of R into L (reversing so tops line up), then pop. Cost of the empty-L case: a rebalance touches $O(m)$ elements, but it only happens after at least $\sim m/2$ cheap pops emptied L. Charging the rebalance to those pops gives $O(1)$ amortized. Edge case: if both stacks are empty, pop_front is an error (underflow) — must be guarded, just like popping an empty stack. Why it works at all: stacks give $O(1)$ at their single top; two of them, tops pointing at opposite ends, cover both deque ends — the reversal cost is amortized away.

(a) size == C means the ring is full → resize: allocate a new array of capacity 2C, copy the C logical elements in front→back order into the fresh array (typically re-basing front = 0), then continue the insertion. By the doubling argument of L3.3 this is amortized $O(1)$. (b) size == 0 (empty): there are no elements, so front points at no valid data — its numeric value is meaningless until the first insert. Conventionally it is kept at 0, but any index is equally correct because nothing is readable. The very first push_front/push_back sets the meaningful position. (c) No. Every update to front (and to any read index) passes through mod C, and mod C always returns a value in the range $[0,C-1]$. So no matter how many times the pointer wraps around the ring, front can never exceed C-1 — the modular arithmetic is the guarantee that keeps indices legal. (d) You cannot distinguish empty from full using the pointer positions alone — this is the classic circular-buffer ambiguity: a totally empty ring and a totally full ring can both make the front/back regions coincide. Fix: store an explicit size counter (or, alternatively, sacrifice one slot as a permanent gap sentinel). Then the test is unambiguous: size == 0 → empty, size == C → full. This is exactly why the parent note tracks size alongside front rather than trying to derive fullness from pointers.

Use a deque of actions, most-recent at the back.

• New action → push_back(action). Then if size > H → pop_front() to drop the oldest action, keeping history bounded at H.
• Undo → pop_back() on the main deque (takes back the most recent action) and push_back() it onto a separate redo deque.
• Redo → pop_back() on the redo deque and push_back() it onto the main deque (re-applies the most recently undone action).
• On a fresh action after some undos → clear the redo deque (the redo history is invalidated), exactly like real editors. Why a deque, not a stack? Undo/redo on its own is stack-like: you always take back the most recent action (LIFO at the back). But the bounded-history requirement forces you to also delete the oldest action — that lives at the front. Only a structure with $O(1)$ at both ends can simultaneously "add newest at back" and "evict oldest at front". Why a stack fails: a plain stack has cheap access only at its top; dropping the bottom element would require shifting or emptying the whole stack = $O(H)$ per eviction. The deque makes eviction $O(1)$. Edge cases: undo on an empty main deque is a no-op (nothing to undo); redo on an empty redo deque is a no-op (nothing to redo); both must be guarded like an empty-stack pop.