Стек и очередь

Представьте стопку тарелок на кухне. Чистую тарелку кладут сверху. Когда нужна тарелка, её берут тоже сверху — ту самую, что положили последней. До нижней тарелки дело дойдёт, только когда снимут все остальные.

Программам часто нужен такой же порядок. Кнопка «Отменить» в редакторе сначала отменяет последнее действие, затем предпоследнее. Что сохранено позже, то выдаётся раньше.

Такой порядок даёт обычный список, если добавлять и забирать элементы только с его конца:

history = []
history.append("type")
history.append("bold")
history.append("delete")
print(history[-1])  # delete
last = history.pop()
print(last, history)  # delete ['type', 'bold']

Давайте разберём пример по строкам:

1. Три вызова append кладут в стопку history действия "type", "bold" и "delete". Последнее оказывается сверху.
2. history[-1] смотрит на верхнюю тарелку и печатает delete, ничего не снимая.
3. history.pop() снимает верхнее значение и кладёт его в last.
4. Последний print печатает delete ['type', 'bold']: в списке остались два первых действия.

Стек на списке

Стек — набор значений, в который добавляют и из которого забирают только с одного конца. Этот конец называют вершиной. Значение, положенное последним, забирают первым, как верхнюю тарелку.

У списка вершина — его конец. Для стека хватает трёх действий:

• append(x) кладёт значение x на вершину;
• pop() без аргумента снимает значение с вершины и возвращает его;
• stack[-1] только смотрит на вершину и стек не меняет.

Остальные элементы при этом не сдвигаются. Поэтому append и pop() работают одинаково быстро на списке любой длины.

Цикл while stack: снимает значения, пока стек не опустеет: пустой список ложен. Значения выходят в порядке, обратном тому, в котором их клали:

words = ["one", "two", "three"]
stack = []
for w in words:
    stack.append(w)
out = []
while stack:
    out.append(stack.pop())
print(out)  # ['three', 'two', 'one']

Слова легли в стопку в порядке one, two, three, а вышли наоборот. Первая положенная тарелка всегда оказывается в самом низу.

Здесь аналогия заканчивается. Из настоящей стопки среднюю тарелку не вытащить, а список такого запрета не знает: stack[0] прочитает нижний элемент. Стек — это договорённость: программа сама решает трогать только вершину.

Поэтому стек подходит задачам, где то, что открылось последним, должно закрыться первым. Так устроены вложенные скобки в выражении.

Очередь на deque

Очередь работает наоборот: первым забирают значение, которое пришло первым, как в очереди к кассе. Вызов pop(0) у списка тоже забирает первый элемент, но медленно. После него каждый оставшийся элемент сдвигается на одну позицию влево. В списке из миллиона элементов каждый вызов двигает почти миллион значений.

Для очереди в модуле collections есть тип deque. Он похож на список, но быстро добавляет и забирает значения с обоих концов. Строка from collections import deque подключает из модуля одно имя deque:

from collections import deque

line = deque(["Ann", "Bob"])
line.append("Kim")
first = line.popleft()
print(first, line)  # Ann deque(['Bob', 'Kim'])
print(len(line), line[0])  # 2 Bob

Разберём, что здесь происходит:

1. deque(["Ann", "Bob"]) создаёт очередь, в которой первой стоит "Ann".
2. append("Kim") добавляет "Kim" в конец очереди.
3. popleft() снимает значение с начала, то есть с левого края, и возвращает "Ann".
4. len и чтение по индексу работают так же, как у списка: в очереди двое, первым стоит Bob.

Метод pop() у deque тоже есть и, как у списка, забирает последнее значение.

Этот вопрос часто задают на собеседовании: «Почему очередь не строят на списке?» Ответ: pop(0) сдвигает все оставшиеся элементы, а popleft() у deque забирает первый элемент без сдвига.

Частая ошибка

Значение снимают с пустого стека:

stack = []
stack.pop()  # ✗

IndexError: pop from empty list

Снимать нечего, и программа останавливается с ошибкой IndexError. popleft() у пустого deque тоже даёт IndexError. Перед тем как снимать значение, проверьте, что набор не пуст, — if stack: или while stack:, как в цикле выше.

Главное

• Стек отдаёт первым то, что положили последним; на списке это append и pop().
• stack[-1] смотрит на вершину, не снимая её.
• Очередь отдаёт первым то, что пришло первым; её строят на deque с append и popleft().
• pop() и popleft() на пустом наборе дают IndexError, поэтому сначала проверяйте if stack:.