Chapter 9: Stack ADT

1. What exactly is a stack?

Think of a stack as a single pile of dinner plates:

You always put a new plate on the very top.
You always take the next plate from the very top.

Because the last plate you placed is the first plate you remove, we call it LIFO - Last-In, First-Out.

2. Core operations (the everyday "plate moves")

Operation	Plain-English meaning	Code method
push (item)	Put a new item on top of the pile	`stack.push(x)`
pop ()	Remove + return the item on top	`stack.pop()`
top ()	Look at the top item without removing it	`stack.top()`
isEmpty ()	Is the pile empty? (`True/False`)	`stack.isEmpty()`
len(stack)	How many items are in the pile?	`len(stack)`

All of these run in constant time, O(1), because we only ever touch the very top element.

3. A quick walk-through

start:   []
push 1 → [1]
push 2 → [1, 2]
push 3 → [1, 2, 3]   (top is 3)

pop    → returns 3,   stack is now [1, 2]
top    → returns 2,   stack stays [1, 2]

Notice how we never "dig" into the middle-only the top moves.

4. Why stacks are useful

Real-world example	How a stack helps
Undo / redo in editors	Each change is pushed; undo just pops the latest action.
Browser back button	Pages you visit get pushed; hitting Back pops the most recent page.
Function calls in any program	When a function is called, its info (arguments, local variables, return address) is pushed onto the call stack; it pops when the function finishes.
Expression evaluation & parsers	Converting or evaluating arithmetic or programming expressions often uses an operator/operand stack.
Backtracking (e.g., solving a maze)	Push your current position; if a path fails, pop to backtrack.

5. Under the hood: two common ways to build one

Python list (what the sample code uses) Pros: already resizable, append & pop from the end are O(1). Cons: may over-allocate some extra memory internally, but that's usually fine.
Linked list Pros: each node only stores its own data + pointer, so memory grows exactly with the stack size; never reallocates a big chunk. Cons: a tiny bit more code, one small pointer stored per item.

Either way, operations remain O(1).

7. `Stack` class

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """Add an item to the top of the stack"""
        self.items.append(item)
    
    def pop(self):
        """Remove and return the top item from the stack"""
        if not self.isEmpty():
            return self.items.pop()
        return None
    
    def top(self):
        """Return the top item without removing it"""
        if not self.isEmpty():
            return self.items[-1]
        return None
    
    def isEmpty(self):
        """Check if the stack is empty"""
        return len(self.items) == 0
    
    def __len__(self):
        """Return the number of items in the stack"""
        return len(self.items)

# Example usage
stack = Stack()

# Push items
stack.push(1)
stack.push(2)
stack.push(3)
print("Stack after pushes:", stack.items)  # [1, 2, 3]

# Check top
print("Top item:", stack.top())  # 3

# Pop items
print("Popped item:", stack.pop())  # 3
print("Stack after pop:", stack.items)  # [1, 2]

# Check length and emptiness
print("Stack length:", len(stack))  # 2
print("Is empty?", stack.isEmpty())  # False

# Pop all items
stack.pop()
stack.pop()
print("Is empty?", stack.isEmpty())  # True

6. Take-home summary

A stack is just a controlled list where you only interact with one end.
Remember the mantra LIFO: Last-In, First-Out.
Five basic moves: push, pop, top, isEmpty, length.
Great for undo features, function calls, parsing, and any scenario where you need to "backtrack" or reverse recent steps.

If you're comfortable with the dinner-plate picture, you already understand stacks!

Data Structures and Object-Oriented Programming