Exercises — Stack — LIFO semantics, push - pop - peek, array and linked list implementations

WHAT we look at: "last in, first out" is literally the definition. Answer: a stack. The acronym is LIFO (Last-In, First-Out). A queue is the opposite — FIFO, first-in first-out.

The top is the rightmost element here, 9.

• peek() returns 9 and the stack stays [7, 3, 9] (peek never removes).
• pop() returns 9 and the stack becomes [7, 3] (pop removes).

top stores the index of the last filled slot. When one element sits at index 0, we need top = 0. So the empty state must be one below the first real index → top = -1. If we used 0 for empty, we could not tell "empty" from "one element at index 0". When top == -1, pop()/peek() have nothing to act on → they underflow and must raise an error (see the boundary box above), never return arr[-1].

Track bottom→top (this matches the top row of the figure — the rightmost box in each little pile is the orange top):

1. push(5) → [5]
2. push(8) → [5, 8]
3. pop() → returns 8, stack [5]
4. push(2) → [5, 2]
5. peek() → returns 2, stack unchanged [5, 2]
6. pop() → returns 2, stack [5]
7. pop() → returns 5, stack [] (now empty — a further pop would underflow) Returned values in order: pops = 8, 2, 5; peek = 2. Final stack empty.

Push d, a, t, a → stack (bottom→top) [d, a, t, a] (this is the tallest pile in the middle row of the figure). Pop repeatedly: a, t, a, d. Output = "atad" — the reverse of "data". LIFO output is reversal.

push does top += 1; pop does top -= 1 (the bottom row of the figure plots exactly these top values, with the dashed line marking "full"):

• push → top = 0
• push → top = 1
• push → top = 2
• pop → top = 1
• push → top = 2 Full means top == capacity - 1 = 3 (the last of the 4 slots, indices 0..3, is filled). We reach at most top = 2, so it is never full. Final top = 2 (three elements stored).

Indices: arr = [7, 3, 9], top = 2.

• Correct order: x = arr[2] = 9; then top = 1. Returns 9 ✅ (the real top).
• Wrong order: top = 1 first; then x = arr[1] = 3. Returns 3 ✗ — the element below the top, and the real top 9 is silently leaked (still sitting at index 2, treated as removed). Rule: order = (read, shrink). Read while top still points at the top.

Bug: after self.head = Node(x), the name self.head already points to the new node. Then self.head.next = self.head makes the node point to itself, and the old top is lost. Trace:

• push(1) on empty: node1 created, head = node1, node1.next = node1 (self-loop). Old head was None — already lost, but node1 loops to itself.
• push(2): node2 created, head = node2, node2.next = node2. node1 is now unreachable — the entire previous stack vanished, and node2 loops to itself. Any traversal (while cur: cur = cur.next) would loop forever. Fix — wire before rewiring the head:

def push(self, x):
    self.head = Node(x, self.head)  # new node.next = OLD head, then becomes head

The new node must point to the old head before head is reassigned.

String: "([)]". Counter view — accumulate a running total: add +1 for any opening bracket (( or [) and −1 for any closing bracket () or ]). Reading ([)] left to right, the running total (prefix sums) after each character is:

• after ( : $0+1=1$
• after [ : $1+1=2$
• after ) : $2-1=1$
• after ] : $1-1=0$

Sequence of running totals = [1, 2, 1, 0]. It never goes negative and ends at 0, so the counter declares it balanced ✗. Stack view: push (; push [; now ) arrives, top is [ — mismatch (a ) must close a (), so it is invalid ✅. Why: a counter remembers only how many brackets are open, not which kind and in what order. Correct nesting requires the most-recent opener to match — exactly LIFO. That is why bracket matching needs a stack, not a counter. (Context — infix to postfix): Expression Evaluation — infix to postfix uses the same LIFO idea for operators: when a new operator arrives you pop operators of higher-or-equal precedence off a stack first, because the most-recently-pushed operator must be resolved before older ones — just like the most-recent bracket must close first.

Read left→right, stack bottom→top:

1. 5 → [5]
2. 1 → [5, 1]
3. 2 → [5, 1, 2]
4. +: b=2, a=1 → 1+2=3 → [5, 3]
5. 4 → [5, 3, 4]
6. *: b=4, a=3 → 3*4=12 → [5, 12]
7. +: b=12, a=5 → 5+12=17 → [17]
8. 3 → [17, 3]
9. -: b=3, a=17 → 17-3=14 → [14] Final value = 14. Why the pop-order matters: for non-commutative - and /, the second pop is the left operand a. Getting it backwards would give 3 - 17 = -14.

Design:

• enqueue(x): push x onto in.
• dequeue(): if out is empty, pop everything from in into out (this reverses order once), then pop from out.

Reversing a LIFO stack once turns it into FIFO order — that is the whole trick. Trace:

1. enqueue(1): in=[1], out=[]
2. enqueue(2): in=[1,2], out=[]
3. dequeue(): out empty → move all: pop 2 then 1 into out → out=[2,1] (bottom→top), in=[]. Pop out → 1. out=[2]
4. enqueue(3): in=[3], out=[2]
5. dequeue(): out not empty → pop out → 2. out=[]
6. dequeue(): out empty → move in: pop 3 → out=[3], in=[]. Pop out → 3. Dequeued order: 1, 2, 3 — perfect FIFO. Cost: each element is pushed to in once and moved to out at most once, so across $n$ operations the total work is proportional to $n$ → amortized $O(1)$ per operation (constant on average, even though a single dequeue that moves everything is momentarily $O(n)$). This "cheap-most-of-the-time, occasional-expensive-step" pattern is exactly the amortized analysis idea revisited in L5.3.

Push order is alphabetical, so the last pushed (deepest alphabetically) pops first — LIFO drives the "go deep" behaviour.

1. Push A. Stack [A].
2. Pop A → visit A. Push its unvisited neighbours B, C → stack [B, C] (C on top).
3. Pop C → visit C. Neighbours A(visited), D → push D → stack [B, D].
4. Pop D → visit D. Neighbours B, C — C visited, B not yet visited → push B → stack [B, B].
5. Pop B → visit B. All neighbours visited → push nothing → stack [B].
6. Pop B → already visited → skip. Stack []. Done. Visit order: A, C, D, B. The stack replaces the recursion call stack — same LIFO, but now we hold the memory, so no risk of a call-stack overflow on deep graphs.

Idea: keep a second stack mins. On push(x), push min(x, current_min) onto mins (or x if empty). On pop, pop both stacks. Then getMin() = mins.peek(). Because each mins entry is the min of everything at-or-below it, it stays valid after any pop — no recomputation, so it touches only the tops → constant $O(1)$ time. Trace (main / mins, bottom→top):

• push(5): main [5], mins [5]
• push(3): min(3,5)=3 → main [5,3], mins [5,3]
• push(7): min(7,3)=3 → main [5,3,7], mins [5,3,3]
• push(2): min(2,3)=2 → main [5,3,7,2], mins [5,3,3,2]
• pop(): remove top of both → returns 2; main [5,3,7], mins [5,3,3]
• getMin(): mins.peek() = 3 ✅ Each op touches only tops → $O(1)$ time, $O(n)$ extra space for mins.

Base case $n=1$: push $x_1$, pop → returns $x_1$. Reverse of $[x_1]$ is $[x_1]$. ✓ Inductive step: assume for any sequence of length $k$ the claim holds. Take length $k+1$: push $x_1,\dots ,x_{k+1}$. The very last push put $x_{k+1}$ on top, so the first pop returns $x_{k+1}$ (the definition of push/top). After that pop, the stack is exactly the state after pushing $x_1,\dots ,x_k$. By the hypothesis, the remaining $k$ pops give $x_k,x_{k-1},\dots ,x_1$. Concatenating: $x_{k+1},x_k,\dots ,x_1$ = reverse of the input. ✓ By induction the claim holds for all $n\ge 1$. $■$ This is why Example L2.2 reverses a string — reversal is the structural signature of LIFO.

Suppose we start at capacity 1 and double each time it fills: capacities hit $1,2,4,8,\dots$ A resize copies the current contents. Over $n$ pushes, the copies performed at successive resizes total $1+2+4+8+\cdots +2^k\text{where }{2}^k\le n.$ This is a geometric series. Using the identity ${\sum }_{i=0}^k{2}^i=2^{k+1}-1,$ the sum equals $2^{k+1}-1$. Since $2^k\le n$, we have $2^{k+1}\le 2n$, so the total copy work $<2n$. Add the $n$ plain stores (one per push, each $O(1)$): total work $<2n+n=3n=O(n)$. Divide by the $n$ pushes: amortized $O(1)$ per push. The occasional expensive $O(n)$ resize is "paid for" by the many cheap $O(1)$ pushes that happened before it — this is precisely the accounting done in Dynamic Array / Amortized Analysis. Key sum to remember: ${\sum }_{i=0}^k{2}^i=2^{k+1}-1.$

LIFO in one sentence ::: The last element pushed is the first one popped — output is the reverse of input order. Why read-then-decrement in array pop ::: Because top still points at the real top while you read; decrement first and you return the element below and leak the top. Why a stack (not a counter) for [](){} ::: A counter forgets which bracket opened; only a stack remembers order, so ([)] is caught. What happens on pop/peek of an empty stack ::: It underflows — the operation must raise an error, so guard with isEmpty first. What happens on push into a full fixed array ::: It overflows — push must raise an error (guard with isFull); a dynamic array instead resizes and never overflows.