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

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

== Реализация на массиве ==
Очередь, способную вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>elements[1..n]</tex>. Она будет обладать следующими полями:
* <tex>head</tex> (голова очереди)
* <tex>tail</tex> (хвост очереди)
* <tex>size</tex> (размер очереди)

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

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

=== empty ===
 '''function''' empty():
   '''return''' size == 0
Из-за того что нам не нужно перевыделять память, каждая операция выполняется за <tex>O(1)</tex> времени.

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

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

Реализация очереди на односвязном списке:
=== list ===
* <tex>x.value</tex> - поле, в котором хранится значение элемента
* <tex>x.next</tex> - указатель на следующий элемент очереди

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

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

=== empty ===
 '''function''' empty():
   '''return''' size == 0
[[Файл: Queue.png|right|230px]]
Каждая операция выполняется за время <tex>O(1)</tex>.

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

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

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

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

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

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

'''Минусы:'''
* Если <tex>leftStack</tex> не пуст, то операция <math> \mathrm {pop} </math> может выполняться <tex>O(n)</tex> времени, в отличии от других реализаций, где <math> \mathrm {pop} </math> всегда выполняется за <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]

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