Конспект: стек, очередь, дека, кольцевой буфер

Понятия

Стек - дисциплина LIFO (последним пришёл - первым ушёл). Операции push и pop с одного конца (вершины). На динамическом массиве обе O(1): push = append, pop = снятие с конца.

Очередь - дисциплина FIFO (первым пришёл - первым ушёл). enqueue в хвост, dequeue с головы, с разных концов. Наивно на массиве dequeue через pop(0) - O(n) (сдвиг хвоста), на серии O(n²).

Кольцевой буфер - массив плюс индексы head (откуда снимать), tail (куда класть) и счётчик count. Индексы двигаются с обёртыванием (i + 1) % size, данные не сдвигаются: enqueue/dequeue - O(1) в худшем случае. Ёмкость фиксирована.

Очередь на двух стеках - in (для enqueue) и out (для dequeue); при пустом out переливают в него весь in. dequeue - O(1) амортизированно.

Дека - двусторонняя очередь: O(1) добавить и снять с ОБОИХ концов. Обобщает стек и очередь.

Что унести

Стек массиву по руке (трогает только дешёвый конец), очередь без ухищрений - нет (голова = начало массива, pop(0) сдвигает хвост). Беда очереди не в дисциплине FIFO, а в реализации ГОЛОВЫ.

Два способа сделать очередь без сдвига:

Кольцевой буфер: двигаем индексы, а не данные; (i + 1) % size замыкает массив в кольцо; count отличает пустую очередь от полной (ведь head == tail бывает в обоих случаях).

Два стека: каждый элемент переливается из in в out РОВНО раз за жизнь (перелив - только при пустом out), проходит 4 дешёвых шага (push в in, pop из in, push в out, pop из out), поэтому серия ≤ 4n - O(1) амортизированно. Потенциал Φ = 2·(размер in) (по два на элемент - на будущие pop из in и push в out): enqueue копит 2, дорогой перелив 2k гасится падением Φ. Это амортизация из прошлого раздела (тот же коэффициент 2, что в Φ = 2·num − size) и упражнение из CLRS.

Выбор реализации - по виду цены: нужен предсказуемый худший вызов (реальное время) - кольцевой буфер; хватает гарантии по серии и нужен рост сам собой - два стека. За deque в стандартных библиотеках стоит кольцевой буфер или двусвязный список.

Ловушки джокера

Сделал очередь на list через pop(0). Классический скрытый O(n²): очередь выглядит невинно, а сдвиг головы тихо превращает обработку в квадрат. Для очереди - deque.

Забыл обёртывание в кольцевом буфере. tail += 1 без % size вылезет за границу, хотя в начале буфера полно свободных ячеек, освобождённых dequeue.

Определил пустоту через head == tail без счётчика. Спутаешь пустую очередь с полной: потеряешь данные или зря откажешь.

Переливаешь при непустом out. Новые элементы ложатся поверх старых и выходят раньше - FIFO сломан. Перелив обратно после каждого dequeue чинит порядок, но элементы льются много раз, и O(1) рассыпается в O(n). Условие «только при пустом out» держит и порядок, и цену.

Принял амортизированную O(1) за гарантию на вызов. Отдельный dequeue с переливом - O(k). Где важен худший ОДИН шаг, нужен кольцевой буфер.

Проверь себя

Чем стек (LIFO) отличается от очереди (FIFO)?

Почему стек на массиве O(1), а наивная очередь через pop(0) - O(n²)?

Как кольцевой буфер даёт O(1) и зачем ему count и обёртывание % size?

Почему очередь на двух стеках - O(1) амортизированно, и при чём тут «перелив только при пустом out»?

Что такое дека и когда выбирают кольцевой буфер, а когда два стека?