Noesis
3.2.5 · D5Linear Data Structures

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

1,944 words9 min read↑ Back to topic
Figure — Stack — LIFO semantics, push - pop - peek, array and linked list implementations
Figure — Stack — LIFO semantics, push - pop - peek, array and linked list implementations

True or false — justify

A stack always outputs elements in exactly the reverse order they were inserted.
False. Reverse order only holds if you push everything first and then pop everything; if you interleave pushes and pops (e.g. push 1, push 2, push 3, pop→3, push 4, pop→4, pop→2) the output order is not the strict reversal of insertion.
peek() and pop() return the same value when called on the same non-empty stack.
True for the returned value (both hand back the top element), but they differ in effect: peek leaves the stack unchanged while pop also removes that element and shrinks the size.
A stack implemented on a fixed-size array of capacity can never raise an error on push.
False. When top == n-1 every slot is filled, so push must raise an overflow error — a fixed array has a hard capacity ceiling that a linked-list stack does not.
In the array implementation, the empty stack is represented by top == 0.
False. Empty is top == -1, one slot below index 0; top == 0 means exactly one element sits in arr[0].
A linked-list stack can overflow if you push too many elements.
False in the algorithmic sense — it grows one node at a time with no fixed capacity. It only fails when the machine genuinely runs out of memory, which is not part of the abstract data type's contract.
Using a plain integer counter (+1 on (, −1 on )) correctly validates any bracket string.
False. A counter works for a single bracket type but forgets which symbol opened, so it wrongly accepts crossed nestings like ([)]. Multiple bracket types require a stack to remember order.
A stack and a queue differ only in a naming convention.
False. They embody opposite disciplines: a stack is LIFO (remove the most recent), a queue is FIFO (remove the oldest). This changes which real problems each solves — undo/backtracking versus fair scheduling.
Reversing a string with a stack works because push-then-pop yields reverse order.
True. Pushing each character then popping all of them outputs characters in reverse insertion order, which is the definition of a stack's output — this is why "cat" becomes "tac".
Every operation on an array-backed stack is guaranteed time.
True for a fixed array (push/pop/peek touch only arr[top]). For a dynamic array it is amortized: most pushes are cheap, but an occasional resize costs — the picture below shows how those rare costs average out. See Dynamic Array / Amortized Analysis.
You must traverse a linked-list stack to find the top element.
False. The head pointer is the top, so access is immediate with no traversal — that is precisely why we make head = top.
Figure — Stack — LIFO semantics, push - pop - peek, array and linked list implementations

Spot the error

pop: the student writes self.top -= 1 first, then return self.arr[self.top]. What breaks?
After decrementing, arr[top] now points to the element below the real top, so it returns the wrong value and leaks the actual top (see the correct read-then-shrink order in the figure above). Correct order is read first, then shrink.
Linked-list push: self.head = node; node.next = self.head. What breaks?
After head = node, head already equals node, so node.next = head makes the node point to itself — an infinite self-loop that discards the rest of the stack. Wire node.next = old_head before reassigning head.
A student uses pop() inside a loop where they only wanted to inspect the top. What breaks?
pop removes the element, so the stack silently shrinks every iteration; they meant peek, which reads without removing. Confusing the two corrupts the size.
Someone checks isEmpty in the array stack with self.top == 0. What breaks?
That test is true when one element exists, not zero, so it reports a one-element stack as empty and never detects the truly empty case (top == -1). Off-by-one on the sentinel.
Bracket check: on ) the student pushes instead of pops. What breaks?
Pushing on a closing bracket means opens are never matched, so depth only grows and the "end empty" test always fails — even a perfectly balanced string is rejected.
peek on the array stack does self.top -= 1; return self.arr[self.top+1]. What breaks?
It mutates top, so the "read-only" peek actually removes the element from the stack's logical view (a later push overwrites it). Peek must never touch top.
In linked-list pop, the student does self.head = self.head.next but forgets to read head.data first. What breaks?
Once head advances, the old top node is unreferenced and its data is lost, so there is nothing left to return. Capture x = head.data before moving the pointer.

Why questions

Why is push on a stack but inserting into the middle of an array is ?
A stack only ever writes at arr[top+1], touching one slot; a mid-array insert must shift every following element to make room. The stack's one-end restriction is exactly what buys the constant cost.
Why do we deliberately forbid random access in a stack when we could allow it?
Restricting access to one end guarantees every operation is and keeps the invariant (LIFO) unbreakable. The constraint is the feature — it makes correctness and speed automatic.
Why does the function call mechanism use a stack rather than a queue?
Functions must return in the reverse order they were called — the most recently entered function finishes first — which is exactly LIFO. See Recursion and the Call Stack.
Why can't a single counter distinguish ([)] from ([])?
A counter only tracks how many brackets are open, not which type opened last. Detecting a crossed close requires comparing the incoming bracket to the most recent open, i.e. the stack's top.
Why does linked-list push set node.next = head before head = node?
If you overwrite head first, the reference to the old top (the rest of the list) is lost. Linking the new node into the chain first preserves the old stack before changing the entry point.
Why is Depth-First Search naturally a stack-based algorithm?
DFS explores as deep as possible then backtracks to the most recent unexplored branch — "most recent first" is LIFO, so an explicit stack (or the call stack) captures exactly that order.
Why does converting infix to postfix rely on a stack of operators?
Operators must be released in an order determined by precedence and nesting, where the last deferred operator is often output first; a stack holds pending operators and pops them in the correct LIFO order. See Expression Evaluation — infix to postfix.
Why does a linked-list stack use more memory per element than an array stack?
Each node stores an extra next pointer alongside the data, whereas a contiguous array stores only the values with no per-element bookkeeping.

Edge cases

What should pop() do on an empty stack?
It must signal an error (underflow / raise an exception), never return garbage. There is no top element to remove, so returning anything silently would corrupt program logic.
What should peek() return on an empty stack?
Same as pop's boundary: it must raise/underflow, because there is no top to inspect. Returning None silently can mask bugs unless the API explicitly defines that.
After pushing one element and popping it, what does top equal in the array stack?
Back to -1, the empty sentinel — push moved it to 0, pop moved it back to -1, restoring the empty state.
Is the empty string "" balanced under the bracket-matching rule?
Yes. No brackets means the stack never underflows and ends empty, satisfying both conditions — vacuously balanced.
Is a lone closing bracket ")" balanced?
No. On seeing ) we try to pop an empty stack (underflow), which immediately signals imbalance — there is no open bracket to match. This is the underflow failure mode.
Is a lone opening bracket "(" balanced?
No. It never underflows — the push succeeds — but the stack ends non-empty, so the "end empty" condition fails. This is the dual leftover failure mode: balance needs both "never underflow" and "end empty".
What happens if you push onto a dynamic-array stack that is exactly at capacity?
It triggers a resize (allocate a bigger array, copy elements), which is a one-off cost; averaged over many pushes it stays amortized, so it does not overflow like a fixed array.
Does isEmpty ever give a false positive right after a pop that emptied the stack?
No. A correct pop restores top to -1 (array) or head to None (linked list), so isEmpty reads true precisely when the last element left.
Recall One-line self-test before moving on

Cover every answer and re-explain: order of read/shrink in pop, order of link/reassign in push, why counter ≠ stack, and both empty-stack boundaries (lone ) underflows, lone ( leaves leftovers). The single unifying idea ::: A stack touches only one end, so correctness reduces to getting operation order right (read-then-shrink, link-then-reassign) and boundaries right (empty and full).