4.2.3.1 - Stacks and their operations (Python)
Use last-in, first-out storage, trace stack state, and implement push, pop and peek with correct empty and full checks in Python.
LIFO and stack state
A stack restricts access to one end, called the top, so the newest stored item is the first one removed.
Stack
A last-in, first-out (LIFO) abstract data type supporting push to add at the top, pop to remove from the top, and peek/top to inspect the top without removing it.
If actions A, B, C are pushed in that order, C is on top and is popped first. An undo system uses this order because the latest action is reversed before earlier ones. Recursive calls also create stack frames: the latest unfinished call must return before the call that invoked it. A queue instead serves the oldest waiting item, so exchanging these types changes the program's behavior.
A dynamic Python implementation can store bottom-to-top items in a list. A static implementation preallocates an array and keeps a top index. In this lesson's static convention, top is the next free slot, also the number of items, rather than the index of the current top element. Thus the current top item is at data[top - 1]. Other texts use −1 for empty and make top point to the last occupied slot; both conventions work, but their checks must not be mixed.
Push, pop and peek
Each operation changes only the state required by its meaning, and peek leaves the stack unchanged.
For a Python list stack, stack.append(value) pushes; stack.pop() removes and returns the last item; stack[-1] peeks. For the static next-free convention, push writes data[top] then increments top. Pop decrements top, reads that slot and can clear it. Peek reads data[top - 1] without changing top or the array. Clearing a removed slot releases an unnecessary reference; the logical boundary is top, even if an old value remains beyond it.
Peek does not remove
{"code":"stack = []\nfor item in ["open", "edit", "save"]:\n stack.append(item)\nprint(stack[-1])\nprint(stack.pop())\nprint(stack)\nprint(stack[-1])","instructions":"Predict all four lines, then run. Replace the first peek print(stack[-1]) with print(stack.pop()). Predict the new remaining stack and final peek, then run. Explain why two pops remove two actions while a peek and a pop remove only one.","files":[],"original_filename":"main.py","runtime_profile":"python-console-v1","file_mode":"fresh"}
The original prints save, save, ['open', 'edit'], edit. The modified program prints save, edit, ['open'], open. Indexing observes a value; pop also updates the list.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account