Очередь — различия между версиями
| Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
| − | '''О́чередь''' — | + | == Определение == |
| + | '''О́чередь''' — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента возможно лишь в конец очереди, выборка — только из начала очереди, при этом выбранный элемент из очереди удаляется. | ||
| + | |||
== Способы реализации очереди == | == Способы реализации очереди == | ||
Существует несколько способов реализации очереди на языках программирования. | Существует несколько способов реализации очереди на языках программирования. | ||
| + | |||
| + | [[Файл: Fifo.png | 300 px]] | ||
=== Массив === | === Массив === | ||
| − | Первый способ представляет очередь в виде | + | Первый способ представляет очередь в виде массива q и двух целочисленных переменных start и end.<br /> |
| − | + | ||
| − | Обычно | + | Обычно start указывает на голову очереди, q[end] — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается на 1. С такими алгоритмами одна ячейка из n всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов. |
Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке. | Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке. | ||
| Строка 17: | Строка 21: | ||
=== Связный список === | === Связный список === | ||
| − | Второй способ основан на работе с динамической памятью. Очередь представляется в качестве | + | Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов. |
Преимущества данного метода: размер очереди ограничен лишь объёмом памяти. | Преимущества данного метода: размер очереди ограничен лишь объёмом памяти. | ||
| Строка 25: | Строка 29: | ||
=== Реализация на двух стеках === | === Реализация на двух стеках === | ||
Очередь может быть построена из двух [[стек]]ов <code>S1</code> и <code>S2</code> как показано ниже: | Очередь может быть построена из двух [[стек]]ов <code>S1</code> и <code>S2</code> как показано ниже: | ||
| + | |||
| + | [[Файл: queue.png | 400 px]] | ||
'''Процедура''' enqueue(''x''): | '''Процедура''' enqueue(''x''): | ||
| Строка 39: | Строка 45: | ||
'''return''' S2.pop() | '''return''' S2.pop() | ||
| − | + | ||
== Очереди в различных языках программирования == | == Очереди в различных языках программирования == | ||
| − | Практически во всех развитых языках программирования реализованы очереди. В | + | Практически во всех развитых языках программирования реализованы очереди. В CLI для этого предусмотрен класс System.Collections.Queue с методами Enqueue и Dequeue. В STL присутствует класс queue<>, определённый в заголовочном файле queue. В нём используется та же терминология (push и pop), что и в [[стек]]ах. |
== Применение очередей == | == Применение очередей == | ||
Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие. | Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие. | ||
| − | Клавиатурный буфер | + | Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нём и на первый незанятый элемент. |
== См. также == | == См. также == | ||
| − | |||
| − | |||
| − | |||
| − | |||
* [[Стек]] | * [[Стек]] | ||
| − | + | ||
| − | |||
| − | |||
== Ссылки == | == Ссылки == | ||
| + | http://ru.wikipedia.org/wiki/%D0%9E%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C_(%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5) | ||
Версия 21:46, 13 марта 2011
Содержание
Определение
О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента возможно лишь в конец очереди, выборка — только из начала очереди, при этом выбранный элемент из очереди удаляется.
Способы реализации очереди
Существует несколько способов реализации очереди на языках программирования.
Массив
Первый способ представляет очередь в виде массива q и двух целочисленных переменных start и end.
Обычно start указывает на голову очереди, q[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 машинных слов, и двух указателей: на следующий элемент в нём и на первый незанятый элемент.
См. также
