Stack

A stack is a last-in-first-out (LIFO) data structure with two core operations: push adds an element to the top, and pop removes the most recently added one. Every operation touches a single end — no shifting, no scanning, no middle access — so on this lesson's Python list both run in amortized O(1) time.

Picture a stack of plates in a cafeteria. You put a clean plate on top; you take the next plate off the top. Nobody — nobody sane — pulls a plate from the middle. That one constraint is the whole data structure, and it is exactly what you want whenever a program must remember what it was doing and resume in reverse order: function calls, undo history, matching nested brackets, depth-first traversal.

How a Stack Works

The displayed code implements a bounded stack: a Python list data plus a max capacity. push(val) first checks len(self.data) >= self.max — if the stack is full, it raises a Stack Overflow exception; otherwise it appends val to the end of the list. pop() checks for emptiness — popping an empty stack raises Stack Underflow — and otherwise removes and returns the last element.

The "top" of the stack is just the last index of the list. append and list.pop() both work at that end, which is why each costs O(1) amortized. You never reach below the top plate, so you never pay for the plates underneath.

One honesty note about the bound. Overflow is genuinely part of this lesson's code — embedded systems use bounded stacks all the time — but it is not part of the LIFO contract itself; a stack on a plain Python list grows until memory runs out. And the capacity slider's 3–10 range is purely a visualization limit: the canvas fits about ten cells, and that says nothing about stacks.

Stack Operations Step by Step

The lesson starts from the default state: an empty stack with capacity 8. Drive it with the Push and Pop buttons and the trace below plays out exactly.

1. push(3) — guard passes (0 < 8), stack becomes [3]. Top index is 0.
2. push(7) — stack becomes [3, 7]. The new cell lands above the old top.
3. push(1) — stack becomes [3, 7, 1].
4. pop() — returns 1, the last value in. Stack is [3, 7]. Note the reversal: last in, first out.
5. pop() — returns 7. Stack is [3].
6. push(9) — stack becomes [3, 9]. The slot 7 vacated is reused.
7. pop() twice — returns 9, then 3. The stack is empty again; one more pop() raises underflow.

The dual failure is worth provoking once: a ninth push into the capacity-8 stack raises overflow before anything is appended — state never changes on a failed operation.

In the player, the stack draws as a vertical container with walls on three sides; the open top is the only door, so pushes drop in and pops lift out through it. The header tracks size and the current top value, vanishing while the stack is empty so you never read stale state. The visual is reinforcement — the trace above is the complete record.

Time and Space Complexity

The top-only interface plus a list that works at its end is what gives these costs; judge the rule and the storage together. A growable list occasionally resizes and copies every element, which is why push is amortized rather than worst-case O(1).

Edge Cases

• Push to a full stack — raises overflow; the stack is unchanged.
• Pop from an empty stack — raises underflow. Guard with an emptiness check or catch the exception.
• Single element — push then pop round-trips the same value; size goes 0 → 1 → 0.
• Duplicates — perfectly legal. A stack is not a set; it records order, not membership.

Common Mistakes

• Confusing pop with peek. pop mutates. Calling it "just to look" destroys the top unless you keep the return value. Read non-destructively with data[-1].
• Pushing and popping at different ends. Push at the back, pop at the front, and you have built a queue. Same plates, opposite discipline.
• Skipping the empty check. An unguarded pop() crashes in most languages and returns undefined in JavaScript — a bug that surfaces far from the pop site.
• Indexing into the middle. Once callers read data[k], the LIFO invariant has leaked; reach for a list or deque instead.
• Not noticing the call stack. Every function call is a push, every return a pop. The "stack overflow" your recursion just hit is this lesson's overflow beat, at runtime scale.