Stack

The essentials

A stack is a linear data structure in which items are added and removed at only one end, called the top. The last item added is the first item removed, so a stack follows LIFO (Last In, First Out). A pile of plates or books is an everyday example.

Key points

• PUSH: adds an element at the top.
• POP: removes and returns the top element.
• PEEK (top): returns the top element without removing it.
• isEmpty: checks whether the stack has no elements.
• Overflow: trying to push into a full stack (of fixed size). Underflow: trying to pop from an empty stack.
• In Python, a list can act as a stack with the end of the list as the top: stack.append(x) pushes, stack.pop() pops, stack[-1] peeks, and len(stack) == 0 tests emptiness. A Python list grows as needed, so overflow is usually not a concern, but underflow must be checked before popping.
• Applications: undo in editors, the browser back button, reversing a string, checking matched parentheses, function calls and evaluating expressions.

Exam tips

• Trace operations step by step. Example: push 10, push 20, pop, push 30, push 40, pop gives the stack [10, 30] with 30 on top.
• When reversing, items come out in the reverse of the order in which they went in.

Common mistakes

• Using pop(0) for a stack. That removes from the front, which is queue behaviour.
• Forgetting to check for an empty stack before popping, causing IndexError in Python.