Какую структуру данных будешь использовать для хранения стека на Python?

Структуры данных для реализации стека в Python

Для хранения стека в Python рекомендуется использовать список (list) благодаря его эффективности и встроенным методам. Альтернативно можно использовать collections.deque, которая оптимизирована для операций с концами. Кастомная реализация на основе связного списка используется в образовательных целях.

1. Список (list) — самый простой вариант

Питон-список идеально подходит для стека благодаря:

• O(1) операциям push (append) и pop
• Встроенным методам
• Простоте использования

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

# Использование
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)

print(stack.pop())    # 30
print(stack.peek())   # 20
print(stack.size())   # 2

2. collections.deque — оптимизированный вариант

Deque (Double-Ended Queue) специально оптимизирована для операций с концами:

from collections import deque

class StackDeque:
    def __init__(self):
        self.items = deque()
    
    def push(self, item):
        """Добавить элемент"""
        self.items.append(item)  # O(1)
    
    def pop(self):
        """Удалить и вернуть верхний элемент"""
        if self.is_empty():
            raise IndexError("pop из пустого стека")
        return self.items.pop()  # O(1)
    
    def peek(self):
        """Посмотреть верхний элемент"""
        if self.is_empty():
            raise IndexError("стек пуст")
        return self.items[-1]  # O(1)
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

# Использование
stack = StackDeque()
for i in range(1000000):
    stack.push(i)

while not stack.is_empty():
    stack.pop()

Сравнение: list vs deque

import timeit
from collections import deque

# Тест push/pop производительности
def test_list():
    s = []
    for i in range(10000):
        s.append(i)
    for _ in range(10000):
        s.pop()

def test_deque():
    s = deque()
    for i in range(10000):
        s.append(i)
    for _ in range(10000):
        s.pop()

print("list:", timeit.timeit(test_list, number=100))
print("deque:", timeit.timeit(test_deque, number=100))
# deque часто быстрее при больших объёмах

3. Кастомная реализация на основе связного списка

Для образовательных целей или специальных случаев:

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

class LinkedListStack:
    def __init__(self):
        self.head = None  # Указатель на верх стека
        self._size = 0
    
    def push(self, item):
        """Добавить элемент в начало списка"""
        new_node = Node(item)
        new_node.next = self.head
        self.head = new_node
        self._size += 1
    
    def pop(self):
        """Удалить и вернуть верхний элемент"""
        if self.is_empty():
            raise IndexError("pop из пустого стека")
        
        data = self.head.data
        self.head = self.head.next
        self._size -= 1
        return data
    
    def peek(self):
        """Посмотреть верхний элемент"""
        if self.is_empty():
            raise IndexError("стек пуст")
        return self.head.data
    
    def is_empty(self):
        return self.head is None
    
    def size(self):
        return self._size

# Использование
stack = LinkedListStack()
stack.push(100)
stack.push(200)
stack.push(300)

while not stack.is_empty():
    print(stack.pop())

4. Практические примеры использования стека

Проверка сбалансированных скобок

def is_balanced(expr):
    """Проверить, сбалансированы ли скобки"""
    stack = []
    pairs = {'(': ')', '[': ']', '{': '}'}
    
    for char in expr:
        if char in pairs:
            stack.append(char)  # push
        elif char in pairs.values():
            if not stack or pairs[stack.pop()] != char:
                return False
    
    return len(stack) == 0

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

Обратная польская нотация (RPN)

def evaluate_rpn(tokens):
    """Вычислить выражение в обратной польской нотации"""
    stack = []
    operators = {'+', '-', '*', '/'}
    
    for token in tokens:
        if token in operators:
            b = stack.pop()
            a = stack.pop()
            
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(int(a / b))
        else:
            stack.append(int(token))
    
    return stack[0]

print(evaluate_rpn(["2", "1", "+", "3", "*"]))  # (2+1)*3 = 9
print(evaluate_rpn(["15", "7", "1", "1", "-", "/", "*", "2", "-", "1", "+"]))  # 5

Обход дерева в глубину (DFS)

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def dfs_iterative(root):
    """Обход дерева итеративно с использованием стека"""
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # Добавляем в обратном порядке (right, left)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

Рекомендация

Используй list в 95% случаев:

• Просто и понятно
• Встроенные методы (append, pop)
• Достаточно быстро для большинства задач

# Минимальная реализация
stack = []
stack.append(item)     # push
item = stack.pop()     # pop
top = stack[-1]        # peek
is_empty = len(stack) == 0

Используй deque, если:

• Нужна максимальная производительность
• Работаешь с очень большими стеками
• Нужны операции с обоих концов

Используй связный список, если:

• Изучаешь структуры данных
• Нужна гибкость в управлении памятью
• Не критична производительность