Как реализуешь стек на Python?

Как реализуешь стек на Python?

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

1. Использование списка (самый простой способ)

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)

# Использование
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print(stack.peek()) # 3
print(stack.pop())  # 3

2. Использование 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

3. С типизацией (для production)

from typing import Any, Optional, Generic, TypeVar

T = TypeVar('T')

class Stack(Generic[T]):
    def __init__(self):
        self._items: list[T] = []
    
    def push(self, item: T) -> None:
        self._items.append(item)
    
    def pop(self) -> T:
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()
    
    def peek(self) -> T:
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._items[-1]
    
    def is_empty(self) -> bool:
        return len(self._items) == 0
    
    def size(self) -> int:
        return len(self._items)

4. Со связным списком

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

class Stack:
    def __init__(self):
        self.top = None
    
    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node
    
    def pop(self):
        if self.is_empty():
            return None
        value = self.top.data
        self.top = self.top.next
        return value
    
    def peek(self):
        if self.is_empty():
            return None
        return self.top.data
    
    def is_empty(self):
        return self.top is None

5. Практический пример: проверка скобок

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

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

6. Вычисление RPN (Reverse Polish Notation)

def evaluate_rpn(tokens: list[str]) -> float:
    stack: Stack[float] = Stack()
    operators = {'+', '-', '*', '/'}
    
    for token in tokens:
        if token in operators:
            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)
        else:
            stack.push(float(token))
    
    return stack.pop()

print(evaluate_rpn(["2", "1", "+", "3", "*"]))  # 9

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

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

def dfs_iterative(root: TreeNode) -> list:
    stack = Stack()
    result = []
    
    if root:
        stack.push(root)
    
    while not stack.is_empty():
        node = stack.pop()
        result.append(node.value)
        
        if node.right:
            stack.push(node.right)
        if node.left:
            stack.push(node.left)
    
    return result

8. Сравнение реализаций

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

1. Для простого случая — используй встроенный list
2. Для production — используй deque или типизированный класс
3. Для обучения — реализуй со связным списком
4. Основное свойство: LIFO (Last In, First Out)
5. Применение: парсинг, обход деревьев, вычисления выражений, undo/redo