Изменения

'''Очередь''' (англ. ''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_1, L_2, R, Rc_1, Rc_2, T</tex>, причем стеки <tex>L_1, L_2</tex> используются для операций <tex>push</tex>, стек <tex>R</tex> используется для операций <tex>pop</tex>, стеки <tex>Rc_1, Rc_2</tex> используются Подробное описание в качестве копий стека <tex>R</tex>, стек <tex>T</tex> используется для перекопирования элементовстатье [[Персистентная очередь#Реализация очереди на шести стеках|Персистентная очередь]].

Также очередь будет запоминать, находится ли она сейчас в режиме перекопирования (''recopy mode'Плюсы:'''), в который переходит из обычного режима, когда после очередной операции в стеке * <tex>LO(1)</tex> становится больше элементовреального времени на операцию, чем в стеке <tex>R</tex>. При активации инициализируется счетчик <tex>toCopy</tex>, показывающий* возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], сколько находится неизвлеченных элементов в стеке <tex>Rc</tex>если использовать [[Персистентный стек|персистентные стеки]].

Пусть в этот момент в стеке <tex>R</tex>, а значит и в стеке <tex>Rc</tex> находились <tex>n</tex> элементов, тогда в стеке <tex>L</tex> их <tex>n+1</tex>. Обрабатываем поступающие дальше операции следующим образом: <tex>push</tex> кладет элемент в парный нашему стеку <tex>L</tex> стек <tex>L'</tex>, а <tex>pop</tex> извлекает элемент только из <tex>Rc</tex>, при этом уменьшая счетчик <tex>toCopy</tex>, <tex>empty</tex> в этом режиме всегда возвращает <tex>false</tex>, так как перекопирование закончится раньше, чем опустошится <tex>Rc</tex>, а у нас еще есть элементы в <tex>L</tex>.  Заметим, что мы можем корректно обработать все операции <tex>push</tex> и первые <tex>n</tex> операций <tex>pop</tex>, то есть у нас есть на перекопирование не меньше <tex>n+1</tex> операции вместе с активирующей.  Корректной ситуация станет, когда в стеках <tex>R</tex> и парном стеке <tex>Rc'</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'</tex> текущей копией стека <tex>R</tex>, а <tex>L'</tex> {{---}} текущим стеком для операций <tex>push</tex>, <tex>2</tex> действия. Таким образом, получили <tex>3 \cdot n + 3</tex> действий на <tex>n + 1</tex> операций с очередью, то есть выполняя 3 дополнительных действия во время операции мы успеем перекопировать все элементы вовремя. Тогда очередь действительно будет выполнять каждое действие за <tex>O(1)</tex> реального времени. Теперь рассмотрим, какие изменения произошли за время перекопирования. Пусть среди <tex>n</tex> следующих за активацией операций у нас <tex>x</tex> операций <tex>pop</tex> и <tex>n-x</tex> операций <tex>push</tex>. Тогда в стеке <tex>R</tex> оказалось <tex>2 \cdot n + 1 - x</tex> элементов, а в новом стеке <tex>L</tex> оказалось <tex>n - x</tex> элементов. Тогда в стеке <tex>R</tex> на <tex>n+1</tex> больше элементов, чем * дольше в стеке <tex>L</tex>, а это значит, что до следующего режима перекопирования <tex>n + 2</tex> среднем выполняются операции, и за это время мы успеем очистить старый стек <tex>Rc</tex>, в котором находится максимум <tex>n</tex> ненужных элементов, просто удаляя при каждой операции в обычном режиме один элемент из <tex>Rc</tex>, если он непуст. Заметим, что вышеприведенный алгоритм гарантирует нам, что в обычном режиме в стеке <tex>L</tex> находится не * больше элементов, чем в <tex>R</tex>, так что проверка на пустоту очереди при обычном режиме сводится к проверке на пустоту стека <tex>R</tex>. Пусть наша очередь <tex>Q</tex> имеет стеки <tex>L1, L2, R, Rc1, Rc2, T</tex>, а также переменные <tex>recopy</tex> и <tex>toCopy</tex>, тогда следующий псевдокод выполняет требуемые операции.=== empty ===<code> empty() return !recopy and R.size == 0</code>=== push ===<code> push(x) if !recopy L1.push(x) checkRecopy() else L2.push(x) checkNormal()</code>=== pop ===<code> pop() if !recopy tmp = R.pop() Rc1.pop() checkRecopy() return tmp else tmp = Rc1.pop() toCopy = toCopy - 1 checkNormal() return tmp</code>=== checkRecopy ===<code> checkRecopy() if Rc2.size > 0 Rc2.pop() recopy = L1.size > R.size if recopy toCopy = Rc1.size additionalOperations()</code>=== checkNormal ===<code> checkNormal() additionalOperations() // Если мы не все перекопировали, то у нас не пуст стек T recopy = T.size != 0</code>=== additionalOperations ===<code> additionalOperations() // Нам достаточно 3 операций на вызов toDo = 3 // Пытаемся перекопировать R в T while toDo > 0 and R.size > 0 T.push(R.pop()) toDo = toDo - 1 // Пытаемся перекопировать L1 в R и Rc2 while toDo > 0 and L1.size > 0 x = L1.pop() R.push(x) Rc2.push(x) toDo = toDo - 1 // Пытаемся перекопировать T в R и Rc2 с учетом toCopy while toDo > 0 and T.size > 0 x = T.pop() if toCopy > 0 R.push(x) Rc2.push(x) toCopy = toCopy - 1 toDo = toDo - 1 // Если все скопировано, то меняем роли L1, L2 и Rc1, Rc2 if T.size = 0 swap(L1, L2) swap(Rc1, Rc2)</code> '''Плюсы''':* <tex>O(1)</tex> реального времени на операцию.* Возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]].  '''Минусы''':* Больше константа на операции.* Больше расход памяти.,* Больше большая сложность реализации.

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