Что такое стек (Stack) в Python?

Стек (Stack) в Python: Полное объяснение

Стек (Stack) — это абстрактная структура данных, которая работает по принципу LIFO (Last In, First Out — последним вошёл, первым вышел). Это означает, что элемент, добавленный последним, удаляется первым. Стек широко используется в программировании для управления памятью, синтаксического анализа и алгоритмов обхода.

Концепция и аналогия

Представь стопку тарелок:

• Новую тарелку кладут сверху (push)
• Тарелку берут сверху (pop)
• Тарелка, которая попала в стопку последней, будет достана первой

Это основной принцип работы стека.

Основные операции стека

Push — добавление элемента в стек Pop — удаление и возврат верхнего элемента Peek — просмотр верхнего элемента без удаления IsEmpty — проверка, пуст ли стек Size — получение количества элементов

Реализация стека в Python

Базовая реализация на списке

Самый простой способ — использовать список:

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """Добавить элемент в стек"""
        self.items.append(item)
    
    def pop(self):
        """Удалить и вернуть верхний элемент"""
        if not self.is_empty():
            return self.items.pop()
        return None
    
    def peek(self):
        """Просмотреть верхний элемент без удаления"""
        if not self.is_empty():
            return self.items[-1]
        return None
    
    def is_empty(self):
        """Проверить, пуст ли стек"""
        return len(self.items) == 0
    
    def size(self):
        """Получить количество элементов"""
        return len(self.items)
    
    def __str__(self):
        return str(self.items)

# Использование
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack)  # [1, 2, 3]
print(stack.pop())  # 3
print(stack.peek())  # 2
print(stack.size())  # 2

Использование deque для оптимизации

Для лучшей производительности используй collections.deque:

from collections import deque

class Stack:
    def __init__(self):
        self.items = deque()
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None
    
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None
    
    def is_empty(self):
        return len(self.items) == 0

Почему deque лучше:

• append() и pop() имеют O(1) сложность
• Работает эффективнее с большими объёмами данных
• Меньше переаллокаций памяти

Практические применения стека

1. Проверка скобок

Определить, сбалансированы ли скобки:

def is_balanced(expr):
    stack = Stack()
    pairs = {'(': ')', '[': ']', '{': '}'}
    
    for char in expr:
        if char in pairs:
            stack.push(char)
        elif char in pairs.values():
            if stack.is_empty() or pairs[stack.pop()] != char:
                return False
    
    return stack.is_empty()

print(is_balanced("({[]})"))  # True
print(is_balanced("({[}])"))  # False

2. Обратная строка

def reverse_string(s):
    stack = Stack()
    for char in s:
        stack.push(char)
    
    result = ""
    while not stack.is_empty():
        result += stack.pop()
    
    return result

print(reverse_string("hello"))  # "olleh"

3. Вычисление постфиксного выражения

def postfix_eval(expr):
    """Вычислить выражение в постфиксной нотации"""
    stack = Stack()
    tokens = expr.split()
    
    for token in tokens:
        if token.isdigit():
            stack.push(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.push(a + b)
            elif token == '-':
                stack.push(a - b)
            elif token == '*':
                stack.push(a * b)
            elif token == '/':
                stack.push(a // b)
    
    return stack.pop()

print(postfix_eval("3 4 + 2 *"))  # (3+4)*2 = 14

4. DFS (глубина в глубину) обход графа

def dfs_iterative(graph, start):
    stack = Stack()
    visited = set()
    stack.push(start)
    
    while not stack.is_empty():
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')
            # Добавить соседей в стек в обратном порядке
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.push(neighbor)
    
    return visited

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}
dfs_iterative(graph, 'A')  # A B D E C F

5. Отслеживание истории вызовов функций

Call stack (стек вызовов) используется интерпретатором Python для отслеживания активных функций:

import traceback

def function_a():
    function_b()

def function_b():
    function_c()

def function_c():
    traceback.print_stack()  # Вывести стек вызовов

function_a()

Стек вызовов в Python

При каждом вызове функции Python создаёт кадр стека (stack frame):

def outer():
    x = 1
    def inner():
        y = 2
        return x + y
    return inner()

result = outer()
# Стек вызовов: outer() -> inner() -> вычисление и возврат

Сложность операций

Встроенные возможности Python

Python имеет встроенный стек в виде списка с методами:

stack = []
stack.append(1)  # push
stack.append(2)
value = stack.pop()  # pop
last = stack[-1]  # peek

Однако для критичного по производительности кода лучше использовать deque.

Стек — одна из самых фундаментальных структур данных, критически важная для понимания того, как работает процесс выполнения программ и много алгоритмических задач.