20 Python Chapter 8.4 — stacks

Python Chapter 8.4 — stacks

← Index · Solutions

Priority key · Priorities guide emphasis; they do not remove taught scope.

Exam recall

LIFO; push/pop at the top. State whether top is last occupied or next free. For postfix, pop right operand before left.

Stack behaviour priority/high

Push A, then B, then C:
       ┌───┐
top →  │ C │ ← next to be popped
       ├───┤
       │ B │
       ├───┤
       │ A │
       └───┘
Pop C → B becomes top. Push D → D becomes top.

Only the top is directly available through stack operations. Removing an arbitrary middle item does not follow the stack interface even if the underlying Python list technically permits it.

A stack is last in, first out (LIFO). Push adds at the top; pop removes/returns the top; peek reads it without removal. An empty pop is underflow. A fixed-capacity full push is overflow. Applications include nested function calls, undo histories and bracket matching because the most recently unfinished action is handled first.

Separate the ADT from the representation. A Python list can act as a stack using append/pop at its end. In a fixed-array implementation, preallocate capacity and maintain top. In a linked implementation, the head can be the top, making push/pop link updates at the head.

Worked implementation — fixed array priority/high

Convention: top is the index of the last live item; initially −1. Size is top+1. Full means top == capacity - 1. This interface raises IndexError on invalid operations; adapt to return False/None if a paper specifies that contract instead.

class ArrayStack:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.data = [None] * capacity
        self.top = -1  # Last occupied index; -1 means no occupied position.
 
    def push(self, item):
        if self.top == len(self.data) - 1:  # Reject before advancing/writing.
            raise IndexError("stack full")
        self.top += 1  # Move to the next free cell before storing.
        self.data[self.top] = item
 
    def pop(self):
        if self.top == -1:
            raise IndexError("stack empty")
        item = self.data[self.top]  # Save the current top before changing it.
        self.data[self.top] = None
        self.top -= 1  # Logical membership ends at the new top.
        return item
 
    def peek(self):
        if self.top == -1:
            raise IndexError("stack empty")
        return self.data[self.top]

Capacity 3: push A → top 0; push B → top 1; pop returns B and top becomes0; push C → logical stack A,C with C on top. Clearing a removed cell is convenient but top determines live contents. Stale array values outside the live region are not stack members.

For a linked stack: push creates a node whose next is the old top, then moves top to it. Pop saves top.data, moves top to top.next, and returns saved data. Check empty before dereferencing top.

The array top is an index; linked top is a node reference. Both represent the same LIFO interface. A linked push allocates a node instead of advancing an array index; do not mix their empty tests or assignments.

Derive a linked stack from head insertion/removal

Use Node from Chapter 19. Unlike a linked queue, this stack does not need a rear reference: both push and pop happen at the same end.

class LinkedStack:
    def __init__(self):
        self.top = None
 
    def push(self, item):
        new = Node(item, self.top)  # New node points to the entire old stack.
        self.top = new             # It becomes the first node to remove.
 
    def pop(self):
        if self.top is None:
            raise IndexError("stack empty")
        item = self.top.data       # Save data before bypassing this node.
        self.top = self.top.next   # Removing the singleton makes top None.
        return item
 
    def peek(self):
        if self.top is None:
            raise IndexError("stack empty")
        return self.top.data       # Preserve links and the top reference.

For push A then push B, the chain is top→B→A→None. Pop returns B and changes top to A. There is no array capacity/full test in this implementation, although allocation is still limited by available memory.

Stack applications priority/medium

Bracket matching: push each opening bracket; for each closing bracket require a matching top and pop it. At the end the stack must be empty. A matching final count alone is insufficient: )( has equal counts but wrong order.

Postfix evaluation: push operands. For an operator, pop the right operand first and then the left, compute left operator right, and push the result. Example 8 3 - 2 * → (8−3)×2 =10. Swapping operands breaks subtraction/division.

Infix to postfix: output operands; hold operators on a stack. Before pushing an operator, pop/output higher-precedence operators, plus equal-precedence ones when the incoming operator is left-associative. Parentheses delimit popping and are omitted from the result. Exponentiation associativity needs the specified convention; do not blindly pop equal precedence for a right-associative operator. Example (2+3)*4 → 2 3 + 4 *.

Practice

Exam focus: HCI 2022 modified Q7 includes array and linked stacks; HCI 2024 Q4 and 2025 Q7 connect stack behaviour to recursion. Infix/postfix applications remain included from school §8.4. Use the original 2022 modified Q7, PDF pp.5–6 for its supplied pointer convention and requested operations.

Approach: write whether top means last occupied position or next free position → derive empty/full → order the read/write and pointer movement → trace one item and an invalid operation. For postfix, label the first popped value right operand, especially for subtraction/division.

20A — adapted from HCI 2022 modified Q7. Capacity 3, top initially −1: push 4, push 7, pop, push 2, push 9. Give the popped value, final live contents bottom-to-top, top and whether another push is possible.

20B — original. Write balanced(text) checking only parentheses ( and ), ignoring other characters, using a stack. Explain why an empty string is balanced and ")(" is not.

20C — original, extra practice. Evaluate postfix 10 4 2 * -. Show the stack after each token. Convert 10 - 4 * 2 to postfix and state which popped operand is used on the left of subtraction.

Hints

20B: reject a closing parenthesis when the stack is empty. 20C: write stacks bottom-to-top consistently.

Revision checklist

• 20.1 Explain LIFO and justify a stack for a scenario.
• 20.2 Trace push, pop, peek and length while identifying the logical top.
• 20.3 Implement a fixed-capacity array stack with a consistent pointer convention.
• 20.4 Implement a linked stack using insertion/deletion at the head.
• 20.5 Handle overflow and underflow without corrupting state.
• 20.6 Distinguish physical array contents from the logical stack after a pop.
• 20.7 Use a stack for the school-taught bracket-matching and expression tasks.
• 20.8 Trace postfix evaluation with correct operand order and infix-to-postfix conversion as taught.
• 20.9 Explain how function calls and recursion use a stack.
• 20.10 Respect a supplied ADT’s allowed operations and return contract.

Visual revision mindmap

Open this mindmap and its text version · All 21 mindmaps

Your mindmap framework

Centre: Python Chapter 8.4 — stacks. Build the six branches below. For each subbranch, add a short definition, a labelled sample and one exam trap from memory; then check the chapter.

flowchart LR
    C["20 • Revision map"]
    C --> B0["Stack contract"]
    C --> B1["Array implementation"]
    C --> B2["Linked implementation"]
    C --> B3["Applications"]
    C --> B4["Expression workflow"]
    C --> B5["Visual checks and mistakes"]

• Stack contract

  • LIFO.
  • Push adds top; pop removes/returns top.
  • Peek reads without removal.
  • Match question’s output and failure convention.

• Array implementation

  • Preallocated storage and logical top.
  • Last-occupied convention: top starts −1.
  • Size = top + 1; full at capacity − 1.
  • Guard before update; save removed value before changing top.

• Linked implementation

  • Top is node reference.
  • Push at head.
  • Pop moves top to next.
  • Singleton removal leaves null; finite memory without fixed array capacity.

• Applications

  • Nested calls and recursion.
  • Undo most recent action.
  • Bracket matching: order and type matter.
  • Postfix evaluates; infix conversion uses precedence/associativity.

• Expression workflow

  • Operand: push.
  • Operator: pop right then left.
  • Apply operation and push result.
  • Parentheses and equal-precedence handling for conversion.

• Visual checks and mistakes

  • Draw bottom-to-top contents after each operation.
  • Separate stale cells from live items.
  • Test overflow, underflow, singleton and peek.
  • Avoid: first pop as left operand; balanced counts imply balanced brackets.

Close the notes and test the map: explain one branch aloud, sketch its sample, then answer a linked practice question. Mark any missing link to revisit.

Source trail

9569 §2.1.1; school Data Structures pp.14–30, Tutorial 8B.

HCI 2022 Q7; 2023 Q7(c–d); 2024 Q4(b–c); 2025 Q7(c–d).

Source guide records provenance and original-paper locations.