Стек, очередь, deque

Список в Python умеет всё: добавлять и удалять где угодно. Но во многих задачах нужны только два способа работы с данными, и у них есть свои имена — стек и очередь. Если узнать их в задаче, решение часто становится очевидным.

Стек

Стек — это стопка тарелок: кладём наверх и берём сверху. «Последний пришёл — первый ушёл» (по-английски LIFO).

В Python стек — обычный список, с которым работают только с конца:

stack = []
stack.append("a")     # положить наверх
stack.append("b")
stack.append("c")
print(stack[-1])      # c — посмотреть верх
print(stack.pop())    # c — снять верх
print(stack.pop())    # b
print(len(stack))     # 1

append и pop() с конца работают мгновенно. Перед pop() проверяй, что стек не пуст: if stack: — иначе будет ошибка IndexError.

Где нужен стек

Стек помогает, когда нужно «вернуться к последнему незавершённому»:

• отмена действий (Ctrl+Z) — отменяется последнее действие;
• вложенные конструкции — скобки, теги HTML, вызовы функций;
• обход «вглубь».

Пример: разворот строки через стек.

stack = []
for ch in "абв":
    stack.append(ch)
res = ""
while stack:
    res += stack.pop()
print(res)    # вба

Пример посложнее: калькулятор для записи, где операция пишется после чисел (3 4 + 2 * означает (3 + 4) * 2):

tokens = "3 4 + 2 *".split()
stack = []
for t in tokens:
    if t in "+-*":
        b = stack.pop()
        a = stack.pop()
        if t == "+": stack.append(a + b)
        elif t == "-": stack.append(a - b)
        else: stack.append(a * b)
    else:
        stack.append(int(t))
print(stack.pop())    # 14

Монотонный стек

Иногда в стеке держат элементы, которые ещё «ждут ответа», и при появлении нового элемента снимают тех, на кого он отвечает. Тогда каждый элемент кладётся и снимается один раз, и вся обработка идёт за n шагов. Подумай, как с таким стеком для каждого числа найти ближайшее меньшее слева.

Очередь

Очередь — как в магазине: встаём в конец, обслуживают из начала. «Первый пришёл — первый ушёл» (FIFO).

Список для очереди плох: pop(0) сдвигает все элементы, и на больших данных это очень медленно. Для очереди есть deque из модуля collections:

from collections import deque

q = deque()
q.append("Аня")        # встать в конец
q.append("Боря")
q.append("Вика")
print(q.popleft())     # Аня — обслужить первого
print(q[0])            # Боря — кто следующий
print(len(q))          # 2

deque (читается «дек») — двусторонняя очередь: у неё быстрые операции с обоих концов: append, appendleft, pop, popleft.

Где нужна очередь

• моделирование очередей, заданий, событий в порядке поступления;
• обход «вширь» — например, поиск кратчайшего пути в лабиринте (это следующая ступень после базового курса);
• «последние k элементов»: deque(maxlen=k) сама выбрасывает старые элементы.

from collections import deque
last = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    last.append(x)
print(list(last))    # [3, 4, 5]

Как выбрать

Нужно	Структура	Операции
брать последнее добавленное	стек (list)	append, pop(), [-1]
брать первое добавленное	очередь (deque)	append, popleft(), [0]
работать с обоими концами	deque	append, appendleft, pop, popleft

Итог

• стек: append и pop() у списка, «последний пришёл — первый ушёл»;
• очередь: deque с append и popleft(), «первый пришёл — первый ушёл»;
• не используй list.pop(0) для очереди — это медленно;
• проверяй пустоту перед снятием элемента;
• стек решает задачи на вложенность и «ближайший слева/справа», очередь — моделирование по порядку.