Очередь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
'''О́чередь''' — [[структура данных]] с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
+
== Определение ==
 +
'''О́чередь''' — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента возможно лишь в конец очереди, выборка — только из начала очереди, при этом выбранный элемент из очереди удаляется.
 +
 
  
 
== Способы реализации очереди ==
 
== Способы реализации очереди ==
  
 
Существует несколько способов реализации очереди на языках программирования.
 
Существует несколько способов реализации очереди на языках программирования.
 +
 +
[[Файл: Fifo.png | 300 px]]
  
 
=== Массив ===
 
=== Массив ===
  
Первый способ представляет очередь в виде [[массив]]а и двух целочисленных [[переменная|переменных]] start и end.<br />
+
Первый способ представляет очередь в виде массива q и двух целочисленных переменных start и end.<br />
[[Файл:Queue1.gif]]<br />
+
 
Обычно <code>start</code> указывает на голову очереди, <code>end</code> — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в <code>q[end]</code> записывается новый элемент очереди, а <code>end</code> уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента <code>q[start]</code> из очереди переменная <code>start</code> уменьшается на 1. С такими алгоритмами одна ячейка из <code>n</code> всегда будет незанятой (так как очередь с <code>n</code> элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов.
+
Обычно 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()
  
Такой способ реализации наиболее удобен в качестве основы для построения [[Персистентная структура данных|персистентной]] очереди.
+
 
  
 
== Очереди в различных языках программирования ==
 
== Очереди в различных языках программирования ==
Практически во всех развитых языках программирования реализованы очереди. В [[Common Language Infrastructure|CLI]] для этого предусмотрен класс System.Collections.Queue с методами Enqueue и Dequeue. В [[Стандартная библиотека шаблонов|STL]] также присутствует класс queue<>, определённый в заголовочном файле queue. В нём используется та же терминология (push и pop), что и в [[стек]]ах.
+
Практически во всех развитых языках программирования реализованы очереди. В CLI для этого предусмотрен класс System.Collections.Queue с методами Enqueue и Dequeue. В STL присутствует класс queue<>, определённый в заголовочном файле queue. В нём используется та же терминология (push и pop), что и в [[стек]]ах.
  
 
== Применение очередей ==
 
== Применение очередей ==
 
Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.
 
Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.
  
Клавиатурный буфер [[BIOS]]<!-- Вариант аббревиатуры "ВСУВВ" вообще нигде не встречается на Википедии --> организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нём и на первый незанятый элемент.
+
Клавиатурный буфер 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). Добавление элемента возможно лишь в конец очереди, выборка — только из начала очереди, при этом выбранный элемент из очереди удаляется.


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

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

Fifo.png

Массив

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

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

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

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

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

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

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

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

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

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

Queue.png

Процедура 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/%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)