all Python 3Algorithms & data structuresfunction

Stack

data structures

LIFO — last in, first out. Implemented with a list. Uses: bracket matching, history, DFS.

Syntax

stack = []
stack.append(x)  # push
stack.pop()      # pop

A list is the right container here: append() and pop() at the end are amortized O(1), and a deque buys you nothing. The recurring trap is popping an empty stack — that raises IndexError, so test the stack in a boolean context before you pop. An explicit stack also rescues traversals that go too deep for recursion and would otherwise hit RecursionError.

Examples

# Базовые операции
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack[-1])  # peek → 3
print(stack.pop())  # → 3
print(stack)  # → [1,2]

# Проверка правильности скобок
def is_balanced(s):
    stack = []
    pairs = {')':'(',']':'[','}':'{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return len(stack) == 0
print(is_balanced('({[]})'))  # → True
print(is_balanced('([)]'))    # → False

# Обращение строки через стек
def reverse_string(s):
    stack = list(s)
    result = []
    while stack:
        result.append(stack.pop())
    return ''.join(result)
print(reverse_string('hello'))  # → olleh

# Перевод в двоичную систему
def to_binary(n):
    if n == 0: return '0'
    stack = []
    while n > 0:
        stack.append(n % 2)
        n //= 2
    return ''.join(str(b) for b in reversed(stack))
print(to_binary(10))   # → 1010
print(to_binary(255))  # → 11111111

# Вычисление постфиксного выражения
def eval_postfix(tokens):
    stack = []
    for t in tokens:
        if t.lstrip('-').isdigit():
            stack.append(int(t))
        else:
            b, a = stack.pop(), stack.pop()
            if t=='+': stack.append(a+b)
            elif t=='-': stack.append(a-b)
            elif t=='*': stack.append(a*b)
            elif t=='/': stack.append(a//b)
    return stack[0]
print(eval_postfix(['3','4','+','2','*']))  # → 14

# Минимальный стек (O(1) min)
class MinStack:
    def __init__(self):
        self.stack = []; self.min_stack = []
    def push(self, x):
        self.stack.append(x)
        m = min(x, self.min_stack[-1]) if self.min_stack else x
        self.min_stack.append(m)
    def pop(self):
        self.min_stack.pop(); return self.stack.pop()
    def get_min(self): return self.min_stack[-1]
ms = MinStack()
for v in [3,1,4,1,5]: ms.push(v)
print(ms.get_min())  # → 1

See also

Common errors

Open in the full glossarydocs.python.orgReport an inaccuracy