Master Stack Operations in Python: From Basics to Real-World Algorithms

In computer science, a stack (also called a heap stack) is an ordered collection where insertions and deletions occur only at the top, following a last‑in‑first‑out (LIFO) rule.

The typical interface for a stack includes operations to push, pop, check emptiness, and get the size. In Python, a list can be used as a stack with append() for push, pop() for pop, len() for size, and a boolean check for emptiness.

# Create a stack
s = []
# Push an element
s.append(1)
# Pop an element
s.pop()
# Check if empty
not s
# Get size
len(s)

Bracket Matching Example

The problem is to verify whether an expression containing the three types of brackets (), [], and {} is correctly nested.

Create an empty stack to store unmatched left brackets.

Traverse the string: push left brackets, pop and match when a right bracket appears.

If a right bracket appears when the stack is empty, the expression is invalid.

After traversal, if the stack is not empty, the expression is invalid.

def match(expr):
    LEFT = {'(', '[', '{'}
    RIGHT = {')', ']', '}'}
    stack = []
    for ch in expr:
        if ch in LEFT:
            stack.append(ch)
        elif ch in RIGHT:
            if not stack or not is_match(stack.pop(), ch):
                return False
    return not stack

Maze Solving Example

A 2‑D array represents a maze where 0 is a path and 1 is a wall. Using a stack to record the path, the algorithm explores neighboring cells, marks visited cells, and backtracks when hitting dead ends until reaching the exit.

def initMaze():
    maze = [[1]*7 for _ in range(7)]
    # set inner paths (omitted for brevity)
    return maze

def path(maze, start, end):
    stack = [(start[0], start[1])]
    while stack:
        i, j = stack[-1]
        if (i, j) == end:
            break
        for di, dj in [(0,-1),(0,1),(-1,0),(1,0)]:
            ni, nj = i+di, j+dj
            if maze[ni][nj] == 0:
                maze[ni][nj] = 1
                stack.append((ni, nj))
                break
        else:
            stack.pop()
    return stack

Postfix Expression Evaluation

Postfix (Reverse Polish) notation eliminates the need for parentheses. The algorithm uses a stack to store operands, applying operators as they appear.

operators = {
    '+': lambda a, b: a + b,
    '-': lambda a, b: a - b,
    '*': lambda a, b: a * b,
    '/': lambda a, b: a / b,
}

def evalPostfix(expr):
    stack = []
    for token in expr.split():
        if token.isdigit():
            stack.append(int(token))
        elif token in operators:
            b = stack.pop()
            a = stack.pop()
            stack.append(operators[token](a, b))
    return stack.pop()

result = evalPostfix('2 3 4 * +')  # 14

Knapsack Problem Example

Given a backpack capacity and a list of item weights, the backtracking algorithm uses a stack to explore combinations that exactly fill the backpack.

def knapsack(t, w):
    n = len(w)
    stack = []
    k = 0
    while stack or k < n:
        while t > 0 and k < n:
            if t >= w[k]:
                stack.append(k)
                t -= w[k]
                k += 1
            else:
                k += 1
        if t == 0:
            print(stack)  # found a solution
        if not stack:
            break
        k = stack.pop()
        t += w[k]
        k += 1

knapsack(10, [1,8,4,3,5,2])

These examples illustrate how the stack data structure serves as a versatile tool for solving a variety of algorithmic problems in Python.