Lesson 4.1
Stack Behavior
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.
Lessons and exercises
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.
Lesson 4.2
Queue Behavior
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.
Lesson 4.3
Implementation Choices
Both can be built on arrays or linked nodes. An array-backed queue needs circular indexing to avoid shifting every element on removal.
Lesson 4.4
Amortised Reasoning
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.
Need help with this topic?
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic