Изменения

'''Очередь''' (англ. ''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-- return element = head head = head.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>\mathtt{leftStack}</tex> не пуст, то операция <tex>\mathtt{pop} </tex> может выполняться <tex>O(n)</tex> времени, в отличии отличие от других реализаций, где <tex>\mathtt{pop} </tex> всегда выполняется за <tex>O(1)</tex>.

Сначала будем действовать аналогично случаю с двумя стеками. Пусть у нас есть стек <tex>L</tex> для операций <tex>push</tex> и стек <tex>R</tex> для операций <tex>pop</tex>. К моменту опустошения стека <tex>R</tex> нам нужно успеть получить стек <tex>R'</tex>, содержащий текущие элементы стека <tex>L</tex> Подробное описание в правильном для извлечения порядке. Перекопирование (''recopy mode'') начнется, когда появится опасность того, что мы не сможем за оставшиеся <tex>R.size</tex> операций <tex>pop</tex> со стеком <tex>R</tex> перекопировать стек <tex>L</tex> в новый стек <tex>R'</tex>. Очевидно, это ситуация <tex>L.size>R.size</tex>, пусть такое состояние отражает специальная переменная логического типа <tex>recopy</tex>. Понятно, что во время перекопирования могут поступить операции <tex>push</tex>, а стек <tex>L</tex> в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек <tex>L'</tex>, в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями <tex>L,L'</tex> и <tex>R,R'</tex>, и вроде бы все станет хорошо. Однако, если реализовать этот алгоритм, мы получим неприятную вещь: старый стек <tex>R</tex> может и не опустошиться за это время, то есть мы получили два стека с выходными данными, а значит, возможен случай (например, если все поступающие операции {{---}} <tex>push</tex>), когда при следующем перекопировании у нас не будет свободного стека для копировании туда элементов <tex>L</tex>. Для преодоления этой проблемы мы принудительно будем извлекать все элементы из стека <tex>R</tex> во вспомогательный стек <tex>T</tex>, затем копировать элементы из стека <tex>L</tex> в <tex>R</tex>, а затем обратно копировать элементы из стека <tex>T</tex> в <tex>R</tex>. Легко показать, что приведенный алгоритм как раз получает на выходе в <tex>R</tex> все элементы стеков <tex>L,R</tex> в правильном порядке. Но этого еще недостаточно. Если мы принудительно извлекаем элементы из стека <tex>R</tex>, появляются следующие проблемы:# Что вернуть при операции <tex>pop</tex>? Для этого заведем себе стек <tex>Rc</tex> {{---}} копию стека <tex>R</tex>, из которого мы и будем извлекать требуемые элементы.статье [[Персистентная очередь# Как поддерживать корректность такой копии? Поскольку этот стек нужен только для перекопирования, а во время него он занят, нужна запасная копия <tex>Rc'</tex> для копирования всех элементов, которые мы копируем в <tex>R</tex>, а по окончании перекопирования поменяем ролями стеки <tex>Rc, Rc'</tex>, как мы делали со стеками <tex>L, L'</tex>.# Как учесть, что во время перекопирования часть элементов была извлечена из <tex>Rc</tex>? Для этого заведем специальную переменную <tex>toCopy</tex>, которая показывает, сколько корректных элементов находится в стеке <tex>T</tex>, и уменьшается при каждом извлечении из <tex>T</tex> или операции <tex>pop</tex>. К счастью, все некорректные элементы будут нарастать со дна стека, так что мы никогда не извлечем некорректный элемент, если <tex>toCopy>0</tex>. Если во время операции <tex>pop</tex> у нас <tex>toCopy = 0</tex>, это означает, что теперь в стеке <tex>R</tex> находится весь правый кусок Реализация очереди, так что нам придется извлечь элемент из него. Теперь может возникнуть проблема с непустым <tex>Rc</tex> после завершения перекопирования. Покажем, что мы всегда успеем его опустошить, если будем использовать дополнительное извлечение из него при каждой операции в обычном режиме, для этого полностью проанализируем алгоритм. Пусть на начало перекопирования в стеке <tex>R</tex> содержится <tex>n</tex> элементов, тогда в стеке <tex>L</tex> находится <tex>n+1</tex> элементов. Мы корректно можем обработать любое количество операций <tex>push</tex>, а также <tex>n</tex> операций <tex>pop</tex>. Заметим, что операция <tex>empty</tex> во время перекопирования всегда возвращает <tex>false</tex>, так как мы не можем извлекать элементы из стека <tex>L</tex>, который не пустой. Таким образом вместе с операцией, активирующей перекопирование, мы гарантированно можем корректно обработать <tex>n + 1</tex> операцию. Посмотрим на дополнительные действия, которые нам предстоят:# Переместить содержимое <tex>R</tex> в <tex>T</tex>, <tex>n</tex> действий.# Переместить содержимое <tex>L</tex> в стеки <tex>R, Rc'</tex>, <tex>n + 1</tex> действий.# Переместить первые <tex>toCopy</tex> элементов из <tex>T</tex> в <tex>R, Rc'</tex>, остальные выкинуть, <tex>n</tex> действий.# Поменять ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>, <tex>2</tex> действия. Таким образом, получили <tex>3 \cdot n + 3</tex> дополнительных действия за <tex>n + 1</tex> операций, или <tex>3=O(1)</tex> дополнительных действий на операцию в режиме перекопирования, что и требовалось. Теперь рассмотрим, как изменились наши стеки за весь период перекопирования. Договоримся, что операция <tex>empty</tex> не меняет очередь, то есть никакие дополнительные действия не совершаются. Пусть за <tex>n</tex> следующих за активацией меняющих операций (<tex>push, pop</tex>) поступило <tex>x</tex> операций <tex>pop</tex>, <tex>n - x</tex> операций <tex>push</tex>. Очевидно, что после перекопирования в новых шести стеках окажется: <tex>n-x</tex> элементов в <tex>L</tex>, <tex>2 \cdot n + 1 - x = (n - x) + (n + 1)</tex> элементов в <tex>R</tex>, то есть до следующего перекопирования еще <tex>n+2</tex> операции. С другой стороны, стек <tex>Rc</tex> содержал всего <tex>n</tex> элементов, так что мы можем очистить его, просто удаляя по одному элементу при каждой операции в обычном режиме. Итак, |Персистентная очередь <tex>Q</tex> будет состоять из шести стеков <tex>L,L',R,Rc,Rc',T</tex>, а также двух внутренних переменных <tex>recopy, toCopy</tex>, которые нужны для корректности перекопирования + дополнительная переменная <tex>copied</tex>, показывающая, перемещали ли мы элементы из стека <tex>L</tex> в стек <tex>R</tex>, чтобы не начать перемещать эти элементы в стек <tex>T</tex>.  Инвариант очереди (обычный режим):# Стек <tex>L</tex> содержит левую половину очереди, порядок при извлечении обратный.# Стек <tex>R</tex> содержит правую половину очереди, порядок при извлечении прямой.# <tex>L.size \leqslant R.size</tex># <tex>R.size = 0 \equiv Q.size = 0</tex># <tex>Rc</tex> {{---}} копия <tex>R</tex># <tex>Rc'.size < R.size - L.size</tex># <tex>L'.size = 0, T.size = 0</tex> Тогда к следующему перекопированию (<tex>L.size=R.size+1</tex>) мы гарантированно будем иметь пустые стеки <tex>L',T,Rc'</tex>, которые нам понадобятся. Инвариант очереди (режим перекопирования):# <tex>Rc.size = toCopy</tex># Если <tex>L.size = 0</tex>, то:## При <tex>toCopy > 0</tex> первые <tex>toCopy</tex> элементов <tex>T</tex> {{---}} корректны, то есть действительно содержатся в очереди.## При <tex>toCopy \leqslant 0</tex> стек <tex>R</tex> содержит весь правый кусок очереди в правильном порядке. Очередь будет работать в двух режимах:# Обычный режим, кладем в <tex>L</tex>, извлекаем из <tex>R</tex> и из <tex>Rc, Rc'</tex> для поддержания порядка, операция <tex>empty = (R.size = 0)</tex>.# Режим перекопирования, кладем в <tex>L'</tex>, извлекаем из <tex>Rc</tex>, возможно из <tex>R</tex>, <tex>empty=false</tex>, совершаем дополнительные действия. Также после операции в обычном режиме следует проверка на активацию перекопирования (<tex>recopy = (L.size > R.size)</tex>), если это так, <tex>toCopy=R.size, recopy=true, copied = false</tex>, совершается первый набор дополнительных действий. После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>recopy=(T.size==0)</tex>), а при завершении меняются ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>. Следующий псевдокод выполняет требуемые операции:=== empty ===<code> empty() '''return''' !recopy '''and''' R.size == 0</code>=== push ===<code> push(x) '''if''' !recopy: L.push(x) '''if''' Rc'.size > 0: Rc'.pop() checkRecopy() '''else''': L'.push(x) checkNormal()</code>=== pop ===<code> pop() '''if''' !recopy: tmp = R.pop() Rc.pop() '''if''' Rc'.size > 0: Rc'.pop() checkRecopy() '''return''' tmp '''else''': tmp = Rc.pop() '''if''' toCopy > 0: toCopy = toCopy - 1 '''else''': R.pop() Rc'.pop() checkNormal() '''return''' tmp</code> === checkRecopy ===<code> checkRecopy() recopy = L.size > R.size '''if''' recopy: toCopy = R.size copied = false checkNormal()</code> === checkNormal ===<code> checkNormal() additionalOperations() // Если мы не все перекопировали, то у нас не пуст стек T recopy = T.size <tex> \ne </tex> 0</code>=== additionalOperations ===<code> additionalOperations() // Нам достаточно 3 операций на вызов toDo = 3 // Пытаемся перекопировать R в T '''while''' '''not''' copied '''and''' toDo > 0 '''and''' R.size > 0: T.push(R.pop()) toDo = toDo - 1 // Пытаемся перекопировать L в R и Rc' '''while''' toDo > 0 '''and''' L.size > 0: copied = true x = L.pop() R.push(x) Rc'.push(x) toDo = toDo - 1 // Пытаемся перекопировать T в R и Rc' с учетом toCopy '''while''' toDo > 0 '''and''' T.size > 0: x = T.pop() '''if''' toCopy > 0: R.push(x) Rc'.push(x) toCopy = toCopy - 1 toDo = toDo - 1 // Если все скопировано, то меняем роли L, L' и Rc, Rc' '''if''' T]].size == 0: swap(L, L') swap(Rc, Rc')</code>

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

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

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