Skip to content
Laviyx Learn

Try

DSA course menu

Stacks in Python: LIFO, Balanced Brackets and Expression Evaluation

Learn the stack data structure: last in, first out, push and pop in O(1), stacks with Python lists and linked lists, checking balanced brackets, evaluating postfix expressions and the min stack.

Beginner10 min readUpdated
On this page

A stack is a collection where the last item added is the first one removed: last in, first out (LIFO). Think of a stack of plates: you put plates on top and take them from the top.

OperationMeaningCost
push(x)put x on topO(1)
pop()remove and return the topO(1)
peek()look at the top without removing itO(1)
is_empty()is there anything left?O(1)

Your browser's Back button, an editor's Undo, and the call stack that runs recursive functions all work this way.

A Python list is a stack#

append and pop() both work at the end of a list, which is O(1):

Python
stack = []
stack.append("page1")     # push
stack.append("page2")
stack.append("page3")
print(stack[-1])          # peek
print(stack.pop())        # pop
print(stack.pop())
print(stack, len(stack) == 0)
Output
page3
page3
page2
['page1'] False

Never use the front of a list as the top: insert(0, x) and pop(0) are O(n).

A stack built on a linked list#

The same operations on a linked list: push and pop at the head, both O(1), and no resizing ever.

Python
class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next

class Stack:
    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, value):
        self.top = Node(value, self.top)
        self.size += 1

    def pop(self):
        if self.top is None:
            raise IndexError("pop from empty stack")
        value = self.top.value
        self.top = self.top.next
        self.size -= 1
        return value

    def peek(self):
        return None if self.top is None else self.top.value

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

Balanced brackets#

Is every opening bracket closed by the right kind, in the right order? A stack remembers which brackets are still open; the most recent one must close first.

Python
def 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            # anything left open is unbalanced

for t in ["(a[b]{c})", "([)]", "((", "print(len(x))"]:
    print(t, balanced(t))
Output
(a[b]{c}) True
([)] False
(( False
print(len(x)) True

Evaluating postfix expressions#

In postfix (reverse Polish) notation the operator comes after its operands: 3 4 + 2 * means (3 + 4) × 2. A stack evaluates it in one pass: push numbers; on an operator, pop two numbers, apply it, and push the result.

Python
def eval_postfix(expr):
    stack = []
    for token in expr.split():
        if token in "+-*/":
            b = stack.pop()          # the second operand is on top
            a = stack.pop()
            if token == "+": stack.append(a + b)
            elif token == "-": stack.append(a - b)
            elif token == "*": stack.append(a * b)
            else: stack.append(a / b)
        else:
            stack.append(float(token))
    return stack.pop()

print(eval_postfix("3 4 + 2 *"))
print(eval_postfix("5 1 2 + 4 * + 3 -"))
Output
14.0
14.0

The order of a and b matters for - and /: 10 2 - is 10 − 2, so the item popped first is the right-hand operand.

Min stack: the minimum in O(1)#

Support push, pop and get_min(), all in O(1). Store, next to each value, the minimum of everything at or below it:

Python
class MinStack:
    def __init__(self):
        self.items = []          # pairs of (value, min so far)

    def push(self, x):
        current_min = min(x, self.items[-1][1]) if self.items else x
        self.items.append((x, current_min))

    def pop(self):
        return self.items.pop()[0]

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

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

Common mistakes#

Practice#

Practice exercise

Write simplify_path(path) that simplifies a Unix-style path: . means "this folder", .. means "go up one folder" (ignored at the root), and repeated slashes count as one. "/home//user/./docs/../photos/" becomes "/home/user/photos".

Show hint

Split on /. Use a stack of folder names: skip empty parts and ., pop on .. (if the stack is not empty), and push anything else. Join with / at the end.

Show solution
Python
def simplify_path(path):
    stack = []
    for part in path.split("/"):
        if part in ("", "."):
            continue
        if part == "..":
            if stack:
                stack.pop()
        else:
            stack.append(part)
    return "/" + "/".join(stack)

print(simplify_path("/home//user/./docs/../photos/"))
print(simplify_path("/../"))
print(simplify_path("/a/b/../../c"))
Output
/home/user/photos
/
/c

Key takeaway#

Next: first in, first out, in Queues and Deques.

Finished this lesson?

Related lessons

DSAQueues and Deques in Python: FIFO, collections.deque and Circular QueuesLearn the queue data structure: first in, first out, why list.pop(0) is slow, collections.deque, a circular array queue, queues from two stacks and the sliding window maximum with a deque.Beginner8 min readDSAMonotonic Stack Explained: Next Greater Element and MoreLearn the monotonic stack pattern: next greater element, daily temperatures, stock span and largest rectangle in a histogram, each solved in O(n) by keeping a stack in sorted order.Intermediate7 min readDSARecursion for DSA: Base Cases, Call Stack and MemoizationUnderstand recursion for data structures and algorithms: base and recursive cases, how the call stack works, recursion trees, the cost of naive Fibonacci, and memoization with lru_cache.Beginner9 min readDSADepth-First Search (DFS) in Python: Recursive and IterativeLearn depth-first search: recursive and stack-based DFS, connected components, counting islands in a grid, detecting cycles in undirected and directed graphs, and when to choose DFS over BFS.Intermediate11 min read