Стек в Python: реализация и применение

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

---

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

1. Использование списка (list)

Стандартный список в Python идеально подходит для реализации стека. Для этого используются два метода:

• push() → append(): добавление элемента в конец списка.
• pop(): удаление и возврат последнего элемента.

Пример:

stack = []
stack.append(1)  # [1]
stack.append(2)  # [1, 2]
stack.append(3)  # [1, 2, 3]

print(stack.pop())  # 3 (стек теперь [1, 2])
print(stack.pop())  # 2 (стек теперь [1])

2. Класс-обертка для стека

Для удобства можно создать класс, инкапсулирующий логику стека:

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()
        raise IndexError("pop from empty stack")
    
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("peek from empty stack")
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

# Использование
s = Stack()
s.push(10)
s.push(20)
print(s.peek())  # 20
print(s.pop())   # 20

---

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

• Push: Добавление элемента на вершину стека.
• Pop: Удаление и возврат верхнего элемента.
• Peek: Просмотр верхнего элемента без удаления.
• isEmpty: Проверка на пустоту.
• Size: Получение текущего размера стека.

---

Альтернативные реализации

1. Использование deque из модуля collections

Для больших объемов данных эффективнее использовать deque, оптимизированный для быстрых операций с обоих концов:

from collections import deque

stack = deque()
stack.append(1)
stack.append(2)
print(stack.pop())  # 2

2. LifoQueue из модуля queue

Подходит для многопоточных приложений, но менее эффективен в однопоточных из-за блокировок:

from queue import LifoQueue

stack = LifoQueue()
stack.put(1)
stack.put(2)
print(stack.get())  # 2

---

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

1. Отмена операций (Undo): Стек хранит историю действий.
2. Синтаксический анализ: Проверка баланса скобок, парсинг выражений.
3. Обход в глубину (DFS): В алгоритмах на графах и деревьях.
4. Стек вызовов: Хранение контекста выполнения функций в Python.

---

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

• Списки подходят для небольших стеков.
• Deque эффективен для больших данных.
• LifoQueue используйте только в многопоточных сценариях.

---

Заключение

Стек — это фундаментальная структура данных, которую легко реализовать в Python. Выбор реализации зависит от задачи: списки и deque подходят для большинства случаев, а LifoQueue — для многопоточности. Понимание работы стека поможет в решении множества задач, от алгоритмов до системных функций.