Изменения

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

Очередь

5340 байт добавлено, 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>pop\mathtt{elements[0\dots n-1]}</tex> (снятие с очереди), . Она будет обладать следующими полями:* <tex>empty\mathtt{head}</tex> {{--- проверка }} голова очереди на наличие в ней элементов. Очередь, способная вместить не более * <tex>n</tex> элементов, можно реализовать с помощью массива <tex>elements[1..n]\mathtt{tail}</tex>{{---}} хвост очереди.
Очередь будет обладать следующими полями:=== empty ===:<tex>head</tex> '''boolean''' empty(голова очереди)::<tex> '''return''' head == 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.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>) и операции работы очереди на созданном списке. Добавление новых элементов будет происходить посредством операции <tex>push</tex>, чтобы изъять элемент из очереди будем использовать <tex>pop</tex>, для проверки очереди на наличие в ней элементов используем <tex>empty</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|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>. === push === '''function''' push(x : '''T'''): pushLeft(x)=== pop === '''T''' pop(): '''if''' '''not''' rightStack.empty() '''return''' popRight() '''else''' '''while''' '''not''' leftStack.empty() pushRight(popLeft()) '''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> реального времени на операцию,* возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]].  
'''Минусы:'''
*сложение дольше в разработкесреднем выполняются операции,*требуется больше расход памяти,* большая сложность реализации.
== См. также ==
* [[Стек]]
* [[Персистентная очередь]]
== Источники информации ==
* [[wikipedia:ru:Очередь_(программирование)|Википедия {{---}} Очередь (программирование)]]
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 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]
== Ссылки ==[[Категория: Дискретная математика и алгоритмы]]* [http[Категория://ru.wikipedia.org/wiki/Очередь_(программирование) ОчередьАмортизационный анализ]]
13
правок

Навигация