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

Нажмите в браузере «назад» — и он вернёт страницу, с которой вы пришли. Ещё раз — ту, что была до неё. А если теперь нажать на любую ссылку, кнопка «вперёд» погаснет: страницы, на которые можно было вернуться вперёд, пропали. Всё это поведение — два стека. Ниже вкладка с главами курсов этого сайта, и ссылки в ней настоящие. Походите по ним и посмотрите, что происходит со стопками страниц под кнопками.

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

Идея

Стек и очередь хранят последовательность и умеют добавлять и забирать по одному элементу за O(1). Стек кладёт и снимает с одного конца: последним пришёл — первым ушёл (LIFO, last in — first out). Очередь кладёт в хвост, а забирает из головы: первым пришёл — первым ушёл (FIFO). Ни поиска, ни доступа к середине — только два конца. Вся разница между ними — в порядке, и этот порядок решает задачу.

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

Стек: всё, что вложено

Самый важный стек в компьютере — стек вызовов. Когда функция вызывает другую, процессор кладёт на стек адрес, куда вернуться, и место для локальных переменных; когда вызванная функция заканчивает, запись снимается. Рекурсия глубиной в миллион — это миллион записей, и стек вызовов не бесконечен: Python по умолчанию останавливается на глубине 1000, а в Go стек каждой горутины растёт сам, но не больше гигабайта на 64-битных машинах. Поэтому глубокий обход графа или вложенную структуру надёжнее разбирать своим стеком в цикле.

Второй классический стек — разбор выражений. В записи «3 + 4 × 2» сначала нужно умножить, хотя умножение стоит позже. Эдсгер Дейкстра в 1961 году придумал для этого сортировочную станцию: числа сразу идут на выход, а операции ждут на стеке, как вагоны в тупике, пока их не пропустит операция слабее. На выходе получается обратная польская запись «3 4 2 × +», где скобок и приоритетов уже нет, а вычислить её можно одним стеком: число кладём, операция снимает два верхних числа и кладёт результат. Как это устроено в калькуляторах, подробно рассказано в главе курса, а код — в разделе ниже.

И третий — скобки. Правильная расстановка скобок — это когда каждая закрывающая закрывает последнюю ещё не закрытую открывающую того же вида. «Последнюю» — значит, стек. Проверим так весь роман: 2,9 миллиона символов, круглые скобки, кавычки-ёлочки и кавычки-лапки, которые ставят внутри ёлочек.

Обычно на стеке одна-две скобки — письмо по-французски в кавычках, ремарка в скобках, — и скоро они закрываются. Глубже всего, на четыре, он уходит в третьем томе, где чтец читает вслух афишку: кавычки афишки, скобка с ремаркой и кавычки-лапки с репликой слушателя внутри неё. Четвёртая скобка на стеке — не отсюда, о ней ниже. Под осью — 60 красных отметок: закрывающие скобки, которым нечего закрыть. Все 60 — номера пунктов: «1) скромность, 2) повиновение высшим чинам ордена» в главах о масонах, «a) государственных дел службы, b) от забот семейных» в дневнике Пьера. Для стека они ошибки, для читателя — нет.

А теперь посмотрите на сплошной блок посередине графика и красную полосу под ним. Это скобка, которая простояла открытой 1 393 233 символа — почти половину книги. Во втором томе, в главе об охоте, в электронном тексте стоит «как и всегда в (своих суждениях и чувствах не зная середины» — открывающая скобка, похоже, попала туда при оцифровке. Закрыть её в главе нечем, и стек несёт её через весь третий том, пока в четвёртом её случайно не «закроет» номер пункта «в трех действиях: 1)». Формально роман сбалансирован: в конце стек пуст. Но баланс не означает, что пары подобраны верно, и лишнюю скобку здесь выдаёт только её невозможная длина.

Очередь: по порядку прихода

Очередь на обычном списке Python напрашивается сама: append в конец, pop(0) из начала. Но pop(0) сдвигает на одну ячейку весь хвост списка — это O(n), и очередь из ста тысяч заданий разбирается за квадратичное время. Замер в разделе о сложности показывает, насколько это заметно.

Правильная очередь на массиве — кольцевой буфер. Элементы никуда не сдвигаются; вместо этого двигается голова — индекс самого старого элемента. Хвост — через столько ячеек после головы, сколько элементов в очереди, а когда индекс доходит до конца массива, он продолжается с нуля, по кругу. Если массив заполнился, его, как динамический массив, переносят во вдвое больший, заодно разворачивая кольцо. В Python готовая очередь — collections.deque: она устроена иначе, как цепочка блоков по 64 элемента, и потому никогда не копирует уже лежащие элементы. В Go отдельного типа нет, и очередь обычно делают на срезе: q = q[1:] снимает голову за O(1), но память под ушедшие элементы освободится только при следующем переезде среза.

Очередь можно собрать и из двух стеков. Новые элементы кладём во «входной» стек. Забираем из «выходного», а когда он пуст, переливаем в него весь входной: при переливании порядок переворачивается, и самый старый элемент оказывается наверху. Одно переливание может стоить O(n), но каждый элемент переливается за свою жизнь ровно один раз, поэтому каждая операция стоит O(1) амортизированно. Так устроены очереди в функциональных языках, где неизменяемый список — это по сути стек. И тот же приём решает вторую задачу статьи: если каждая запись в стеке помнит максимум под собой, очередь начинает отвечать на вопрос «какой максимум?» за O(1).

Почему очередь честная

Принтер печатает задания по одному. Если брать их по порядку прихода, это очередь. Можно брать последнее пришедшее — это стек. А можно сначала самое короткое. Ниже одни и те же 50 заданий, три правила и загрузка принтера, которую можно менять:

Нажмите «Среднее по 1000 наборам» при загрузке 90 %. Среднее ожидание у очереди и у стека почти одинаковое — около полутора минут. Это не совпадение: если порядок не смотрит на размер задания, среднее ожидание одно и то же при любом порядке (в теории очередей это следует из закона сохранения Клейнрока). Различается разброс. Дольше всех в очереди ждут в среднем 4,2 минуты, а в стеке — 11: задание, которому не повезло прийти перед толпой, уходит на дно и печатается, только когда новые перестанут приходить. Очередь гарантирует, что никого не обгонят. «Короткие вперёд» вдвое снижают среднее ожидание, но длинный отчёт может простоять дольше, чем в очереди, — об этой цене подробно в статье о планировании задач.

Бывает, что стек всё-таки лучше. Сервер под перегрузкой копит очередь запросов, и к тому моменту, когда до старого запроса доходит дело, пользователь, скорее всего, уже не ждёт ответа. Инженеры Facebook описывали в 2015 году «адаптивный LIFO»: пока очереди нет, запросы обслуживают по порядку, а как только она начинает расти, сервер переключается на самые свежие — у них больше шансов успеть к сроку.

Код

Кнопки браузера: стек — это динамический массив, у которого трогают только конец. Демо идёт по настоящим ссылкам между главами курса и печатает оба стека после каждого шага:

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

+ slides         [slides map photo draft]  head=1 size=4
print map        [slides . photo draft]  head=2 size=3
+ poem           [slides poem photo draft]  head=2 size=4
+ invoice        [photo draft slides poem invoice . . .]  head=0 size=5

Сортировочная станция и вычисление обратной польской записи — два стека, один для операций, другой для чисел. Обратите внимание на правую ассоциативность степени: 2^3^2 — это 2^9, а не 8²; за неё отвечает одно условие при выпуске операций со стека.

И проверка скобок на всём романе. Позиции считаются в символах: в Python это просто индекс строки, а в Go строку приходится превратить в срез рун, потому что индексы обычной строки — номера байтов, и русская буква занимает два.

Сколько это стоит

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

Наклон линии сдвига — единица: вдвое длиннее очередь — вдвое дороже каждое задание, а весь разбор — вчетверо. На 64 тысячах заданий сдвиг в Python медленнее deque в шестьдесят с лишним раз, в Go — почти в шестьсот. Линия кольца горизонтальна при любом n.

Где работают

Стек — везде, где есть вложенность и возврат: вызовы функций, отмена правок в редакторах (правки ложатся на стек, Ctrl+Z снимает верхнюю), разбор скобок, выражений и HTML-тегов, обход в глубину. Очередь — везде, где важен порядок прихода: буферы клавиатуры и сетевых карт, очереди задач на серверах, цикл событий в браузере, обход в ширину. Заметьте: обход графа в ширину и в глубину — один и тот же алгоритм, в котором поменяли очередь на стек.

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

История

В 1946 году Алан Тьюринг в проекте вычислительной машины ACE описал вызов подпрограмм с операциями BURY и UNBURY — «закопать» адрес возврата и «откопать» его, по сути стек вызовов. В 1955 году Клаус Самельсон и Фридрих Бауэр предложили «операционный подвал» (Operationskeller) для перевода формул в машинные команды, а в марте 1957 года подали на него заявку на патент; в 1988 году Бауэр получил за принцип стека премию IEEE «Пионер компьютерной техники». Независимо похожие идеи в 1954 году развивал Чарльз Хэмблин, автор обратной польской записи. По-русски стек долго называли магазином — как магазин пистолета, где последний вставленный патрон выходит первым.

Задачи

В первой задаче стек вычитывает рукопись: найти первую перепутанную скобку, причём три теста — главы «Войны и мира», и в одной из них ошибка настоящая. Во второй очередь на двух стеках каждое мгновение знает самое сильное землетрясение за последний месяц по каталогу USGS.