Очередь (программирование)

Очередь (программирование)

О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

Содержание

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

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

Массив

Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end.
Queue1.gif
Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается на 1. С такими алгоритмами одна ячейка из 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 машинных слов, и двух указателей: на следующий элемент в нём и на первый незанятый элемент.

См. также

Ссылки

Логотип Викисловаря
В Викисловаре есть статья «очередь»

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Очередь (программирование)" в других словарях:

  • Очередь (компьютер) — Очередь  определённый порядок в следовании или в движении чего либо или кого либо. Живая очередь Очередь (программирование) Очередь (экономика) [1] Очередь (роман) роман Владимира Сорокина Очередью также называют несколько патронов, выпущенных за …   Википедия

  • Очередь — Очередь  определённый порядок в следовании или в движении чего либо или кого либо. Живая очередь «Очередь» польская настольная игра. Очередь (программирование) Очередью также называют несколько патронов, выпущенных за один раз …   Википедия

  • Программирование — Эта статья должна быть полностью переписана. На странице обсуждения могут быть пояснения. У этого термина существуют и другие значения, см. Программи …   Википедия

  • Программирование —         процесс составления упорядоченной последовательности действий (программы (См. Программа)) для ЭВМ; научная дисциплина, изучающая программы для ЭВМ и способы их составления, проверки и улучшения.          Каждая ЭВМ является автоматом,… …   Большая советская энциклопедия

  • ПРОГРАММИРОВАНИЕ, МАТЕМАТИЧЕСКОЕ — раздел прикладной математики, применяющийся в качестве метода в экономических исследованиях. Разрабатывает теорию и методы решения условных экстремальных задач, является основной частью формального аппарата анализа разнообразных задач управления …   Большой экономический словарь

  • Двусвязная очередь — (жарг. дэк, дек от англ. deque double ended queue; двухсторонняя очередь, двусвязный список, очередь с двумя концами) структура д …   Википедия

  • МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ — математическая дисциплина, посвященная теории и методам решения задач о нахождении экстремумов функций на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами). М. п.… …   Математическая энциклопедия

  • Математическое программирование —         математическая дисциплина, посвященная теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами).          М. п. раздел науки об… …   Большая советская энциклопедия

  • Объектно-ориентированное программирование — Эта статья во многом или полностью опирается на неавторитетные источники. Информация из таких источников не соответствует требованию проверяемости представленной информации, и такие ссылки не показывают значимость темы статьи. Статью можно… …   Википедия

  • Парадигма (программирование) — Парадигма программирования  это совокупность идей и понятий, определяющая стиль написания программ. Парадигма, в первую очередь, определяется базовой программной единицей и самим принципом достижения модульности программы. В качестве этой единицы …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»