Изменения

[[Файл: Fifo_new.png|thumb|right|150px|Очердь]]'''Очередь''' (''Queue'')  — это динамическое множество, добавление и удаление элементов в котором происходит путём операций ''Push'' и ''Pop'' соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется стратегия «первым вошел — первым вышел» (''first-in, first-out — FIFO''). Очередь подобна, например, живой очередь в магазине за хлебом. У нее имеется '''голова''' (''head'') и '''хвост''' (''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте, точно так же, как человек занимает очередь последним, чтобы купить хлеб. Из очереди всегда выводится элемент, который находится в её головной части аналогично тому, как человек, который ждал дольше всех, расплачивается за хлеб.

== Способы реализации Очередь будет обладать следующими полями::<tex>head</tex> (голова очереди ==):<tex>tail</tex> (хвост очереди):<tex>size</tex> (размер очереди)

Существует несколько способов реализации очереди на языках программирования. [[Файл: Fifo.png | 300 px]] === Массив push === Первый способ представляет очередь в виде массива m[] размером n и двух целочисленных переменных push(указателейx) start и end.<br /> Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в m elements[endtail] записывается новый элемент очереди, а end увеличивается на единицу. Если значение end становится равным n, то мы как бы циклически обходим массив и значение переменной становится равным = x tail = (tail + 1. Извлечение элемента из очереди производится аналогично: после извлечения элемента m[start] из очереди переменная start увеличивается на 1, т.е как с переменной end. С такими алгоритмами одна ячейка из n всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов. Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке. Недостатки: максимальное количество элементов в очереди ограничено размером массива. При его переполнении требуется перевыделение памяти и копирование всех элементов в новый массив% elements. length size++=== Связный список ===Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов. Преимущества данного метода: размер очереди ограничен лишь объёмом памяти. Недостатки: сложнее в разработке; требуется больше памяти; при работе с такой очередью память сильнее фрагментируется; работа с очередью несколько медленнее. ==pop = Реализация на двух стеках ===Очередь может быть построена из двух [[стек]]ов <code>S1</code> и <code>S2</code> как показано ниже: [[Файл: queue.png | 400 px]]  '''Процедура''' enqueuepop(''x''): S1.push if (!empty(''x'')) then x = elements[head] '''Процедура''' dequeue head = (head + 1): '''если''' S2 пуст: '''если''' S1 пуст:% elements.length сообщить об ошибке: очередь пуста '''пока''' S1 не пуст:size-- S2.push(S1.pop()) '''return''' S2.pop()  x== Очереди в различных языках программирования = empty ===Практически во всех развитых языках программирования реализованы очереди. В CLI для этого предусмотрен класс System.Collections.Queue с методами Enqueue и Dequeue. В STL присутствует класс queue<>, определённый в заголовочном файле queue. В нём используется та же терминология empty(push и pop), что и в [[стек]]ах.  return size == Применение очередей ==0Очередь Каждая операция выполняется в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура течение времени <tex>O(ведь в этот момент приложение может совершать другие действия1), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие</tex>. Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нём и на первый незанятый элемент.(реализация очереди на массиве)