Изменения

{{В разработке}}== Определение ==[[Файл: Fifo_new.png|right|150px]]'''О́чередьОчередь''' (англ. ''queue'' — [[)  {{---}} это структура данных]] с дисциплиной доступа к элементам «первый пришёл — первый , добавление и удаление элементов в которой происходит путём операций <tex> \mathtt{push} </tex> и <tex> \mathtt{pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO, First In — First Out''). Добавление элемента У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (принято обозначать словом enqueue — поставить англ. ''tail''). Когда элемент ставится в очередь) возможно лишь , он занимает место в конец её хвосте. Из очередивсегда выводится элемент, выборка — только из начала который находится в ее голове. Очередь поддерживает следующие операции:* <tex> \mathtt{empty} </tex> {{---}} проверка очереди на наличие в ней элементов,* <tex> \mathtt {push} </tex> (что принято называть словом dequeue — убрать из запись в очередь) {{---}} операция вставки нового элемента,* <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> {{---}} хвост очереди.

=== Массив push === '''function''' push(x : '''T'''): '''if''' (size() != n) elements[tail] = x tail = (tail + 1) % n

Первый способ представляет очередь в виде [[массив]]а и двух целочисленных [[переменная|переменных]] start и end.<br />=== pop ===[[Файл '''T''' pop():Queue1.gif]]<br />Обычно <code>start</code> указывает на голову очереди, <code>end</code> — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в <code>q '''if''' (empty()) '''return null''' x = elements[endhead]</code> записывается новый элемент очереди, а <code>end</code> уменьшается на единицу. Если значение end становится меньше head = (head + 1, то мы как бы циклически обходим массив и значение переменной становится равным ) % n. Извлечение элемента из очереди производится аналогично: после извлечения элемента <code>q[start]</code> из очереди переменная <code>start</code> уменьшается на 1. С такими алгоритмами одна ячейка из <code>n</code> всегда будет незанятой (так как очередь с <code>n</code> элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов. '''return''' x

Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке=== size === '''int''' size() '''if''' head > tail '''return''' n - head + tail '''else''' '''return''' tail - headИз-за того что нам не нужно снова выделять память, каждая операция выполняется за <tex>O(1)</tex> времени.

Недостатки'''Плюсы: максимальное '''* проста в разработке,* по сравнению с реализацией на списке есть незначительная экономия памяти.'''Минусы:'''* количество элементов в очереди ограничено размером массива. При его (исправляется написанием функции расширения массива),* при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив.

=== Связный список =Реализация на списке ==Второй способ основан на работе с динамической памятью. Очередь представляется в качестве Для данной реализации очереди необходимо создать [[линейный Список | список|линейного списка]], в котором добавление<tex>list</удаление элементов идет строго с соответствующих его концовtex> и операции работы на созданном списке.

Преимущества данного методаРеализация очереди на односвязном списке:=== List ===* <code>ListItem(data : '''T''', next : размер '''ListItem''')</code> {{---}} конструктор,* <tex>\mathtt{x.value}</tex> {{---}} поле, в котором хранится значение элемента,* <tex>\mathtt{x.next}</tex> {{---}} указатель на следующий элемент очереди ограничен лишь объёмом памяти.

Недостатки=== push === '''function''' push(x : сложнее в разработке; требуется больше памяти; при работе с такой очередью память сильнее фрагментируется; работа с очередью несколько медленнее'''T'''): element = tail tail = ListItem(x, NULL) '''if''' size == 0 head = tail '''else''' element.next = tail size++

=== Реализация на двух стеках pop ===Очередь может быть построена из двух [[стек]]ов <code>S1</code> и <code>S2</code> как показано ниже '''T''' pop(): size-- element = head head = head.next '''return''' element

'''Процедура''' enqueue(''x''): S1.push(''x'') === empty === '''Процедураboolean''' dequeueempty(): '''еслиreturn''' S2 пуст:head == tail '''если''' S1 пуст[[Файл: сообщить об ошибке: очередь пуста '''пока''' S1 не пуст: S2.push(S1Queue.pop()) '''return''' S2.pop()png|right|230px]]

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

== Очереди в различных языках программирования Реализация на двух стеках ==Практически во всех развитых языках программирования реализованы очереди. В Очередь можно реализовать на двух [[Common Language InfrastructureСтек|CLIстеках]] <tex>\mathtt{leftStack}</tex> и <tex>\mathtt{rightStack}</tex>. Поступим следующим образом: <tex>\mathtt{leftStack}</tex> будем использовать для этого предусмотрен класс Systemоперации <tex> \mathtt {push} </tex>, <tex>\mathtt{rightStack}</tex> для операции <tex> \mathtt{pop} </tex>.Collections.Queue с методами Enqueue и Dequeue. В [[Стандартная библиотека шаблонов|STL]] также присутствует класс queueПри этом, если при попытке извлечения элемента из <tex>\mathtt{rightStack}</tex>он оказался пустым, определённый просто перенесем все элементы из <tex>\mathtt{leftStack}</tex> в заголовочном файле queue. В нём используется та же терминология него (push и pop)при этом элементы в <tex>\mathtt{rightStack}</tex> получатся уже в обратном порядке, что нам и в [[стек]]ахнужно для извлечения элементов, а <tex>\mathtt{leftStack}</tex> станет пустым).

== Применение очередей ==Очередь в программировании используется, как * <tex> \mathtt{pushLeft} </tex> и в реальной жизни, когда нужно совершить какие<tex> \mathtt{pushRight} </tex> {{--то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение}} функции, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередьреализующие операцию <tex> \mathtt{push} </tex> для соответствующего стека, * <tex> \mathtt{popLeft} </tex> и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие<tex> \mathtt{popRight} </tex> {{---}} аналогично операции <tex> \mathtt {pop} </tex>.

Клавиатурный буфер [[BIOS]]=== 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> времени, обычно длиной в 16 машинных словотличие от других реализаций, и где <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]