Очередь

Определение

Очередь (Queue)  — это динамическое множество, добавление и удаление элементов в котором происходит путём операций Push и Pop соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется стратегия «первым вошел — первым вышел» (first-in, first-out — FIFO).

Способы реализации очереди

Существует несколько способов реализации очереди на языках программирования.

Массив

Первый способ представляет очередь в виде массива m[] размером n и двух целочисленных переменных (указателей) start и end.

Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в m[end] записывается новый элемент очереди, а end увеличивается на единицу. Если значение end становится равным n, то мы как бы циклически обходим массив и значение переменной становится равным 1. Извлечение элемента из очереди производится аналогично: после извлечения элемента m[start] из очереди переменная start увеличивается на 1, т.е как с переменной end. С такими алгоритмами одна ячейка из n всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов.

Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке.

Недостатки: максимальное количество элементов в очереди ограничено размером массива. При его переполнении требуется перевыделение памяти и копирование всех элементов в новый массив.

Связный список

Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов.

Преимущества данного метода: размер очереди ограничен лишь объёмом памяти.

Недостатки: сложнее в разработке; требуется больше памяти; при работе с такой очередью память сильнее фрагментируется; работа с очередью несколько медленнее.

Реализация на двух стеках

Очередь может быть построена из двух стеков S1 и S2 как показано ниже:

Процедура enqueue(x):
    S1.push(x)

Процедура dequeue():
    если S2 пуст:
        если S1 пуст:
            сообщить об ошибке: очередь пуста

        пока S1 не пуст:
            S2.push(S1.pop())

    return S2.pop()

Очереди в различных языках программирования

Практически во всех развитых языках программирования реализованы очереди. В CLI для этого предусмотрен класс System.Collections.Queue с методами Enqueue и Dequeue. В STL присутствует класс queue<>, определённый в заголовочном файле queue. В нём используется та же терминология (push и pop), что и в стеках.

Применение очередей

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

Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нём и на первый незанятый элемент.(реализация очереди на массиве)

См. также

• Стек

Ссылки

http://ru.wikipedia.org/wiki/Очередь_(программирование)