Редактирование: Очередь

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
[[Файл: Fifo_new.png|right|150px]]
+
'''О́чередь''' — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента возможно лишь в конец очереди, выборка — только из начала очереди, при этом выбранный элемент из очереди удаляется.
'''Очередь''' (англ. ''queue'')  {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <tex> \mathtt{push} </tex> и <tex> \mathtt{pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (англ. ''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции:
 
* <tex> \mathtt{empty} </tex> {{---}} проверка очереди на наличие в ней элементов,
 
* <tex> \mathtt {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента,
 
* <tex> \mathtt{pop} </tex> (снятие с очереди) {{---}} операция удаления нового элемента,
 
* <tex> \mathtt{size} </tex> {{---}} операция получения количества элементов в очереди.
 
  
== Реализация циклической очереди на массиве ==
 
Очередь, способную вместить не более <tex>\mathtt{n}</tex> элементов, можно реализовать с помощью массива <tex>\mathtt{elements[0\dots n-1]}</tex>. Она будет обладать следующими полями:
 
* <tex>\mathtt{head}</tex> {{---}} голова очереди,
 
* <tex>\mathtt{tail}</tex> {{---}} хвост очереди.
 
  
=== empty ===
+
== Способы реализации очереди ==
'''boolean''' empty():
 
  '''return''' head == tail
 
  
=== push ===
+
Существует несколько способов реализации очереди на языках программирования.
'''function''' push(x : '''T'''):
 
  '''if''' (size() != n)
 
    elements[tail] = x
 
    tail = (tail + 1) % n
 
  
=== pop ===
+
[[Файл: Fifo.png | 300 px]]
'''T''' pop():
 
  '''if''' (empty())
 
    '''return null'''
 
  x = elements[head]
 
  head = (head + 1) % n
 
  '''return''' x
 
  
=== size ===
+
=== Массив ===
'''int''' size()
 
  '''if''' head > tail
 
    '''return''' n - head + tail
 
  '''else'''
 
    '''return''' tail - head
 
Из-за того что нам не нужно снова выделять память, каждая операция выполняется за <tex>O(1)</tex> времени.
 
  
'''Плюсы:'''
+
Первый способ представляет очередь в виде массива q и двух целочисленных переменных start и end.<br />
* проста в разработке,
 
* по сравнению с реализацией на списке есть незначительная экономия памяти.
 
'''Минусы:'''
 
* количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива),
 
* при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив.
 
  
== Реализация на списке ==
+
Обычно start указывает на голову очереди, q[end] — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается на 1. С такими алгоритмами одна ячейка из n всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов.
Для данной реализации очереди необходимо создать [[Список | список]] <tex>list</tex> и операции работы на созданном списке.
 
  
Реализация очереди на односвязном списке:
+
Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке.
=== List ===
 
* <code>ListItem(data : '''T''', next : '''ListItem''')</code> {{---}} конструктор,
 
* <tex>\mathtt{x.value}</tex> {{---}} поле, в котором хранится значение элемента,
 
* <tex>\mathtt{x.next}</tex> {{---}} указатель на следующий элемент очереди.
 
  
=== push ===
+
Недостатки: максимальное количество элементов в очереди ограничено размером массива. При его переполнении требуется перевыделение памяти и копирование всех элементов в новый массив.  
'''function''' push(x : '''T'''):
 
  element = tail
 
  tail = ListItem(x, NULL)
 
  '''if''' size == 0
 
    head = tail
 
  '''else'''
 
    element.next = tail
 
  size++
 
  
=== pop ===
+
=== Связный список ===
'''T''' pop():
+
Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов.
  size--
 
  element = head
 
  head = head.next
 
  '''return''' element
 
  
=== empty ===
+
Преимущества данного метода: размер очереди ограничен лишь объёмом памяти.
'''boolean''' empty():
 
  '''return''' head == tail
 
[[Файл: Queue.png|right|230px]]
 
  
'''Плюсы:'''
+
Недостатки: сложнее в разработке; требуется больше памяти; при работе с такой очередью память сильнее фрагментируется; работа с очередью несколько медленнее.
* каждая операция выполняется за время <tex>O(1)</tex>.
 
'''Минусы:'''
 
* память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве.
 
  
== Реализация на двух стеках ==
+
=== Реализация на двух стеках ===
Очередь можно реализовать на двух [[Стек|стеках]] <tex>\mathtt{leftStack}</tex> и <tex>\mathtt{rightStack}</tex>. Поступим следующим образом: <tex>\mathtt{leftStack}</tex> будем использовать для операции <tex> \mathtt {push} </tex>, <tex>\mathtt{rightStack}</tex> для операции <tex> \mathtt{pop} </tex>. При этом, если при попытке извлечения элемента из <tex>\mathtt{rightStack}</tex> он оказался пустым, просто перенесем все элементы из <tex>\mathtt{leftStack}</tex> в него (при этом элементы в <tex>\mathtt{rightStack}</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>\mathtt{leftStack}</tex> станет пустым).
+
Очередь может быть построена из двух [[стек]]ов <code>S1</code> и <code>S2</code> как показано ниже:
  
* <tex> \mathtt{pushLeft} </tex> и <tex> \mathtt{pushRight} </tex> {{---}} функции, реализующие операцию <tex> \mathtt{push} </tex> для соответствующего стека,
+
[[Файл: queue.png | 400 px]]
* <tex> \mathtt{popLeft} </tex> и <tex> \mathtt{popRight} </tex> {{---}} аналогично операции <tex> \mathtt {pop} </tex>.
 
  
=== push ===
+
  '''Процедура''' enqueue(''x''):
  '''function''' push(x : '''T'''):
+
    S1.push(''x'')
  pushLeft(x)
+
=== pop ===
+
  '''Процедура''' dequeue():
  '''T''' pop():
+
    '''если''' S2 пуст:
  '''if''' '''not''' rightStack.empty()
+
        '''если''' S1 пуст:
    '''return''' popRight()
+
            сообщить об ошибке: очередь пуста
  '''else'''
+
    '''while''' '''not''' leftStack.empty()
+
        '''пока''' S1 не пуст:
      pushRight(popLeft())
+
            S2.push(S1.pop())
     '''return''' popRight()
+
 +
     '''return''' S2.pop()
  
При выполнении операции <tex> \mathtt{push} </tex> будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию <tex> \mathtt{pop} </tex> из первого стека, третью во второй стек на финальный <tex> \mathtt{pop} </tex>. Тогда для операций <tex> \mathtt{pop} </tex> учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции <tex> \mathtt{push} </tex>.
 
  
Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, а значит, амортизационная стоимость операций <tex>O(1)</tex>.
 
  
'''Плюсы:'''
+
== Очереди в различных языках программирования ==
* эту реализацию несложно модифицировать для получения минимума в текущей очереди за <tex>O(1)</tex>.
+
Практически во всех развитых языках программирования реализованы очереди. В CLI для этого предусмотрен класс System.Collections.Queue с методами Enqueue и Dequeue. В STL присутствует класс queue<>, определённый в заголовочном файле queue. В нём используется та же терминология (push и pop), что и в [[стек]]ах.
'''Минусы:'''
 
* если <tex>\mathtt{leftStack}</tex> не пуст, то операция <tex> \mathtt{pop} </tex> может выполняться <tex>O(n)</tex> времени, в отличие от других реализаций, где <tex> \mathtt{pop} </tex> всегда выполняется за <tex>O(1)</tex>.
 
  
== Реализация на шести стеках ==
+
== Применение очередей ==
 +
Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.
  
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим <tex>O(n)</tex> времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с <tex>O(1)</tex> истинного времени на операцию.
+
Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нём и на первый незанятый элемент.
 
 
Подробное описание в статье [[Персистентная очередь#Реализация очереди на шести стеках|Персистентная очередь]].
 
 
 
=== Отличия от других реализаций ===
 
 
 
'''Плюсы:'''
 
* <tex>O(1)</tex> реального времени на операцию,
 
* возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]].
 
 
 
'''Минусы:'''
 
* дольше в среднем выполняются операции,
 
* больше расход памяти,
 
* большая сложность реализации.
 
  
 
== См. также ==
 
== См. также ==
 
* [[Стек]]
 
* [[Стек]]
* [[Персистентная очередь]]
 
  
== Источники информации ==
 
* [[wikipedia:ru:Очередь_(программирование)|Википедия {{---}} Очередь (программирование)]]
 
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
 
* T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262
 
* [http://hdl.handle.net/1813/6273 ''Hood R., Melville R.'' Real Time Queue Operations in Pure LISP. {{---}} Cornell University, 1980]
 
  
[[Категория: Дискретная математика и алгоритмы]]
+
== Ссылки ==
[[Категория: Амортизационный анализ]]
+
http://ru.wikipedia.org/wiki/Очередь_(программирование)

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: