1632
правки
Изменения
Очередь
,rollbackEdits.php mass rollback
== Определение ==
[[Файл: Fifo_new.png|right|150px]]'''Очередь'''(англ. 'О́чередь'queue'' — ) {{---}} это структура данных с дисциплиной доступа к элементам «первый пришёл — первый , добавление и удаление элементов в которой происходит путём операций <tex> \mathtt{push} </tex> и <tex> \mathtt{pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (англ. ''tail''). Когда элемент ставится в очередь, First In — First Out)он занимает место в её хвосте. Добавление элемента возможно лишь Из очереди всегда выводится элемент, который находится в конец ее голове. Очередь поддерживает следующие операции:* <tex> \mathtt{empty} </tex> {{---}} проверка очередина наличие в ней элементов,* <tex> \mathtt {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента, выборка — только из начала * <tex> \mathtt{pop} </tex> (снятие с очереди) {{---}} операция удаления нового элемента, при этом выбранный элемент из * <tex> \mathtt{size} </tex> {{---}} операция получения количества элементов в очереди удаляется.
== Реализация циклической очереди на массиве ==
Очередь, способную вместить не более <tex>\mathtt{n}</tex> элементов, можно реализовать с помощью массива <tex>\mathtt{elements[0\dots n-1]}</tex>. Она будет обладать следующими полями:
* <tex>\mathtt{head}</tex> {{---}} голова очереди,
* <tex>\mathtt{tail}</tex> {{---}} хвост очереди.
== Способы реализации очереди =empty === '''boolean''' empty(): '''return''' head == tail
=== pop === '''T''' pop(): '''if''' (empty()) '''return null''' x = elements[[Файл: Fifo.png | 300 px]head] head = (head + 1) % n '''return''' x
=== Массив size === '''int''' size() '''if''' head > tail '''return''' n - head + tail '''else''' '''return''' tail - headИз-за того что нам не нужно снова выделять память, каждая операция выполняется за <tex>O(1)</tex> времени.
=== Связный список pop ===Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов '''T''' pop(): size-- element = head head = head.next '''return''' element
=== push === '''Процедураfunction''' enqueuepush(x : '''T'x''): S1.push pushLeft(x)=== pop === '''T'x''pop(): '''if''' '''Процедураnot''' dequeuerightStack.empty(): '''еслиreturn''' S2 пуст:popRight() '''еслиelse''' S1 пуст: сообщить об ошибке: очередь пуста '''while''' '''покаnot''' S1 не пуст:leftStack.empty() S2.push pushRight(S1.poppopLeft()) '''return''' S2.poppopRight()
При выполнении операции <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>.
== Применение очередей Реализация на шести стеках ==Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.
== См. также ==
* [[Стек]]
* [[Персистентная очередь]]
== Источники информации ==
* [[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]