Просмотр исходного текста страницы Очередь

== Определение ==
[[Файл: Fifo_new.png|right|150px]]
'''Очередь''' (англ. ''queue'')  {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <tex> \mathtt{push} </tex> и <tex> \mathtt{pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (англ. ''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции:
* <tex> \mathtt{empty} </tex> {{---}} проверка очереди на наличие в ней элементов,
* <tex> \mathtt {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента,
* <tex> \mathtt{pop} </tex> (снятие с очереди) {{---}} операция удаления нового элемента,
* <tex> \mathtt{size} </tex> {{---}} операция получения количества элементов в очереди.

== Реализация циклической очереди на массиве ==
Очередь, способную вместить не более <tex>\mathtt{n}</tex> элементов, можно реализовать с помощью массива <tex>\mathtt{elements[0\dots n-1]}</tex>. Она будет обладать следующими полями:
* <tex>\mathtt{head}</tex> {{---}} голова очереди,
* <tex>\mathtt{tail}</tex> {{---}} хвост очереди.

=== empty ===
 '''boolean''' empty():
   '''return''' head == tail

=== push ===
 '''function''' push(x : '''T'''):
   '''if''' (size() != n)
     elements[tail] = x
     tail = (tail + 1) % n

=== pop ===
 '''T''' pop():
   '''if''' (empty()) 
     '''return null'''
   x = elements[head]
   head = (head + 1) % n
   '''return''' x

=== size ===
 '''int''' size()
   '''if''' head > tail
     '''return''' n - head + tail
   '''else'''
     '''return''' tail - head
Из-за того что нам не нужно снова выделять память, каждая операция выполняется за <tex>O(1)</tex> времени.

'''Плюсы:'''
* проста в разработке,
* по сравнению с реализацией на списке есть незначительная экономия памяти.
'''Минусы:'''
* количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива),
* при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив.

== Реализация на списке ==
Для данной реализации очереди необходимо создать [[Список | список]] <tex>list</tex> и операции работы на созданном списке.

Реализация очереди на односвязном списке:
=== List ===
* <code>ListItem(data : '''T''', next : '''ListItem''')</code> {{---}} конструктор,
* <tex>\mathtt{x.value}</tex> {{---}} поле, в котором хранится значение элемента,
* <tex>\mathtt{x.next}</tex> {{---}} указатель на следующий элемент очереди.

=== push ===
 '''function''' push(x : '''T'''):
   element = tail
   tail = ListItem(x, NULL)
   '''if''' size == 0
     head = tail
   '''else''' 
     element.next = tail
   size++

=== pop ===
 '''T''' pop(): 
   size--
   element = head
   head = head.next
   '''return''' element

=== empty ===
 '''boolean''' empty():
   '''return''' head == tail
[[Файл: Queue.png|right|230px]]

'''Плюсы:'''
* каждая операция выполняется за время <tex>O(1)</tex>.
'''Минусы:'''
* память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве.

== Реализация на двух стеках ==
Очередь можно реализовать на двух [[Стек|стеках]] <tex>\mathtt{leftStack}</tex> и <tex>\mathtt{rightStack}</tex>. Поступим следующим образом: <tex>\mathtt{leftStack}</tex> будем использовать для операции <tex> \mathtt {push} </tex>, <tex>\mathtt{rightStack}</tex> для операции <tex> \mathtt{pop} </tex>. При этом, если при попытке извлечения элемента из <tex>\mathtt{rightStack}</tex> он оказался пустым, просто перенесем все элементы из <tex>\mathtt{leftStack}</tex> в него (при этом элементы в <tex>\mathtt{rightStack}</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>\mathtt{leftStack}</tex> станет пустым).

* <tex> \mathtt{pushLeft} </tex> и <tex> \mathtt{pushRight} </tex> {{---}} функции, реализующие операцию <tex> \mathtt{push} </tex> для соответствующего стека,
* <tex> \mathtt{popLeft} </tex> и <tex> \mathtt{popRight} </tex> {{---}} аналогично операции <tex> \mathtt {pop} </tex>.

=== push ===
 '''function''' push(x : '''T'''):
   pushLeft(x)
=== pop ===
 '''T''' pop():
   '''if''' '''not''' rightStack.empty()
     '''return''' popRight() 
   '''else'''
     '''while''' '''not''' leftStack.empty()
       pushRight(popLeft())
     '''return''' popRight()

При выполнении операции <tex> \mathtt{push} </tex> будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию <tex> \mathtt{pop} </tex> из первого стека, третью во второй стек на финальный <tex> \mathtt{pop} </tex>. Тогда для операций <tex> \mathtt{pop} </tex> учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции <tex> \mathtt{push} </tex>.

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

'''Плюсы:'''
* эту реализацию несложно модифицировать для получения минимума в текущей очереди за <tex>O(1)</tex>.
'''Минусы:'''
* если <tex>\mathtt{leftStack}</tex> не пуст, то операция <tex> \mathtt{pop} </tex> может выполняться <tex>O(n)</tex> времени, в отличии от других реализаций, где <tex> \mathtt{pop} </tex> всегда выполняется за <tex>O(1)</tex>.

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

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

Подробное описание в статье [[Персистентная очередь#Реализация очереди на шести стеках|Персистентная очередь]].

=== Отличия от других реализаций ===

'''Плюсы:'''
* <tex>O(1)</tex> реального времени на операцию,
* возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]]. 

'''Минусы:'''
* дольше в среднем выполняются операции,
* больше расход памяти,
* большая сложность реализации.

== См. также ==
* [[Стек]]
* [[Персистентная очередь]]

== Источники информации ==
* [[wikipedia:ru:Очередь_(программирование)|Википедия {{---}} Очередь (программирование)]]
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
* T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262
* [http://hdl.handle.net/1813/6273 ''Hood R., Melville R.'' Real Time Queue Operations in Pure LISP. {{---}} Cornell University, 1980]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]