This page is the "no scenario left behind" companion to the Stack topic note . We will hunt down every kind of situation a stack can hit — normal, empty, full, degenerate, and the tricky exam twist — and work each one all the way through.
Intuition What "every scenario" means for a stackA number can be positive, negative, or zero. A stack has analogous "edge states": it can be empty , full (fixed array), or exactly one element (the boundary between empty and not). Each operation (push, pop, peek) behaves at those edges in a way you must see once so it never surprises you.
Every cell below is a distinct case class this topic can throw at you. The examples afterward each hit one or more cells (labelled [Cell N] ).
#
Case class
Trigger / degenerate input
What could go wrong
1
Normal interleaved push/pop
mixed sequence
wrong LIFO read-off
2
Empty-stack operation
pop/peek on top == -1 or head is Noneunderflow crash
3
Full fixed array
push when top == cap-1overflow crash
4
Single element (boundary)
one push then pop
off-by-one at top = 0
5
Empty → dynamic growth
linked list, no capacity
never overflows
6
Order-of-operations bug
pop = read-then-shrink; push wiring
corrupt / self-loop
7
Real-world word problem
undo history / browser back
model choice
8
Multi-type nesting (exam twist)
([)] vs ([])counter fails, stack needed
Run push(5), push(9), pop(), push(2), push(7), pop(), pop() on an empty array stack (capacity 10). List the return value of each pop and the final contents bottom→top.
Forecast: guess the three popped values before reading on. (People often say 9, 7, 5 — watch.)
push(5) → [5], top=0.
Why this step? First element lands at index top+1 = 0; top moves -1 → 0.push(9) → [5,9], top=1. New top is arr[1]=9.
Why? Increment first, then store — the next free slot is always top+1.pop() → returns 9 , [5], top=0.
Why 9? LIFO removes the most recent survivor, which is 9.push(2) → [5,2], top=1.push(7) → [5,2,7], top=2.pop() → returns 7 , [5,2], top=1.
Why 7? 7 is now newest.pop() → returns 2 , [5], top=0.
Why 2 not 5? 2 arrived after 5, so it leaves first.
Popped order: 9, 7, 2. Final stack: [5].
Verify: Every element that went in (5,9,2,7) either was popped or remains. Popped {9,7,2} ∪ remaining {5} = {5,9,2,7} ✅. And top ended at 0 = (1 push left) − 1 ✅.
Start empty. Call pop(). Then start empty and call peek(). What happens in each?
Forecast: Do these return None, 0, or crash? Decide first.
Empty means top == -1 (array) or head is None (linked list).
Why this test? top = -1 was our sentinel "one below index 0" — there is literally no valid slot to read.
pop() checks is_empty() → true → raises IndexError("pop from empty").
Why raise, not return None? Returning a fake value silently corrupts the caller. A stack has no element to give, so failing loudly is correct.peek() likewise raises on empty — there is no top to look at.
Verify: Reading arr[-1] in Python would return the last slot (wrap-around) — a silent wrong answer. The guard prevents exactly that ✅. Underflow ⇔ top < 0 ⇔ empty.
Array stack with capacity = 3. Do push(1), push(2), push(3), push(4). Trace top and the fourth push.
Forecast: After three pushes, what is top, and what does the fourth do?
push(1)→top=0; push(2)→top=1; push(3)→top=2.
Why watch top? Full means top == cap-1 = 2.is_full() is now true.
Why this exact test? Index 2 is the last legal slot for capacity 3 (indices 0,1,2).push(4) → is_full() true → raises OverflowError("stack full").
Why crash and not grow? A fixed array has no more contiguous memory reserved. Growing is the dynamic array 's job, not this one's.
Verify: cap−1 = 3−1 = 2 = final top ✅. A linked-list stack (singly linked list ) would accept 4 because it allocates a new node — no capacity to hit.
Empty stack. push(42), then peek(), then pop(), then is_empty(). Track top at every moment.
Forecast: After the pop, is the stack empty, and what is top?
push(42): top: -1 → 0, arr[0]=42.
Why 0? top+1 = -1+1 = 0, the first real index.peek(): returns arr[0]=42, top unchanged at 0.
Why unchanged? peek reads only — it must not shrink.pop(): read arr[0]=42 first , then top: 0 → -1.
Why read first? If we did top -= 1 first, top becomes −1 and arr[-1] is the wrong (last) slot.is_empty(): top == -1 → true .
Why? We are back to the exact empty sentinel we started with — the round trip is clean.
Verify: peek returned 42, pop returned 42, both equal the single pushed value ✅. Final top = -1 matches the initial empty state ✅.
Using a LinkedStack (starts empty, head = None), push 10, 20, 30. Draw the node chain and give peek() after each push.
Forecast: Which node is head after all three pushes, and what does peek return?
push(10): new node (10, next→None); head → node10.
Why next→None? Old head was None, so this node sits at the bottom.push(20): new node (20, next→node10); head → node20. peek()=20.
Why wire next before moving head? If we set head = node20 first, node20.next would point to itself — the whole "wire-first" rule from the mistakes list.push(30): new node (30, next→node20); head → node30. peek()=30.
Chain (head→tail): 30 → 20 → 10 → None.
Verify: peek after each push = last pushed value (10, 20, 30) — matches LIFO ✅. No capacity check ever ran, so growth is unbounded ✅. size = 3.
A stack holds [7, 8] (top=1). Someone codes pop as top -= 1; return arr[top]. What does it return, versus the correct x = arr[top]; top -= 1; return x?
Forecast: Will the buggy version return 8 or 7?
Correct order: read arr[1]=8, then top: 1→0, return 8 .
Why? 8 is the newest element, the true top.
Buggy order: top: 1→0 first, then return arr[0]=7.
Why wrong? After decrementing, top points to the element below the real top, so we return 7 and leave 8 stranded (leaked).
Verify: Correct pop = 8; buggy pop = 7. They differ, proving order matters ✅. The stranded 8 also breaks LIFO for later pops.
You visit pages A → B → C → D, then press Back twice, then visit E. Which page are you on, and what remains in Back-history? Model it with a stack.
Forecast: Guess the current page before working it.
Each visit is a push; each Back is a pop (revealing the previous page).
Why a stack? "Back" must undo the most recent navigation first — pure LIFO. (This is the same shape as an undo feature and the call stack .)
Visit A,B,C,D → history bottom→top [A,B,C,D], current = D.
Back → pop D, current = C. History [A,B,C].
Back → pop C, current = B. History [A,B].
Visit E → push E. History [A,B,E], current = E .
Why does C, D vanish? Visiting E from B discards the forward branch — real browsers do exactly this.
Verify: Two Backs from D land on B (D→C→B: two steps) ✅. Final current = E, history depth = 3 (A,B,E) ✅.
Decide balanced or not: (a) ([]), (b) ([)]. Show why a plain +1/−1 counter is fooled but a stack is not.
Forecast: Which of the two strings is balanced? A counter would say both are — is that right?
Rule: push every opener; on a closer, the top must be its matching opener, then pop.
String (a) ([]):
( push → stack [ ( ].[ push → stack [ ( , [ ].] closer: top is [, matches → pop → stack [ ( ].
Why check the top's type? The most recent opener is the only one allowed to close now (LIFO).) closer: top is (, matches → pop → stack empty.End: empty & no mismatch → balanced ✅.
String (b) ([)]:
( push → [ ( ].[ push → [ ( , [ ].) closer: top is [, but ) needs ( → mismatch → NOT balanced ❌.
Why does a counter fail here? A single counter only knows how many brackets are open, not which kind . Both strings have 2 opens then 2 closes, so a counter returns 0 (balanced) for both. The stack remembers the identity and order — this is the whole reason expression parsing needs a stack.
Verify: (a) ends with empty stack and zero mismatches → balanced. (b) hits a type mismatch at step 3 → not balanced. A counter yields 0 for both, giving the wrong verdict on (b) ✅ (mismatch proven).
Recall Quick self-testPop on an empty stack does what? ::: Raises an error (underflow) — there is no element to return.
After push(x) on an array stack, top becomes? ::: old top + 1.
Why must pop read before decrementing? ::: After decrement arr[top] points to the element below, returning the wrong value.
Why does a counter fail on ([)]? ::: It counts quantity, not bracket type/order; a stack remembers which opener is most recent.
A fixed array of capacity n is full when? ::: top == n - 1.
Mnemonic Edge-state checklistE-F-S : before trusting a stack op, ask E mpty? F ull? S ingle-element boundary? Those three cover every degenerate case.
Related: Queue (the FIFO opposite) · DFS uses an explicit/implicit stack .
