Изменения

[[Файл: 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> {{---}} операция получения количества элементов в очереди удаляется.

== Способы реализации очереди =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> времени.

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

Обычно start указывает == Реализация на голову списке ==Для данной реализации очереди, qнеобходимо создать [end[Список | список] — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив <tex>list</tex> и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается операции работы на 1. С такими алгоритмами одна ячейка из n всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмовсозданном списке.

Преимущества данного методаРеализация очереди на односвязном списке: возможна незначительная экономия памяти по сравнению со вторым способом; проще === 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 ===Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов '''T''' pop(): size-- element = head head = head.next '''return''' element

Преимущества данного метода=== empty === '''boolean''' empty(): размер очереди ограничен лишь объёмом памяти '''return''' head == tail[[Файл: Queue.png|right|230px]]

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

=== Реализация на двух стеках ===Очередь может быть построена из можно реализовать на двух [[стекСтек|стеках]]ов <codetex>S1\mathtt{leftStack}</codetex> и <codetex>S2\mathtt{rightStack}</codetex> как показано ниже. Поступим следующим образом:<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> станет пустым).

[[Файл: queue* <tex> \mathtt{pushLeft} </tex> и <tex> \mathtt{pushRight} </tex> {{---}} функции, реализующие операцию <tex> \mathtt{push} </tex> для соответствующего стека,* <tex> \mathtt{popLeft} </tex> и <tex> \mathtt{popRight} </tex> {{---}} аналогично операции <tex> \mathtt {pop} </tex>.png | 400 px]]

=== 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>O(1)</tex>. В CLI для этого предусмотрен класс System.Collections.Queue с методами Enqueue и Dequeue. В STL присутствует класс queue'''Минусы:'''* если <tex>\mathtt{leftStack}</tex>не пуст, определённый в заголовочном файле queue. В нём используется та же терминология то операция <tex> \mathtt{pop} </tex> может выполняться <tex>O(push и popn)</tex> времени, что и в [[стек]]ахотличие от других реализаций, где <tex> \mathtt{pop} </tex> всегда выполняется за <tex>O(1)</tex>.

== Применение очередей Реализация на шести стеках ==Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.

Клавиатурный буфер BIOS организован Одним из минусов реализации на двух стеках является то, что в виде кольцевого массивахудшем случае мы тратим <tex>O(n)</tex> времени на операцию. Если распределить время, обычно длиной необходимое для перемещения элементов из одного стека в 16 машинных словдругой, по операциям, и двух указателеймы получим очередь без худших случаев с <tex>O(1)</tex> истинного времени на операцию. Подробное описание в статье [[Персистентная очередь#Реализация очереди на шести стеках|Персистентная очередь]]. === Отличия от других реализаций === '''Плюсы: '''* <tex>O(1)</tex> реального времени на следующий элемент операцию,* возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]].  '''Минусы:'''* дольше в нём и на первый незанятый элементсреднем выполняются операции,* больше расход памяти,* большая сложность реализации.

== Ссылки ==[[Категория: Дискретная математика и алгоритмы]]http[[Категория://ru.wikipedia.org/wiki/Очередь_(программирование)Амортизационный анализ]]