Stack

You already use stacks every day without naming them. When you stack plates after dinner, the last plate you put on top is the first one you take off. When you press Undo in a text editor, the most recent change is the one that gets reversed first. When you press Back in a browser, you return to the page you visited most recently. Every one of these follows the same rule: last in, first out (LIFO).

A stack is the computer-science name for that rule. It is an Abstract Data Type — a "shape" for data plus the operations allowed on it. The clever part is that your programming language does not give you a ready-made stack, so you build one yourself out of an array plus an integer pointer.

Python has no built-in "stack" type, so we build one from a list of a fixed size. We need three things:

• MAX_SIZE — a constant saying how many items the stack can hold.
• stack — the array (list) itself, sized to that constant.
• top_pointer — an integer that says which index currently holds the top item.

MAX_SIZE = 5                       # the stack can hold 5 items
stack = [None] * MAX_SIZE          # the array that stores the data
top_pointer = -1                   # -1 means the stack is empty

Try the stack yourself. Set MAX_SIZE, enter a value, and click Push or Pop. Watch the top_pointer climb and fall, and try to trigger overflow and underflow. Use the playback controls to step through the code.

1MAX_SIZE = 5
2if top_pointer == MAX_SIZE - 1:
3    print("Stack overflow")
4    top_pointer = top_pointer + 1
5    stack[top_pointer] = new_item
6if top_pointer == -1:
7    print("Stack underflow")
8    item = stack[top_pointer]
9    top_pointer = top_pointer - 1
10    return item

push() adds a new item to the top of the stack. The order is critical: check full → increment pointer → store item. Never store first then move the pointer, and never skip the full-check.

def push(new_item):
    global top_pointer
    if top_pointer == MAX_SIZE - 1:      # is the stack full?
        print("Stack overflow - cannot push")
    else:
        top_pointer = top_pointer + 1     # move the pointer up
        stack[top_pointer] = new_item       # store the item there

pop() removes and returns the top item. The order is: check empty → read item → decrement pointer → return item. You must read the item BEFORE decrementing, or the pointer no longer points at it.

def pop():
    global top_pointer
    if top_pointer == -1:                  # is the stack empty?
        print("Stack underflow - nothing to pop")
        return None
    else:
        item = stack[top_pointer]            # read the top item
        top_pointer = top_pointer - 1       # move the pointer down
        return item                          # give it back to the caller

These three tiny helpers make push and pop readable. Writing if is_full(): instead of if top_pointer == MAX_SIZE - 1: reads like English and is harder to get wrong.

def is_empty():
    return top_pointer == -1

def is_full():
    return top_pointer == MAX_SIZE - 1

def peek():
    if is_empty():
        return None
    return stack[top_pointer]

A trace shows the stack state and top_pointer after each operation. Remember: push increments the pointer, pop decrements it.

# Trace: start empty, then push 7, push 3, pop, push 9

start    top_pointer = -1   stack = []
push 7   top_pointer = 0    stack = [7]
push 3   top_pointer = 1    stack = [7, 3]
pop      top_pointer = 0    (3 removed) -> returns 3
push 9   top_pointer = 1    stack = [7, 9]

A text editor keeps the last few text changes on a stack so the user can undo them. The most recent change must be undone first. The stack can hold up to 10 changes.

Fifteen exam-style stack tasks. Each shows only the question — click Hint for the thought process, or Help for the worked solution.