📌Стеки, очереди, деки — базовые структуры данных с примерами
🖥Три ключевые структуры данных, которые лежат в основе множества алгоритмов. Никакой магии — только логика и практика. Погнали!
1️⃣Стек (Stack)
Что это?
Структура, где элементы добавляются и удаляются по принципу «последний вошел — первый вышел» (LIFO).
Аналогия:
Стопка тарелок. Новую кладете сверху (push), верхнюю берете первой (pop). 🍽
а) Отмена действий (Ctrl+Z)
class TextEditor:
def __init__(self):
self.text = ""
self.history = [] # стек для отмены
def write(self, char):
self.history.append(self.text) # сохраняем состояние
self.text += char
def undo(self):
if self.history:
self.text = self.history.pop() # восстанавливаем последнее состояние
editor = TextEditor()
editor.write("A") # текст: "A"
editor.write("B") # текст: "AB"
editor.undo() # текст: "A" (вернулись к предыдущему состоянию)
б) Проверка баланса скобок
def is_balanced(s):
stack = []
brackets = {")": "(", "}": "{", "]": "["}
for char in s:
if char in "({[":
stack.append(char)
elif char in ")}]":
if not stack or stack.pop() != brackets[char]:
return False
return not stack
print(is_balanced("({[]})")) # True
print(is_balanced("({[}])")) # False
в) Стек вызовов (рекурсия)
def factorial(n):
if n == 0:
return 1
return n * factorial(n-1) # каждый вызов добавляется в стек
print(factorial(5)) # 120
2️⃣Очередь (Queue)
Что это?
Структура, где элементы работают по принципу «первый вошел — первый вышел» (FIFO).
Аналогия:
Очередь в кассу магазина. Кто пришел первым, тот первым и уйдет. 🛒
а) Обработка задач
from collections import deque
task_queue = deque()
# Добавляем задачи в очередь
task_queue.append("send_email")
task_queue.append("generate_report")
task_queue.append("backup_database")
# Обрабатываем по порядку
while task_queue:
current_task = task_queue.popleft()
print(f"Выполняем: {current_task}")
# Вывод:
# Выполняем: send_email
# Выполняем: generate_report
# Выполняем: backup_database
б) Поиск в ширину (BFS)
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node)
visited.add(node)
queue.extend(graph[node]) # добавляем соседей
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["E"],
"D": [],
"E": []
}
bfs(graph, "A") # A → B → C → D → E
в) Буфер данных (стриминг)
buffer = deque(maxlen=3) # ограничиваем размер буфера
# Добавляем данные
buffer.append("пакет1")
buffer.append("пакет2")
buffer.append("пакет3")
buffer.append("пакет4") # "пакет1" автоматически удаляется
print(list(buffer)) # ['пакет2', 'пакет3', 'пакет4']
3️⃣ Дек (Deque, Double-Ended Queue)
Что это?
Гибрид стека и очереди: элементы можно добавлять и удалять с обоих концов.
Аналогия:
Очередь, где можно встать как в начало, так и в конец. Например, поезд с вагонами, которые цепляют спереди и сзади. 🚆
а) Планировщик задач с приоритетами
from collections import deque
tasks = deque()
# Обычные задачи идут в конец, срочные — в начало
tasks.append("task1")
tasks.append("task2")
tasks.appendleft("urgent_task")
print(tasks) # deque(['urgent_task', 'task1', 'task2'])
б) Алгоритм скользящего окна (максимум в подмассивах)
def max_sliding_window(nums, k):
dq = deque()
result = []
for i, num in enumerate(nums):
while dq and nums[dq[-1]] <= num:
dq.pop()
dq.append(i)
if dq[0] == i - k: # удаляем элементы вне окна
dq.popleft()
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(max_sliding_window([1,3,-1,-3,5,3,6], 3)) # [3, 3, 5, 5, 6]