Изменения

[[Файл: Fifo_new.png|thumb|right|150px]]'''Очередь''' (англ. ''Queuequeue'')  —  {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций ''Push'' <tex> \mathtt{push} </tex> и ''Pop'' <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>push\mathtt{n}</tex> (запись в очередь) элементов, можно реализовать с помощью массива <tex>\mathtt{elements[0\dots n- операция вставки нового элемента1]}</tex>.Она будет обладать следующими полями:*<tex>pop\mathtt{head}</tex> (снятие с {{---}} голова очереди) - операция удаления нового элемента.,*<tex>empty\mathtt{tail}</tex> {{--- проверка }} хвост очереди на наличие в ней элементов.

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

'''function''' push(x: '''T'''): '''if''' (size() != n)

tail = (tail + 1) % elements.lengthn size++

'''T''' pop(): '''if !''' (empty()) then '''return null''' x = elements[head] head = (head + 1) % elements.length size--n '''return ''' x === empty size === empty'''int''' size() '''if''' head > tail '''return size == 0''' n - head + tail '''else''' '''return''' tail - headКаждая Из-за того что нам не нужно снова выделять память, каждая операция выполняется в течение времени за <tex>O(1)</tex>времени.

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

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

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

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

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

'''T''' pop(): if !empty() size-- then x element = head.value head = head.next size-- '''return''' element return x

'''boolean''' empty(): '''return size ''' head == 0tail[[Файл: Queue.png|thumb|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>.

'''function''' push(x: '''T'''): leftStack.push pushLeft(x)

'''T''' pop(): '''if ''' '''not''' rightStack.empty() then if !leftStack.empty '''return''' popRight() then '''else''' '''while !''' '''not''' leftStack.empty() do rightStack.push pushRight(popLeft(leftStack.pop)) '''return rightStack''' 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> реального времени на операцию,* возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]].

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

== Ссылки ==[[Категория: Дискретная математика и алгоритмы]]* [http[Категория://ru.wikipedia.org/wiki/Очередь_(программирование) Википедия - Очередь (программирование)Амортизационный анализ]]