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

Предпосылки: абстрактный тип данных (контракт операций, оценка сложности O(…)), массив, динамический массив, связный список (односвязный, двусвязный), ссылки, базовое чтение Ruby (классы, методы, массивы и хеши).

← Связный список | Хеш-таблица →

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

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

Стек

Из контракта стека — добавление и удаление с одного конца — следует порядок выдачи: последний добавленный достаётся первым. Это правило называют LIFO (Last In, First Out, «последним пришёл — первым вышел»). Знакомый образ — стопка тарелок: берут верхнюю, ту, что положили последней.

Операция	Сигнатура	Сложность
Положить на вершину	`push(x)`	O(1)
Снять с вершины	`pop() → x`	O(1)
Посмотреть вершину	`peek() → x`	O(1)
Проверить пустоту	`empty?() → bool`	O(1)

Стрелка в сигнатуре показывает, что́ операция возвращает: pop отдаёт снятый элемент, empty? — да/нет.

Под этот контракт хорошо ложится динамический массив: и добавление, и снятие идут с правого края, где массив просто меняет длину, не сдвигая остальные элементы. Подошёл бы и односвязный список — там вершина это голова, операции тоже O(1) и без перевыделения памяти, — но на практике массив быстрее: его элементы лежат подряд, и процессор читает их из кеша, а не гоняется за разбросанными узлами (подробнее — локальность данных).

Тот же LIFO лежит в основе стека вызовов программы: вызванная последней функция завершается первой, и управление возвращается к той, что её вызвала.

Очередь

Стек выдаёт элементы в обратном порядке — иногда это ровно то, что не нужно. Задания на принтере печатаются в порядке поступления: первое отправленное должно выйти первым, а не последним. Контракт под такой порядок другой: добавлять в один конец, забирать из противоположного. Тогда первым уйдёт самый старый элемент — правило FIFO (First In, First Out, «первым пришёл — первым вышел»). Конец, куда добавляют, по привычке из связного списка называют хвостом, конец, откуда забирают, — головой.

Операция	Сигнатура	Сложность
Добавить в конец	`enqueue(x)`	O(1)
Забрать из начала	`dequeue() → x`	O(1)
Посмотреть первый	`front() → x`	O(1)
Проверить пустоту	`empty?() → bool`	O(1)

Прямолинейная реализация — односвязный список, который помнит и голову, и хвост: добавление идёт в хвост, выдача — из головы, обе операции O(1). Но узлы списка разбросаны по памяти, и при большом потоке элементов процессор постоянно промахивается мимо кеша (см. типы промахов) — расплата за непрерывные прыжки по ссылкам. Кольцевой буфер (ring buffer) убирает эту расплату, держа элементы подряд в одном массиве.

Кольцевой буфер: от «мёртвой зоны» к кольцу

Начнём с прямой реализации очереди на массиве. Добавление — в конец, O(1). А выдача из начала? Сдвигать все оставшиеся элементы на одну позицию влево — O(n), слишком дорого. Дешевле не трогать элементы, а запомнить, где сейчас начало очереди, отдельным числом — индексом head. Забрали элемент — сдвинули head на один вправо:

После нескольких выдач:
[_][_][_][_][A][B][C][D]
             ^           ^
           head        tail

head указывает на первый живой элемент, tail — на первую свободную ячейку за последним. Четыре ячейки слева уже отданы и не вернутся: новые элементы добавляются только справа, потому что tail движется только вправо. Со временем tail упрётся в правый край, и массиву придётся расти — хотя слева простаивает «мёртвая зона», а живых элементов горстка.

Зону можно вернуть в оборот. Что если tail, дойдя до правого края, продолжит не за границей массива, а с нулевой ячейки — туда, где место уже освободилось? Записывать он будет только в пустые ячейки слева, живые элементы справа не затрагивая, так что данные не теряются. Массив логически замыкается в кольцо:

[G][H][_][_][E][F]
       ^     ^
     tail   head

Переход через край по модулю

Осталось выразить «дойдя до правого края, продолжить с нуля» формулой. Размер буфера — число ячеек — назовём capacity. Сдвиг любого индекса на следующую ячейку:

next = (current + 1) % capacity

% здесь — остаток от деления. Для capacity = 8: с предпоследней позиции (6 + 1) % 8 = 7 — обычный шаг вправо; с последней (7 + 1) % 8 = 0 — заворот в начало. Одна формула покрывает оба случая, и head, и tail двигаются ею.

Пустой буфер против полного

Заворот по кольцу порождает неоднозначность. Пустой буфер даёт head == tail (забрали всё, что добавили). Но и полностью забитый буфер тоже даёт head == tail: tail, обойдя кольцо, догоняет head сзади. Одно и то же условие — два противоположных состояния.

Различить их можно двумя классическими способами. Первый — хранить отдельный счётчик size: буфер пуст при size == 0, полон при size == capacity, а head == tail перестаёт быть единственным признаком. Второй — пожертвовать одной ячейкой: договориться, что полный буфер всегда оставляет одну дырку перед head. Тогда полнота — это (tail + 1) % capacity == head, и это условие никогда не совпадает с head == tail, потому что между ними всегда есть незанятая ячейка.

Рост буфера

Когда добавлять больше некуда, буфер растёт так же, как динамический массив: выделяется буфер вдвое больше, и элементы переносятся в него. При переносе кольцо удобно «выпрямить» — переписать элементы подряд от начала, так что head оказывается в нуле, а tail — сразу за последним перенесённым. Удвоение размера делает копирование редким: на длинной серии добавлений средняя цена одного добавления остаётся O(1) (амортизированная стоимость — та же, что у роста динамического массива).

Дек

Стек работает одним концом, очередь — двумя, но роли концов закреплены: один только добавляет, другой только забирает. Иногда нужна свобода добавлять и забирать с любого конца — например, чтобы и класть «срочное» в начало, и обычное в хвост. Такой ADT называют деком (deque — double-ended queue, «двусторонняя очередь»; читается как «дек»).

Операция	Сигнатура	Сложность
Добавить в начало	`push_front(x)`	O(1)
Добавить в конец	`push_back(x)`	O(1)
Удалить из начала	`pop_front() → x`	O(1)
Удалить из конца	`pop_back() → x`	O(1)

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

Три уровня свободы

ADT	Добавление	Удаление	Чем удобно реализовать
Стек	один конец	тот же конец	массив или односвязный список
Очередь	один конец	противоположный	кольцевой буфер или односвязный список с хвостом
Дек	оба конца	оба конца	кольцевой буфер или двусвязный список

Доступ только по краям, а не по содержимому

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

А если искать нужно именно по содержимому — по имени "alice", по идентификатору заказа — и за O(1), а не перебором? Эту задачу решает хеш-таблица: она сопоставляет произвольному ключу позицию в массиве и так находит значение напрямую, не обходя остальные.

Стек на односвязном списке

Вершина стека — голова списка: push создаёт узел, ссылающийся на прежнюю голову, pop сдвигает голову на следующий узел. Оба — O(1). Работа же с хвостом потребовала бы при снятии искать предпоследний узел — O(n) в односвязном списке. Направление ссылок (каждый новый узел указывает на предыдущий) и есть порядок LIFO.

class Node
  attr_accessor :value, :next
 
  def initialize(value, next_node = nil)
    @value = value
    @next = next_node
  end
end
 
class Stack
  def initialize
    @head = nil
  end
 
  def push(value)
    @head = Node.new(value, @head)
  end
 
  def pop
    return nil unless @head
    value = @head.value
    @head = @head.next
    value
  end
 
  def peek
    @head ? @head.value : nil
  end
 
  def empty?
    @head.nil?
  end
end

Очередь на кольцевом буфере

Буфер хранит три числа: head (первый живой элемент), tail (первая свободная ячейка) и size (сколько элементов внутри — он же различает пустой буфер и полный). Добавление пишет в tail и двигает его по модулю; выдача читает из head и двигает его так же. Когда места не осталось, resize переносит элементы в буфер вдвое больше, выпрямляя кольцо: head уходит в 0, tail — за последний перенесённый элемент.

class RingQueue
  def initialize(initial_capacity = 8)
    @buffer = Array.new(initial_capacity)
    @head = 0
    @tail = 0
    @size = 0
  end
 
  def enqueue(value)
    resize if @size == @buffer.length
    @buffer[@tail] = value
    @tail = (@tail + 1) % @buffer.length
    @size += 1
  end
 
  def dequeue
    return nil if @size == 0
    value = @buffer[@head]
    @buffer[@head] = nil
    @head = (@head + 1) % @buffer.length
    @size -= 1
    value
  end
 
  def front
    return nil if @size == 0
    @buffer[@head]
  end
 
  def empty?
    @size == 0
  end
 
  private
 
  def resize
    new_buffer = Array.new(@buffer.length * 2)
    @size.times { |i| new_buffer[i] = @buffer[(@head + i) % @buffer.length] }
    @buffer = new_buffer
    @head = 0
    @tail = @size
  end
end

Прогон на буфере из 8 ячеек, заполненном четырьмя выдачами слева (head = 4): добавление кладёт элемент в @buffer[tail] и сдвигает tail по модулю — дойдя до края, тот заворачивается в освободившееся начало. Восьмое добавление застаёт @size == 8: срабатывает resize, цикл @size.times переписывает живые элементы подряд от head, и кольцо снова становится прямой лентой с запасом справа.

Sources

← Связный список | Хеш-таблица →

CS Notes

Explorer

stack-queue-deque