Изменения

Перейти к: навигация, поиск

Очередь

4313 байт добавлено, 17:56, 10 июля 2019
м
Поправка грамматики.
== Определение ==
[[Файл: 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> (размер очереди)
=== push ===
'''function''' push(x: '''T'''): '''if''' (size() != n)
elements[tail] = x
tail = (tail + 1) % elements.lengthn size++
=== pop ===
'''T''' pop(): '''if !''' (empty()) then '''return null''' x = elements[head] head = (head + 1) % elements.lengthn size-- '''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> {{--- }} указатель на следующий элемент очереди.
=== push ===
'''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++ 
=== pop ===
'''T''' pop(): if !empty() size-- then x element = head.value head = head.next size-- '''return''' element return x
=== empty ===
'''boolean''' empty(): '''return size ''' head == 0tail[[Файл: Queue.png|thumb|right|230px]]Каждая операция выполняется за время <tex>O(1)</tex>.
'''Плюсы:'''
* каждая операция выполняется за время <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>.
=== push ===
'''function''' push(x: '''T'''): leftStack.push pushLeft(x)
=== pop ===
'''T''' pop(): '''if ''' '''not''' rightStack.empty() then '''return''' popRight() '''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[wikipedia://ru.wikipedia.org/wiki/:Очередь_(программирование) |Википедия {{--- }} Очередь (программирование)]]
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
13
правок

Навигация