A stack is a collection where the last item you add is the first one you take out. This rule is called LIFO, which means Last In, First Out. Think of a pile of plates: you put a new plate on top, and you also take a plate from the top. Stacks are behind the undo button in an editor, the back button in a browser, and the way a program keeps track of function calls. In this lesson you will build a stack in Python with a list, add the push, pop and peek operations, and use it to reverse a string and check brackets.
Try every example in our online Python compiler.
Stack operations
Operation | What it does | List method |
|---|---|---|
push | Adds an item on top | append() |
pop | Removes and returns the top item | pop() |
peek | Looks at the top item without removing it | list[-1] |
is empty | Checks whether the stack has no items | len(list) == 0 |
size | Counts the items | len(list) |
The end of the list is the top of the stack. append() and pop() work at the end of a list, so both are fast.
A stack with a plain list
stack = []
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)
print(stack.pop())
print(stack)
print(stack[-1])
print(len(stack) == 0)Output:
[10, 20, 30]
30
[10, 20]
20
FalseThe last item pushed (30) is the first one popped. After the pop, 20 is on top.
Stack with functions (the exam style)
School and college exams often ask for push, pop and display as separate functions. They also handle two special cases: popping from an empty stack is called underflow, and a stack with a fixed size that is full is called overflow. A Python list can grow, so overflow does not happen unless you set a limit yourself.
stack = []
def push(stack, item):
stack.append(item)
def pop(stack):
if len(stack) == 0:
return 'Stack is empty (underflow)'
return stack.pop()
def peek(stack):
if len(stack) == 0:
return 'Stack is empty'
return stack[-1]
def display(stack):
for i in range(len(stack) - 1, -1, -1):
print(stack[i])
push(stack, 10)
push(stack, 20)
push(stack, 30)
display(stack)
print(peek(stack))
print(pop(stack))
print(pop(stack))
print(pop(stack))
print(pop(stack))
print(stack)Output:
30
20
10
30
30
20
10
Stack is empty (underflow)
[]The first three lines come from display(), which prints from the top down. Then peek() shows 30 without removing it, and the four pop() calls return 30, 20 and 10, and then the underflow message.
A Stack class
A class keeps the data and the operations together, and is a cleaner design.
class Stack:
def __init__(self):
self._items = []
def push(self, item):
self._items.append(item)
def pop(self):
if self.is_empty():
raise IndexError('pop from empty stack')
return self._items.pop()
def peek(self):
if self.is_empty():
raise IndexError('peek from empty stack')
return self._items[-1]
def is_empty(self):
return len(self._items) == 0
def size(self):
return len(self._items)
s = Stack()
s.push('a')
s.push('b')
s.push('c')
print(s.size(), s.peek(), s.pop(), s.size(), s.is_empty())
s.pop()
s.pop()
print(s.is_empty())
try:
s.pop()
except IndexError as e:
print('IndexError:', e)Output:
3 c c 2 False
True
IndexError: pop from empty stackThe class raises an IndexError when you pop from an empty stack, and the try/except block catches it. A single underscore in the attribute name is a signal that it is meant to be used inside the class only.
Example 1: reverse a string
Because a stack gives items back in the opposite order, it reverses a string naturally.
def reverse_text(text):
stack = []
for ch in text:
stack.append(ch)
result = ''
while stack:
result += stack.pop()
return result
print(reverse_text('Python'))Output:
nohtyPThe loop pushes every letter, and then pops them all, so the last letter comes out first. (In real code, text[::-1] is shorter, but this shows how a stack works.)
Example 2: check balanced brackets
A classic use of a stack is to check that every opening bracket has a matching closing bracket, in the right order.
def is_balanced(expression):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in expression:
if ch in '([{':
stack.append(ch)
elif ch in ')]}':
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
for expr in ['(a+b)*[c-d]', '((a+b)', '{[()]}', '([)]']:
print(expr, is_balanced(expr))Output:
(a+b)*[c-d] True
((a+b) False
{[()]} True
([)] FalseEvery opening bracket goes on the stack. Every closing bracket must match the bracket on top. At the end, the stack must be empty. In ‘((a+b)’ one bracket is left open, and in ‘([)]’ the order is wrong.
Where stacks are used
- The undo and redo feature of an editor
- The back button of a browser
- Checking brackets in a compiler
- Evaluating expressions, and converting infix to postfix
- The call stack that keeps track of function calls, which is why a function that calls itself forever raises a RecursionError
Using collections.deque
A list is fine for a stack. For very large stacks, or when you also need to remove from the front, Python offers collections.deque, which has fast append() and pop() at both ends. For learning and exams, a list is what you need.
Common mistakes
- Popping from an empty stack. Always check whether the stack is empty first, or catch the error.
- Using pop(0). That removes the first item, which is a queue behaviour. For a stack, use pop() with no argument.
- Confusing peek and pop. peek only looks at the top item, and pop removes it.
- Inserting at the front with insert(0, item), and then popping from the end. The order is then wrong.
Practice questions
- Push the numbers 1 to 5, and then pop them all and print them.
- Write a function that returns the top item of a stack without removing it.
- Use a stack to check whether a word is a palindrome.
- Check whether the expression ‘{[(a+b)*c]-d}’ is balanced.
- Add a maximum size to the Stack class, and raise an error on overflow.
Summary
- A stack works on the LIFO rule: the last item in is the first item out.
- With a list, push is append(), pop is pop(), and peek is the index -1.
- Check for underflow before you pop.
- Stacks are used for undo, bracket checking, expression evaluation and function calls.