Стек и очередь: стопка тарелок против турникета в метро

Вся разница между стеком и очередью — в том, с какого конца вы достаёте элементы.

Стек: последний пришёл — первый ушёл. Очередь: первый пришёл — первый ушёл. Два правила, на которых держится половина программ.

Стек: стопка тарелок

Вообразите стопку чистых тарелок. Новую вы кладёте сверху, и берёте тоже сверху. До нижней тарелки не добраться, пока не снимете все, что лежат на ней. Такой порядок называют LIFO — Last In, First Out, «последний пришёл — первый ушёл».

У стека всего две главные операции: положить наверх (push) и снять сверху (pop). Никакого доступа к середине — и именно эта строгость делает стек предсказуемым и быстрым.

Где живёт стек

Кнопка «Назад» в браузере — это стек посещённых страниц: последняя открытая снимается первой. Отмена действия (Ctrl+Z) в редакторе — стек ваших правок. Даже вызовы функций в программе хранятся в «стеке вызовов»: последняя вызванная функция завершается первой, а если она зациклится — вы увидите знаменитую ошибку stack overflow, переполнение стека.

Очередь: турникет в метро

Очередь устроена честнее. Кто встал раньше — пройдёт раньше. Новые элементы добавляются в хвост, а забираются из головы. Это FIFO — First In, First Out, «первый пришёл — первый ушёл». Ровно как живая очередь в кассу.

Операции тоже две: встать в хвост (enqueue) и выйти из головы (dequeue). Никто не лезет без очереди, порядок соблюдается строго.

Где живёт очередь

Документы, отправленные на принтер, печатаются в порядке отправки — это очередь заданий. Сообщения между сервисами часто ждут обработки в очереди. Задачи операционной системы выстраиваются в очередь к процессору. Везде, где важна справедливость «кто первый — того и обслужим», стоит очередь.

Одно правило меняет всё

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

from collections import deque

# Стек (LIFO): кладём и снимаем с одного конца
stack = []
for x in ["страница1", "страница2", "страница3"]:
    stack.append(x)
print("Назад ведёт на:", stack.pop())   # страница3

# Очередь (FIFO): кладём в хвост, берём из головы
queue = deque()
for x in ["документ1", "документ2", "документ3"]:
    queue.append(x)
print("Печатаем первым:", queue.popleft())  # документ1

В стеке мы сняли тот документ, что положили последним. В очереди — тот, что положили первым. Те же три элемента, противоположный результат. Кстати, для очереди в Python берут deque, а не обычный список: убирать элемент из начала списка медленно, потому что приходится сдвигать все остальные.

Когда что выбрать

Бонус: обход в ширину

Очередь — сердце алгоритма «поиск в ширину» (BFS), которым находят кратчайший путь в лабиринте или в сети дорог. Мы кладём в очередь точки, до которых дошли, и разбираем их строго по порядку — поэтому ближайшие места исследуются раньше дальних. Заменишь очередь на стек — и тот же код начнёт нырять вглубь, превратившись в «поиск в глубину» (DFS). Одна структура, два разных характера обхода.

Стек и очередь — самые маленькие кирпичики в мире структур данных. Но именно из таких простых правил — «бери сверху» и «бери спереди» — складывается поведение огромных систем.