Изменения

'''Очередь''' (англ. ''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>empty\mathtt{size} </tex> {{- проверка --}} операция получения количества элементов в очереди на наличие в ней элементов.

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

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

'''T''' pop(): '''if !''' (empty()) '''return null''' x = elements[head] head = (head + 1) % elements.length size--n '''return ''' x === empty size === empty'''int''' size() '''if''' head > tail '''return''' n - head + tail '''else''' '''return size == 0''' 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'''): element = tail tail = new listListItem(x, NULL) '''if ''' size == 0 head = tail '''else ''' element.next = tail size++

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

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

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

Очередь можно реализовать на двух [[Стек|стеках]] <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'''): pushLeft(x)

'''T''' pop(): '''if !rigthStack''' '''not''' rightStack.empty() '''return ''' popRight() '''else''' '''while !''' '''not''' leftStack.empty()

'''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>реального времени на операцию,* возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]].

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

== Ссылки Источники информации ==* [http[wikipedia://ru.wikipedia.org/wiki/:Очередь_(программирование) |Википедия {{--- }} Очередь (программирование)]]