Очередь

Определение

Очередь (Queue)  — это структура данных, добавление и удаление элементов в которой происходит путём операций Push и Pop соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (first-in, first-out — FIFO). У очереди имеется голова (head) и хвост (tail). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове.

• [math]push[/math] (запись в очередь) - операция вставки нового элемента.
• [math]pop[/math] (снятие с очереди) - операция удаления нового элемента.
• [math]empty[/math] - проверка очереди на наличие в ней элементов

Реализация на массиве

Очередь, способную вместить не более [math]n[/math] элементов, можно реализовать с помощью массива [math]elements[1..n][/math]. Она будет обладать следующими полями:

• [math]head[/math] (голова очереди)
• [math]tail[/math] (хвост очереди)
• [math]size[/math] (размер очереди)

push

push(x)
   elements[tail] = x
   tail = (tail + 1) % elements.length
   size++

pop

pop()
   if !empty()
      x = elements[head]
      head = (head + 1) % elements.length
      size--
      return x

empty

empty()
   return size == 0

Из-за того что нам не нужно перевыделять память, каждая операция выполняется за [math]O(1)[/math] времени.

Плюсы:

- прост в разработке

- по сравнению с реализацией на списке, есть незначительная экономия памяти

Минусы:

- количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива)

- при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив

Реализация на списке

Для данной реализации очереди необходимо создать список ([math]list[/math]) и операции работы на созданном списке.

Реализация очереди на односвязном списке:

list

• [math]x.value[/math] - поле, в котором хранится значение элемента
• [math]x.next[/math] - указатель на следующий элемент очереди

push

push(x)
   element = tail
   tail = new list(x, NULL)
   if size == 0
      head = tail
   else 
      element.next = tail
   size++

pop

pop()
   if empty()
      return
   element = head
   head = head.next
   size--
   return element

empty

empty()
   return size == 0

Каждая операция выполняется за время [math]O(1)[/math].

Минусы:

• Память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве

Реализация на двух стеках

Очередь можно реализовать на двух стеках [math]leftStack[/math] и [math]rightStack[/math]. Один из стеков [math](leftStack)[/math] будем использовать для операции [math]push[/math], другой для операции [math]pop[/math]. При этом, если при попытке извлечения элемента из [math]rightStack[/math] он оказался пустым, просто перенесем все элементы из [math]leftStack[/math] в него (при этом элементы в [math]rightStack[/math] получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а [math]leftStack[/math] станет пустым).

• [math]pushLeft[/math] и [math]pushRight[/math] - функции, реализующие операцию [math]push[/math] для соответствующего стека;
• [math]popLeft[/math] и [math]popRight[/math] - аналогично операции [math]pop[/math].

push

push(x)
   pushLeft(x)

pop

if !rigthStack.empty()
   return popRight()

else
   while !leftStack.empty()
      pushRight(popLeft())
   return popRight()

При выполнении операции [math]push[/math] будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию [math]pop[/math] из первого стека, третью во второй стек на финальный [math]pop[/math]. Тогда для операций [math]pop[/math] учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции [math]push[/math].

Таким образом, для каждой операции требуется [math]O(1)[/math] монет, а значит, амортизационная стоимость операций [math]O(1)[/math].

Минусы:

• Если [math]leftStack[/math] не пуст, то операция [math]pop[/math] может выполняться [math]O(n)[/math] времени, в отличии от других реализаций, где [math]pop[/math] всегда выполняется за [math]O(1)[/math]

Реализация на пяти стеках

Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим [math]O(n)[/math] времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с [math]O(1)[/math] истинного времени на операцию.

Для такой очереди можно использовать либо шесть обычных стеков, либо два персистентных и три обычных. Рассмотрим последний вариант как более простой.

Пусть мы имеем стеки [math]L, L', R, R', T[/math], причем стеки [math]L[/math] и [math]L'[/math] используются для операций [math]push[/math], персистентные стеки [math]R[/math] и [math]R'[/math] используются для операций [math]pop[/math], а стек [math]T[/math] используется для перекопирования элементов.

В каждый момент времени в очереди зафиксировано какой [math]Lcur[/math] из стеков [math]L[/math] и [math]L'[/math] используется для помещения туда элементов, пришедших с операцией [math]push[/math], а также какой [math]Rcur[/math] из стеков [math]R[/math] и [math]R'[/math] используется для извлечения оттуда элементов, запрашиваемых операцией [math]pop[/math].

Очередь будет работать в двух режимах:

1. Обычный режим, аналогично реализации на двух стеках.
2. Режим перекопирования (recopy mode). Этот режим активируется, когда при очередной операции в обычном режиме в стеке [math]Lcur[/math] становится больше элементов, чем в стеке [math]Rcur[/math].

При активации режима перекопирования:

• Инициализируется счетчик [math]toCopy=Rcur.size+Lcur.size[/math], который означает, сколько элементов нужно будет скопировать из [math]T[/math].
• Текущий стек для операций [math]push[/math] меняется с [math]Lcur[/math] на другой стек.

В режиме перекопирования на каждую операцию выполняются дополнительные действия. Поскольку в этом режиме остаются корректными все операции [math]push[/math] и [math]Rcur.size[/math] операций [math]pop[/math], которые мы сможем выполнить на персистентном стеке [math]Rcur[/math], можно предполагать, что на перекопирование у нас есть по крайней мере [math]n + 1 = Rcur.size + 1[/math] операций, включая ту, которая активировала этот режим.

Суммарно за эти операции мы должны сделать:

1. Перемещение содержимого стека [math]Rcur[/math] в стек [math]T[/math], это [math]n[/math] операций.
2. Перемещение содержимого стека [math]Lcur[/math] в стек [math]T[/math], это [math]n + 1[/math] операция.
3. Перемещение содержимого стека [math]T[/math] во второй стек для извлечения, это [math]2 \cdot n + 1[/math] операций.

Счетчик [math]toCopy[/math] уменьшается в двух случаях:

• Мы переместили часть содержимого [math]T[/math] в стек для извлечения.
• Нам пришел запрос [math]pop[/math] и мы уменьшили [math]toCopy[/math] на 1, чтобы показать, что один из элементов [math]Rcur[/math] на дне [math]T[/math] уже был извлечен.

Итого имеем суммарно [math]4 \cdot n + 2[/math] дополнительные стековые операции, которые мы должны сделать за [math]n + 1[/math] операций, то есть [math]4[/math] дополнительных операции на одну обычную, что означает [math]O(1)[/math] истинного времени на операцию.

См. также

• Стек

Ссылки

• Википедия - Очередь (программирование)
• Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
• T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262