все Python 3Алгоритмы и структуры данныхфункция

Стек (stack)

структуры

LIFO — последний вошёл, первый вышел. Реализуется через list. Применения: скобки, история, DFS.

Синтаксис

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

Для стека список — правильный контейнер: append() и pop() с конца стоят амортизированные O(1), и deque здесь ничего не выигрывает. Ловушка одна и постоянная: pop() на пустом стеке бросает IndexError, поэтому перед снятием проверяют, что стек непуст (сам список в булевом контексте это и показывает). Явный стек ещё и спасает там, где рекурсивный обход уходит слишком глубоко и упирается в RecursionError.

Примеры

# Базовые операции
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

См. также

Частые ошибки

Открыть в полном глоссарииdocs.python.orgСообщить о неточности