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

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

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

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

Массив

Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end.

Обычно 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())

    вернуть S2.pop()

Такой способ реализации наиболее удобен в качестве основы для построения персистентной очереди.

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

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

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

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

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

См. также

• Коллекция
• Массив
• Список
• Стек
• Двухсторонняя очередь
• Очередь с приоритетом
• Именованный канал
• FIFO (информатика)
• LIFO (информатика)

Ссылки

• [www.nist.gov/dads/HTML/queue.html Определение с NIST]

Отрывок, характеризующий Очередь (программирование)

– Он у меня тактик великий! – сказал князь сыну, указывая на архитектора.
И разговор зашел опять о войне, о Бонапарте и нынешних генералах и государственных людях. Старый князь, казалось, был убежден не только в том, что все теперешние деятели были мальчишки, не смыслившие и азбуки военного и государственного дела, и что Бонапарте был ничтожный французишка, имевший успех только потому, что уже не было Потемкиных и Суворовых противопоставить ему; но он был убежден даже, что никаких политических затруднений не было в Европе, не было и войны, а была какая то кукольная комедия, в которую играли нынешние люди, притворяясь, что делают дело. Князь Андрей весело выдерживал насмешки отца над новыми людьми и с видимою радостью вызывал отца на разговор и слушал его.
– Всё кажется хорошим, что было прежде, – сказал он, – а разве тот же Суворов не попался в ловушку, которую ему поставил Моро, и не умел из нее выпутаться?
– Это кто тебе сказал? Кто сказал? – крикнул князь. – Суворов! – И он отбросил тарелку, которую живо подхватил Тихон. – Суворов!… Подумавши, князь Андрей. Два: Фридрих и Суворов… Моро! Моро был бы в плену, коли бы у Суворова руки свободны были; а у него на руках сидели хофс кригс вурст шнапс рат. Ему чорт не рад. Вот пойдете, эти хофс кригс вурст раты узнаете! Суворов с ними не сладил, так уж где ж Михайле Кутузову сладить? Нет, дружок, – продолжал он, – вам с своими генералами против Бонапарте не обойтись; надо французов взять, чтобы своя своих не познаша и своя своих побиваша. Немца Палена в Новый Йорк, в Америку, за французом Моро послали, – сказал он, намекая на приглашение, которое в этом году было сделано Моро вступить в русскую службу. – Чудеса!… Что Потемкины, Суворовы, Орловы разве немцы были? Нет, брат, либо там вы все с ума сошли, либо я из ума выжил. Дай вам Бог, а мы посмотрим. Бонапарте у них стал полководец великий! Гм!…
– Я ничего не говорю, чтобы все распоряжения были хороши, – сказал князь Андрей, – только я не могу понять, как вы можете так судить о Бонапарте. Смейтесь, как хотите, а Бонапарте всё таки великий полководец!
– Михайла Иванович! – закричал старый князь архитектору, который, занявшись жарким, надеялся, что про него забыли. – Я вам говорил, что Бонапарте великий тактик? Вон и он говорит.
– Как же, ваше сиятельство, – отвечал архитектор.
Князь опять засмеялся своим холодным смехом.
– Бонапарте в рубашке родился. Солдаты у него прекрасные. Да и на первых он на немцев напал. А немцев только ленивый не бил. С тех пор как мир стоит, немцев все били. А они никого. Только друг друга. Он на них свою славу сделал.
И князь начал разбирать все ошибки, которые, по его понятиям, делал Бонапарте во всех своих войнах и даже в государственных делах. Сын не возражал, но видно было, что какие бы доводы ему ни представляли, он так же мало способен был изменить свое мнение, как и старый князь. Князь Андрей слушал, удерживаясь от возражений и невольно удивляясь, как мог этот старый человек, сидя столько лет один безвыездно в деревне, в таких подробностях и с такою тонкостью знать и обсуживать все военные и политические обстоятельства Европы последних годов.
– Ты думаешь, я, старик, не понимаю настоящего положения дел? – заключил он. – А мне оно вот где! Я ночи не сплю. Ну, где же этот великий полководец твой то, где он показал себя?
– Это длинно было бы, – отвечал сын.
– Ступай же ты к Буонапарте своему. M lle Bourienne, voila encore un admirateur de votre goujat d'empereur! [вот еще поклонник вашего холопского императора…] – закричал он отличным французским языком.
– Vous savez, que je ne suis pas bonapartiste, mon prince. [Вы знаете, князь, что я не бонапартистка.]
– «Dieu sait quand reviendra»… [Бог знает, вернется когда!] – пропел князь фальшиво, еще фальшивее засмеялся и вышел из за стола.
Маленькая княгиня во всё время спора и остального обеда молчала и испуганно поглядывала то на княжну Марью, то на свекра. Когда они вышли из за стола, она взяла за руку золовку и отозвала ее в другую комнату.