Стек и очередь: LIFO и FIFO

Если ты знаешь, что стек - это LIFO, а очередь - FIFO, почему стек на массиве даёт O(1), и в чём беда наивной очереди через pop(0), листай до «Теперь сам».

Как думаешь, в каком порядке структура отдаёт то, что в неё положили

До сих пор мы брали элемент по индексу или искали по значению. Но есть структуры, где ты вообще не выбираешь, какой элемент достать, - структура сама решает по ПОРЯДКУ. Их две, и различаются они одним: с какого конца отдавать. Стек отдаёт с того же конца, куда клал, - получается обратный порядок. Очередь отдаёт с другого конца - получается прямой. Оба ограничения не бедность, а сила: чем меньше структура обещает, тем дешевле её операции.

На что это похоже

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

Механизм: один конец против двух

Стек, дисциплина LIFO (last in, first out). Две операции: push(x) кладёт x наверх, pop() снимает верхний и возвращает его. Оба конца - один и тот же (вершина). На динамическом массиве стек ложится идеально: push - это append (в конец, амортизированно O(1)), pop - снятие с конца (O(1), сдвигать нечего). Вершина стека - конец массива, а конец у массива дёшев с обеих сторон.

Очередь, дисциплина FIFO (first in, first out). enqueue(x) кладёт x в хвост, dequeue() снимает с головы. Концы РАЗНЫЕ: кладём с одного, снимаем с другого. Вот тут массив и подводит. Хвост-то дёшев (append), а голова - это НАЧАЛО массива, и снять оттуда через pop(0) значит сдвинуть весь оставшийся хвост на позицию влево - O(n).

Правило

Стек - дисциплина LIFO (последним пришёл - первым ушёл): push и pop с одного конца, на массиве обе O(1). Очередь - дисциплина FIFO (первым пришёл - первым ушёл): enqueue в хвост, dequeue с головы, с разных концов. Наивная очередь на массиве снимает с головы через pop(0) - это сдвиг всего хвоста, O(n) на операцию и O(n²) на серию. Стек массиву по руке, а очередь без ухищрений - нет.

Разбор: почему стек на массиве - это O(1)

Стек трогает только один конец - вершину, - и мы сажаем её на КОНЕЦ массива, где всё дёшево. push(x) - это a.append(x): добавление в конец, амортизированно O(1) (динамический массив с удвоением, доказали в прошлом разделе). pop() - это снятие последнего элемента: за ним ничего не лежит, сдвигать нечего, O(1). Ни одна операция стека не лезет в начало массива, поэтому дорогого сдвига не возникает вовсе. Серия из n операций стека - O(n). Стек и массив совпали по слабым местам: оба не любят начало, а стек в начало и не ходит.

Разбор: почему наивная очередь на массиве - это O(n²)

Очередь вынуждена трогать оба конца. Хвост дёшев: enqueue(x) - это снова append, O(1). А dequeue() снимает с ГОЛОВЫ, то есть с начала массива. Если делать это в лоб через a.pop(0), произойдёт то же, что при удалении первого элемента: вся оставшаяся часть сдвинется на позицию влево, чтобы закрыть дырку в начале, - O(длины). Проведи n пар «enqueue, dequeue»: каждый dequeue сдвигает то, что накопилось, суммарно выходит Θ(n²). Абстрактно очередь ничем не хуже стека - разница в одной операции, dequeue с головы, которую массив делает дорого. Значит, дело не в дисциплине FIFO, а в РЕАЛИЗАЦИИ головы: убрать сдвиг - и очередь снова станет O(1). Как - в следующих двух уроках.

Что ломается без этого

Главная ошибка - реализовать очередь «в лоб» списком с pop(0) и получить O(n²) там, где ждёшь линию. Это одна из самых частых причин внезапно медленного кода: очередь выглядит невинно, а pop(0) в цикле тихо превращает обработку в квадрат. Вторая ошибка - лечить это через pop(0) «поосторожнее» (реже вызывать и т. п.): проблема не в частоте, а в самом сдвиге головы, и лечится она сменой реализации, а не экономией вызовов. Стек такой беды не знает - но именно потому, что не трогает начало.

Зачем это в работе

Стек и очередь - рабочие лошади программирования. Стек держит порядок вложенных дел: стек вызовов функций, отмена действий (undo), проверка скобок, обход в глубину. Очередь держит порядок ожидания: задачи на обработку, сообщения между сервисами, обход в ширину. В Python стек делают прямо на list (append/pop - обе O(1)), а вот очередь на list через pop(0) - классическая ошибка, поэтому для очереди берут collections.deque, где снятие с головы O(1). Понимать, ПОЧЕМУ list не годится для очереди, - значит не наступить на этот квадрат в реальной задаче.

Теперь сам

Ты кладёшь в структуру числа 1, 2, 3, а потом снимаешь три раза. В каком порядке они выйдут, если структура - стек? Если очередь? И почему стек на list (append/pop) даёт O(1) на операцию, а очередь на list через pop(0) - нет?