stack-queue-deque

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

Предпосылки: массив, динамический массив, связный список (односвязный, двусвязный).

Парсер арифметических выражений обрабатывает скобки: открывающая — запомнить, закрывающая — проверить, что последняя открытая ей соответствует. Представим, что он использует обычный массив. Технически это работает: append добавляет, pop удаляет с конца. Но интерфейс массива разрешает insert(0, x), delete_at(i), arr[i] = y — операции, которые для парсера бессмысленны и опасны. Если кто-то по ошибке вставит элемент в середину, порядок скобок нарушится.

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

Стек

Стек работает по принципу LIFO — Last In, First Out: последним пришёл, первым вышел. Как стопка тарелок: берёшь верхнюю, которую положил последней.

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

Стек на динамическом массиве идеален: push и pop работают с правого края — массив просто меняет length, никаких сдвигов. Альтернатива — односвязный список (O(1) без resize), но на практике массив выигрывает за счёт кэш-локальности. Call stack работает по LIFO: последняя вызванная функция завершается первой.

Очередь

Стек работает с одного конца. Но задания на принтере обрабатываются в порядке поступления, обход дерева в ширину проходит уровень за уровнем — здесь нужен доступ с противоположного конца: добавляем в хвост, забираем из головы. Это принцип FIFO — First In, First Out: первым пришёл, первым вышел.

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

На односвязном списке с tail очередь реализуется просто: enqueue через tail, dequeue через head — обе операции O(1). Но узлы списка разбросаны по куче, и при интенсивной работе cache misses начинают доминировать. Ring buffer решает это, сохраняя данные в непрерывном массиве.

Ring Buffer: от «мёртвой зоны» к кольцу

Наивная реализация очереди на массиве: enqueue — append в конец, O(1). Dequeue — забрать из начала. Сдвигать все элементы (O(n)) слишком дорого, поэтому вместо сдвига двигаем указатель head:

После нескольких dequeue:
[_][_][_][_][A][B][C][D]
             ↑           ↑
           head        tail

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

Что если, когда tail дошёл до конца массива, он вернётся в начало? «Мёртвая зона» становится свободным местом для новых элементов. Массив логически замкнут в кольцо:

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

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

Переход на следующую позицию: если текущий индекс — последний слот, следующий должен быть нулевым. Операция по модулю делает именно это:

next = (current + 1) % capacity

Индекс 7 в массиве из 8: (7 + 1) % 8 = 0 — переход в начало. Индекс 3: (3 + 1) % 8 = 4 — обычное продвижение. Одна формула покрывает оба случая.

Обе операции (enqueue и dequeue) — O(1). Никаких сдвигов, никакой мёртвой зоны.

Как отличить пустой буфер от полного?

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

Рост буфера

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

Дек

Стек работает с одного конца, очередь — с двух, но роли фиксированы: один для добавления, другой для удаления. Иногда нужны оба конца для обеих операций. Дек (deque — double-ended queue, произносится как “deck”, колода карт) даёт именно это.

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

Односвязный список для дека не подходит: pop_back требует предыдущий узел — O(n). Реализуют дек на ring buffer или двусвязном списке. На практике дек встречается в work-stealing планировщиках (потоки крадут задачи с противоположного конца), алгоритме BFS с приоритетами (0-1 BFS), и реализации sliding window.

Сводка: три уровня свободы

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

Проблема: доступ только по числовому ключу

Все три ADT работают с позицией: начало, конец, индекс. Ключ — всегда число.

Что если нужен доступ по произвольному ключу? Строка “alice”, объект, UUID? Хеш-таблица превращает произвольный ключ в O(1) доступ.

Реализация (Ruby)

Реализация (Ruby)

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

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: push создаёт узел, указывающий на текущий head; pop двигает head на следующий. Оба — O(1). Работа с tail потребовала бы предыдущий узел при pop — O(n) в односвязном списке. Направление указателей (каждый новый узел указывает на тот, что был до него) совпадает с порядком LIFO.

Очередь на ring buffer

В Ruby в stdlib уже есть Queue. Здесь RingQueue — учебная реализация для понимания механики ring buffer.

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

При resize элементы копируются в начало нового буфера, «выпрямляя» кольцо: head сбрасывается в 0 — как при росте динамического массива.