Unit 4 · Moderate
Two abstract data types defined by a restriction rather than a capability. The restriction is the point: limiting which element is reachable is what makes each fit a specific class of problem.
What a strong answer looks like
A strong Unit 4 answer names the access discipline first, then explains why that discipline suits the problem.
Know
A stack pushes and pops at one end, so the most recent item leaves first. That ordering is what makes it match nesting, backtracking, and call stacks.
Apply
Reach for a stack whenever the problem involves matching pairs or undoing recent work.
Watch out
Treating a stack as a general list and indexing into it, which discards the guarantee that makes it useful.
Study move
Use a stack to check bracket balance and state both failure conditions.
Know
A queue adds at the rear and removes from the front, so items leave in arrival order. That fits scheduling and level-by-level exploration.
Apply
Reach for a queue whenever fairness or breadth-first order matters.
Watch out
Confusing the two disciplines under pressure; the traversal you get depends entirely on which you chose.
Study move
Describe how the same graph traversal changes when a stack is swapped for a queue.
Know
Both can be built on arrays or linked nodes. An array-backed queue needs circular indexing to avoid shifting every element on removal.
Apply
Wrap indices with modular arithmetic so vacated front slots are reused.
Watch out
A naive array queue that shifts on every dequeue, turning a constant-time operation linear.
Study move
Implement a circular queue and state what full and empty look like.
Know
A queue built from two stacks moves each element at most once, so although one transfer is linear, the average cost per operation is constant.
Apply
Argue amortised cost by counting total work across a sequence, not the worst single operation.
Watch out
Reporting the worst single operation as the cost, which misses the whole point of amortisation.
Study move
Explain why the two-stack queue is amortised constant despite an occasional linear step.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Implement a queue using two stacks and argue its amortised cost per operation.
