Stack in Python: Implementation and Uses

A stack is a collection where you can only add and remove items at one end, the top. The last item in is the first item out, which is called LIFO (last in, first out). Think of a stack of plates: you put a plate on top, and you take the top plate off. In Python you rarely need a special class. A plain list works as a stack: append() to push and pop() to pop, both in O(1) time.

This guide covers the operations, a clean Stack class, and the problems where a stack is the right tool: matching brackets, undo, postfix expressions and the “next greater element” family. All the output shown is real.

Stack basics with a list

Push with append. Pop with pop(), which removes and returns the last item. Peek at the top with [-1]. Check for empty with not stack:

stack = []
stack.append("a")
stack.append("b")
stack.append("c")
print(stack)
print(stack.pop())
print(stack[-1])
print(len(stack), not stack)

Output

['a', 'b', 'c']
c
b
2 False

Popping an empty stack is an error, so check first if the stack might be empty:

stack = []
try:
    stack.pop()
except IndexError as e:
    print(type(e).__name__, e)

Output

IndexError pop from empty list

Always work at the end of the list. Using insert(0, x) and pop(0) would also behave like a stack, but each of them shifts every item, which makes them O(n) (see Time Complexity of Python Data Structures).

A Stack class

In interviews and larger programs it is common to wrap the list in a class, so the code says what it means and only the stack operations are available:

class Stack:
    def __init__(self):
        self._items = []

    def push(self, x):
        self._items.append(x)

    def pop(self):
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        if not self._items:
            raise IndexError("peek from empty stack")
        return self._items[-1]

    def is_empty(self):
        return not self._items

    def __len__(self):
        return len(self._items)

s = Stack()
for x in [1, 2, 3]:
    s.push(x)
print(s.peek(), len(s))
print(s.pop(), s.pop())
print(s.is_empty(), len(s))

Output

3 3
3 2
False 1

The class hides the list behind push, pop and peek, and raises a clear error when the stack is empty. (Classes are covered in Python Classes and Objects for Beginners.)

Use 1: matching brackets

Is ([]{}) valid but ([)] not? Each opening bracket is pushed. Each closing bracket must match the most recent opening one still waiting, which is exactly the top of the stack:

def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

for t in ["([]{})", "([)]", "((", "", "a(b)c"]:
    print(repr(t), is_balanced(t))

Output

'([]{})' True
'([)]' False
'((' False
'' True
'a(b)c' True

At the end the stack must be empty, otherwise some bracket was never closed ("(("). Any problem with nesting, such as HTML tags or nested function calls, works the same way.

Use 2: undo and redo

Every editor uses two stacks. Each change pushes the previous state on the undo stack. Undo pops it, and pushes the current state on the redo stack:

text = ""
undo, redo = [], []

def type_(s):
    global text
    undo.append(text)
    redo.clear()
    text += s

def do_undo():
    global text
    if undo:
        redo.append(text)
        text = undo.pop()

def do_redo():
    global text
    if redo:
        undo.append(text)
        text = redo.pop()

type_("Hello")
type_(" World")
print(text)
do_undo()
print(text)
do_redo()
print(text)

Output

Hello World
Hello
Hello World

The most recent change is always the first one undone, which is LIFO. A browser’s back button works the same way.

Use 3: evaluating expressions

In postfix (reverse Polish) notation the operator comes after its numbers: 3 4 + means 3 plus 4. A stack evaluates it with no brackets and no precedence rules. Push numbers. When you meet an operator, pop two, calculate and push the result:

def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in ("+", "-", "*", "/"):
            b = stack.pop()
            a = stack.pop()
            if t == "+":
                stack.append(a + b)
            elif t == "-":
                stack.append(a - b)
            elif t == "*":
                stack.append(a * b)
            else:
                stack.append(a / b)
        else:
            stack.append(float(t))
    return stack[0]

print(eval_rpn("3 4 + 2 *".split()))
print(eval_rpn("5 1 2 + 4 * + 3 -".split()))

Output

14.0
14.0

Both expressions equal 14: (3 + 4) × 2 and 5 + (1 + 2) × 4 − 3. Note the order when popping: the second pop is the left operand, which matters for - and /.

Use 4: next greater element (monotonic stack)

A very common interview pattern: for each item, find the next item to its right that is larger. Keep a stack of positions whose answer is still unknown. Each new number resolves every waiting position with a smaller value:

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

print(next_greater([2, 1, 2, 4, 3]))

Output

[4, 2, 4, -1, -1]

The stack stays sorted from big to small, hence “monotonic”. Each index is pushed once and popped once, so the whole thing is O(n), even though it has a loop inside a loop. The same idea answers “how many days until a warmer temperature”:

def daily_temps(temps):
    answer = [0] * len(temps)
    stack = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

print(daily_temps([73, 74, 75, 71, 69, 72, 76, 73]))

Output

[1, 1, 4, 2, 1, 1, 0, 0]

Use 5: a stack that knows its minimum

How would you get the smallest item in a stack in O(1)? Keep a second stack that records the minimum so far at every level:

class MinStack:
    def __init__(self):
        self.stack = []
        self.mins = []

    def push(self, x):
        self.stack.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))

    def pop(self):
        self.mins.pop()
        return self.stack.pop()

    def get_min(self):
        return self.mins[-1]

m = MinStack()
for x in [5, 3, 7, 3, 8]:
    m.push(x)
print(m.get_min())
m.pop()
m.pop()
print(m.get_min())
m.pop()
m.pop()
print(m.get_min())

Output

3
3
5

When an item is popped, its minimum record goes with it, so the previous minimum is right there again.

The call stack and recursion

Python itself uses a stack. Every function call pushes a frame (its variables and where to return to), and returning pops it. That is why recursion works, and why a function that never stops calling itself runs out of room:

def countdown(n):
    return countdown(n - 1)

try:
    countdown(10)
except RecursionError as e:
    print(type(e).__name__)

Output

RecursionError

Python stops it with a RecursionError once the stack gets too deep (about a thousand calls by default). Any recursive algorithm can be rewritten with an explicit stack of your own, which is how iterative depth-first search works (see Graphs in Python: Adjacency List, BFS and DFS). More on recursion in Recursion in Python Explained Simply.

Time complexity

A collections.deque also works as a stack (append and pop at the right end) and has the same costs:

from collections import deque

d = deque()
d.append(1)
d.append(2)
print(d.pop(), d.pop())

Output

2 1

There is also queue.LifoQueue, but it exists for passing data safely between threads and is slower. For ordinary code, use a list.

Common mistakes

• Popping an empty stack. Check if stack: first, or handle IndexError.
• Working at the front of the list. Use the end. pop(0) is O(n).
• Forgetting the leftovers. In bracket matching, an empty stack at the end is part of the answer.
• Popping in the wrong order. For non-commutative operators, the first pop is the right operand.
• Mixing up stack and queue. A stack is LIFO. If you need first-in-first-out, use a deque (see Queue and Deque in Python Explained).

Try it yourself

Work out each answer first, then open the solution.

1. Reverse the order of the words in "one two three" using a stack.

def reverse_words(sentence):
    stack = sentence.split()
    out = []
    while stack:
        out.append(stack.pop())
    return " ".join(out)

print(reverse_words("one two three"))

three two one

2. Evaluate the postfix expression 2 3 4 * +.

def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in ("+", "*"):
            b, a = stack.pop(), stack.pop()
            stack.append(a + b if t == "+" else a * b)
        else:
            stack.append(float(t))
    return stack[0]

print(eval_rpn("2 3 4 * +".split()))

14.0

3. Remove adjacent duplicate letters repeatedly from "abbaca".

def remove_dups(s):
    stack = []
    for ch in s:
        if stack and stack[-1] == ch:
            stack.pop()
        else:
            stack.append(ch)
    return "".join(stack)

print(remove_dups("abbaca"))

ca

4. Why is O(1) for both append and pop() important for a stack?

Run these in our free Python compiler.

Frequently asked questions

What is a stack in Python?

A stack is a last-in, first-out collection. Python has no separate stack type: you use a list, with append() to push and pop() to pop.

What does LIFO mean?

Last in, first out: the most recently added item is the first one removed, like a pile of plates.

How do I implement a stack in Python?

Use a list for the simplest version, or wrap a list in a Stack class with push, pop, peek and is_empty methods. collections.deque works as well.

What is the difference between a stack and a queue?

A stack removes the newest item first (LIFO). A queue removes the oldest item first (FIFO). Use a list for a stack and a deque for a queue.

What is a stack overflow?

It happens when the call stack runs out of space, usually because of recursion that goes too deep or never stops. In Python this raises a RecursionError.

Where are stacks used in real life?

Undo and redo in editors, the browser back button, matching brackets in compilers and editors, evaluating expressions, and the call stack that runs your program.

Related reading

• Queue and Deque in Python Explained – the first-in-first-out partner.
• Recursion in Python Explained Simply – the call stack in action.
• Graphs in Python: Adjacency List, BFS and DFS – DFS with an explicit stack.
• Time Complexity of Python Data Structures – why the end of a list is the right end.