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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация на шести стеках: правки)
м (rollbackEdits.php mass rollback)
 
(не показано 100 промежуточных версий 9 участников)
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
 
[[Файл: Fifo_new.png|right|150px]]
 
[[Файл: Fifo_new.png|right|150px]]
'''Очередь''' (''Queue'')  — это структура данных, добавление и удаление элементов в которой происходит путём операций ''Push'' и ''Pop'' соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (''first-in, first-out FIFO''). У очереди имеется '''голова''' (''head'') и '''хвост''' (''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове.
+
'''Очередь''' (англ. ''queue'')  {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <tex> \mathtt{push} </tex> и <tex> \mathtt{pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (англ. ''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции:
*<tex>push</tex> (запись в очередь) - операция вставки нового элемента.
+
* <tex> \mathtt{empty} </tex> {{---}} проверка очереди на наличие в ней элементов,
*<tex>pop</tex> (снятие с очереди) - операция удаления нового элемента.
+
* <tex> \mathtt {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента,
*<tex>empty</tex> - проверка очереди на наличие в ней элементов
+
* <tex> \mathtt{pop} </tex> (снятие с очереди) {{---}} операция удаления нового элемента,
 +
* <tex> \mathtt{size} </tex> {{---}} операция получения количества элементов в очереди.
  
== Реализация на массиве ==
+
== Реализация циклической очереди на массиве ==
Очередь, способную вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>elements[1..n]</tex>. Она будет обладать следующими полями:
+
Очередь, способную вместить не более <tex>\mathtt{n}</tex> элементов, можно реализовать с помощью массива <tex>\mathtt{elements[0\dots n-1]}</tex>. Она будет обладать следующими полями:
* <tex>head</tex> (голова очереди)
+
* <tex>\mathtt{head}</tex> {{---}} голова очереди,
* <tex>tail</tex> (хвост очереди)
+
* <tex>\mathtt{tail}</tex> {{---}} хвост очереди.
* <tex>size</tex> (размер очереди)
+
 
 +
=== empty ===
 +
'''boolean''' empty():
 +
  '''return''' head == tail
  
 
=== push ===
 
=== push ===
  push(x)
+
  '''function''' push(x : '''T'''):
    elements[tail] = x
+
  '''if''' (size() != n)
    tail = (tail + 1) % elements.length
+
    elements[tail] = x
    size++
+
    tail = (tail + 1) % n
 +
 
 
=== pop ===
 
=== pop ===
  pop()
+
  '''T''' pop():
    if !empty()
+
  '''if''' (empty())
      x = elements[head]
+
    '''return null'''
      head = (head + 1) % elements.length
+
  x = elements[head]
      size--
+
  head = (head + 1) % n
      return x
+
  '''return''' x
=== empty ===
+
 
  empty()
+
=== size ===
    return size == 0
+
  '''int''' size()
Из-за того что нам не нужно перевыделять память, каждая операция выполняется за <tex>O(1)</tex> времени.
+
  '''if''' head > tail
 +
    '''return''' n - head + tail
 +
  '''else'''
 +
    '''return''' tail - head
 +
Из-за того что нам не нужно снова выделять память, каждая операция выполняется за <tex>O(1)</tex> времени.
  
 
'''Плюсы:'''
 
'''Плюсы:'''
:- прост в разработке
+
* проста в разработке,
:- по сравнению с реализацией на списке, есть незначительная экономия памяти
+
* по сравнению с реализацией на списке есть незначительная экономия памяти.
 
'''Минусы:'''
 
'''Минусы:'''
:- количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива)
+
* количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива),
:- при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив
+
* при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив.
  
 
== Реализация на списке ==
 
== Реализация на списке ==
Для данной реализации очереди необходимо создать список (<tex>list</tex>) и операции работы на созданном списке.
+
Для данной реализации очереди необходимо создать [[Список | список]] <tex>list</tex> и операции работы на созданном списке.
  
 
Реализация очереди на односвязном списке:
 
Реализация очереди на односвязном списке:
=== list ===
+
=== List ===
* <tex>x.value</tex> - поле, в котором хранится значение элемента
+
* <code>ListItem(data : '''T''', next : '''ListItem''')</code> {{---}} конструктор,
* <tex>x.next</tex> - указатель на следующий элемент очереди
+
* <tex>\mathtt{x.value}</tex> {{---}} поле, в котором хранится значение элемента,
 +
* <tex>\mathtt{x.next}</tex> {{---}} указатель на следующий элемент очереди.
  
 
=== push ===
 
=== push ===
  push(x)
+
  '''function''' push(x : '''T'''):
    element = tail
+
  element = tail
    tail = new list(x, NULL)
+
  tail = ListItem(x, NULL)
    if size == 0
+
  '''if''' size == 0
      head = tail
+
    head = tail
    else  
+
  '''else'''
      element.next = tail
+
    element.next = tail
    size++
+
  size++
  
 
=== pop ===
 
=== pop ===
  pop()
+
  '''T''' pop():
    if empty()
+
  size--
      return
+
  element = head
    element = head
+
  head = head.next
    head = head.next
+
  '''return''' element
    size--
 
    return element
 
  
 
=== empty ===
 
=== empty ===
  empty()
+
  '''boolean''' empty():
    return size == 0
+
  '''return''' head == tail
 
[[Файл: Queue.png|right|230px]]
 
[[Файл: Queue.png|right|230px]]
Каждая операция выполняется за время <tex>O(1)</tex>.
 
  
 +
'''Плюсы:'''
 +
* каждая операция выполняется за время <tex>O(1)</tex>.
 
'''Минусы:'''
 
'''Минусы:'''
* Память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве
+
* память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве.
  
 
== Реализация на двух стеках ==
 
== Реализация на двух стеках ==
Очередь можно реализовать на двух [[Стек|стеках]] <tex>leftStack</tex> и <tex>rightStack</tex>. Один из стеков <tex>(leftStack)</tex> будем использовать для операции <tex>push</tex>, другой для операции <tex>pop</tex>. При этом, если при попытке извлечения элемента из <tex>rightStack</tex> он оказался пустым, просто перенесем все элементы из <tex>leftStack</tex> в него (при этом элементы в <tex>rightStack</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>leftStack</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> станет пустым).
  
* <tex>pushLeft</tex> и <tex>pushRight</tex> - функции, реализующие операцию <tex>push</tex> для соответствующего стека;
+
* <tex> \mathtt{pushLeft} </tex> и <tex> \mathtt{pushRight} </tex> {{---}} функции, реализующие операцию <tex> \mathtt{push} </tex> для соответствующего стека,
* <tex>popLeft</tex> и <tex>popRight</tex> - аналогично операции <tex>pop</tex>.
+
* <tex> \mathtt{popLeft} </tex> и <tex> \mathtt{popRight} </tex> {{---}} аналогично операции <tex> \mathtt {pop} </tex>.
  
 
=== push ===
 
=== push ===
  push(x)
+
  '''function''' push(x : '''T'''):
    pushLeft(x)
+
  pushLeft(x)
 
=== pop ===
 
=== pop ===
  if !rigthStack.empty()
+
  '''T''' pop():
    return popRight()
+
  '''if''' '''not''' rightStack.empty()
+
    '''return''' popRight()  
else
+
  '''else'''
    while !leftStack.empty()
+
    '''while''' '''not''' leftStack.empty()
 
       pushRight(popLeft())
 
       pushRight(popLeft())
    return popRight()
+
    '''return''' popRight()
  
При выполнении операции <tex>push</tex> будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию <tex>pop</tex> из первого стека, третью во второй стек на финальный <tex>pop</tex>. Тогда для операций <tex>pop</tex> учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции <tex>push</tex>.
+
При выполнении операции <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> монет, а значит, амортизационная стоимость операций <tex>O(1)</tex>.
  
 +
'''Плюсы:'''
 +
* эту реализацию несложно модифицировать для получения минимума в текущей очереди за <tex>O(1)</tex>.
 
'''Минусы:'''
 
'''Минусы:'''
* Если <tex>leftStack</tex> не пуст, то операция <tex>pop</tex> может выполняться <tex>O(n)</tex> времени, в отличии от других реализаций, где <tex>pop</tex> всегда выполняется за <tex>O(1)</tex>
+
* если <tex>\mathtt{leftStack}</tex> не пуст, то операция <tex> \mathtt{pop} </tex> может выполняться <tex>O(n)</tex> времени, в отличие от других реализаций, где <tex> \mathtt{pop} </tex> всегда выполняется за <tex>O(1)</tex>.
  
 
== Реализация на шести стеках ==
 
== Реализация на шести стеках ==
 +
 
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим <tex>O(n)</tex> времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с <tex>O(1)</tex> истинного времени на операцию.
 
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим <tex>O(n)</tex> времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с <tex>O(1)</tex> истинного времени на операцию.
  
Сначала будем действовать аналогично случаю с двумя стеками. Пусть у нас есть стек <tex>L</tex> для операций <tex>push</tex> и стек <tex>R</tex> для операций <tex>pop</tex>. К моменту опустошения стека <tex>R</tex> нам нужно успеть получить стек <tex>R'</tex>, содержащий текущие элементы стека <tex>L</tex> в правильном для извлечения порядке. Перекопирование начнется, когда появится опасность того, что мы не сможем за оставшиеся <tex>R.size</tex> операций <tex>pop</tex> со стеком <tex>R</tex> перекопировать стек <tex>L</tex> в новый стек <tex>R'</tex>. Очевидно, это ситуация <tex>L.size>R.size</tex>, пусть такое состояние отражает специальная переменная логического типа <tex>recopy</tex>.
+
Подробное описание в статье [[Персистентная очередь#Реализация очереди на шести стеках|Персистентная очередь]].
  
Понятно, что во время перекопирования могут поступить операции <tex>push</tex>, а стек <tex>L</tex> в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек <tex>L'</tex>, в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями <tex>L,L'</tex> и <tex>R,R'</tex>, и вроде бы все станет хорошо.
+
=== Отличия от других реализаций ===
  
Однако, если реализовать этот алгоритм, мы получим неприятную вещь: старый стек <tex>R</tex> может и не опустошиться за это время, то есть мы получили два стека с выходными данными, а значит возможен случай (например, когда все поступающие операции <tex>push</tex>), когда при следующем перекопировании у нас не будет свободного стека для копировании туда элементов <tex>L</tex>. Для преодоления этой проблемы мы принудительно будем извлекать все элементы из стека <tex>R</tex> во вспомогательный стек <tex>T</tex>, затем копировать элементы из стека <tex>L</tex> в <tex>R</tex>, а затем обратно копировать элементы из стека <tex>T</tex> в <tex>R</tex>. Легко показать, что приведенный алгоритм как раз получает на выходе в <tex>R</tex> все элементы стеков <tex>L,R</tex> в правильном порядке.
+
'''Плюсы:'''
 +
* <tex>O(1)</tex> реального времени на операцию,
 +
* возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]].  
  
Но этого еще недостаточно. Если мы принудительно извлекаем элементы из стека <tex>R</tex>, появляются следующие проблемы:
+
'''Минусы:'''
# Что вернуть при операции <tex>pop</tex>? Для этого заведем себе стек <tex>Rc</tex> {{---}} копию стека <tex>R</tex>.
+
* дольше в среднем выполняются операции,
# Как поддерживать корректность такой копии? Поскольку этот стек нужен только для перекопирования, а во время него он занят, нужна запасная копия <tex>Rc'</tex>, в которую мы будем копировать все те же элементы, которые мы копируем в <tex>R</tex>, а по окончании перекопирования поменяем ролями стеки <tex>Rc,Rc'</tex>, как мы делали со стеками <tex>L, L'</tex>.
+
* больше расход памяти,
№ Как учесть, что во время перекопирования часть элементов была извлечена из <tex>Rc</tex>? Для этого заведем специальную переменную <tex>toCopy</tex>, которая показывает, сколько корректных элементов находится в стеке <tex>T</tex> и уменьшается при каждом извлечении из <tex>T</tex> или операции <tex>pop</tex>. К счастью, все некорректные элементы будут нарастать с дна стека, так что мы никогда не извлечем некорректный элемент, если <tex>toCopy>0</tex>.
+
* большая сложность реализации.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Если мы использовали стек <tex>L</tex> для операций <tex>push</tex> и стек <tex>R</tex> для операций <tex>pop</tex>, то для перекопирования мы должны заменить текущий стек <tex>R</tex> на новый стек <tex>R'</tex>, который содержит сначала все элементы <tex>L</tex> в обратном порядке, а затем все элементы <tex>R</tex> в прямом порядке. Этого можно добиться, если сначала извлечь все элементы <tex>R</tex> во вспомогательный стек <tex>T</tex>, затем извлечь все элементы <tex>L</tex> в стек <tex>R</tex>, а затем обратно извлечь весь стек <tex>T</tex> в <tex>R</tex>. Поскольку мы выполняем эти действия не сразу, а во время выполнения обычных операций с очередью, нам нужно уметь обрабатывать операции <tex>push</tex>, для этого будем класть поступающие элементы во вспомогательный стек <tex>L'</tex>, а для операций <tex>pop</tex> будем использовать не стек <tex>R</tex>, который во время перекопирования потерял свою структуру, а его копию <tex>Rc</tex>, остающуюся неизменной во время перекопирования. Чтобы сохранить информацию о том, сколько элементов мы уже извлекли из <tex>Rc</tex>, будем использовать счетчик <tex>toCopy</tex>, который показывает, сколько элементов из скопированных в <tex>T</tex> из <tex>R</tex> действительно находятся в очереди, оставшиеся элементы нужно извлечь без копирования.
 
 
 
Для такой реализации будем использовать стеки <tex>L_1, L_2, R, Rc_1, Rc_2, T</tex>, причем стеки <tex>L_1, L_2</tex> используются для операций <tex>push</tex>, стек <tex>R</tex> используется для операций <tex>pop</tex>, стеки <tex>Rc_1, Rc_2</tex> используются в качестве копий стека <tex>R</tex> для операций <tex>pop</tex> при перекопировании, стек <tex>T</tex> используется как временное хранилище элементов <tex>R</tex>.
 
 
 
В каждый момент времени в очереди зафиксировано, какой <tex>L</tex> из стеков <tex>L_1</tex> и <tex>L_2</tex> используется для помещения туда элементов, пришедших с операцией <tex>push</tex>, а также какой <tex>Rc</tex> из стеков <tex>Rc_1</tex> и <tex>Rc_2</tex> является в данный момент точной копией стека <tex>R</tex>.
 
 
 
Также очередь будет запоминать, находится ли она сейчас в режиме перекопирования (''recopy mode''), в который переходит из обычного режима, когда после очередной операции в стеке <tex>L</tex> становится больше элементов, чем в стеке <tex>R</tex>. При активации инициализируется счетчик <tex>toCopy</tex>, показывающий, сколько находится неизвлеченных элементов в стеке <tex>Rc</tex>.
 
 
 
Обрабатываем поступающие дальше операции следующим образом: <tex>push</tex> кладет элемент в парный нашему стеку <tex>L</tex> стек <tex>L'</tex>, а <tex>pop</tex> извлекает элемент только из <tex>Rc</tex>, при этом уменьшая счетчик <tex>toCopy</tex>. <tex>empty</tex> в этом режиме всегда возвращает <tex>false</tex>, так как при перекопировании <tex>n+1>0</tex> элементов из <tex>L</tex> всегда остаются в очереди, так как извлечение происходит только из <tex>Rc</tex>.
 
 
 
Пусть в этот момент в стеке <tex>R</tex>, а значит, и в стеке <tex>Rc</tex> находились <tex>n</tex> элементов, тогда в стеке <tex>L</tex> их <tex>n+1</tex>. Заметим, что мы можем корректно обработать все операции <tex>push</tex> и первые <tex>n</tex> операций <tex>pop</tex>, то есть у нас есть на перекопирование не меньше <tex>n+1</tex> операции вместе с активирующей.
 
 
 
Корректной ситуация станет, когда в стеках <tex>R</tex> и парном стеке <tex>Rc'</tex> окажутся все находящиеся на момент активации в очереди и не извлеченные после активации элементы, причем в порядке, правильном для извлечения.
 
 
 
Чтобы получить корректную ситуацию и перейти в обычный режим, нужно:
 
# Извлечь весь стек <tex>R</tex> в стек <tex>T</tex>, <tex>n</tex> действий.
 
# Извлечь весь стек <tex>L</tex> в стеки <tex>R, Rc'</tex>, <tex>n+1</tex> действие.
 
# Извлечь <tex>toCopy</tex> элементов <tex>T</tex> в стеки <tex>R, Rc'</tex>, а оставшиеся выкинуть, <tex>n</tex> действий.
 
# Назначить <tex>Rc'</tex> текущей копией стека <tex>R</tex>, а <tex>L'</tex> {{---}} текущим стеком для операций <tex>push</tex>, <tex>2</tex> действия.
 
 
 
Таким образом, получили <tex>3 \cdot n + 3</tex> действий на <tex>n + 1</tex> операций с очередью, то есть выполняя 3 дополнительных действия во время операции мы успеем перекопировать все элементы вовремя. Тогда очередь действительно будет выполнять каждое действие за <tex>O(1)</tex> реального времени.
 
 
 
Теперь рассмотрим, какие изменения произошли за время перекопирования. Пусть среди <tex>n</tex> следующих за активацией операций у нас <tex>x</tex> операций <tex>pop</tex> и <tex>n-x</tex> операций <tex>push</tex>. Тогда в стеке <tex>R</tex> оказалось <tex>2 \cdot n + 1 - x</tex> элементов, а в новом стеке <tex>L</tex> оказалось <tex>n - x</tex> элементов. Тогда в стеке <tex>R</tex> на <tex>n+1</tex> больше элементов, чем в стеке <tex>L</tex>, а это значит, что до следующего режима перекопирования <tex>n + 2</tex> операции, и за это время мы успеем очистить старый стек <tex>Rc</tex>, в котором находится максимум <tex>n</tex> ненужных элементов, просто удаляя при каждой операции в обычном режиме один элемент из <tex>Rc</tex>, если он непуст.
 
 
 
Заметим, что вышеприведенный алгоритм гарантирует нам, что в обычном режиме в стеке <tex>L</tex> находится не больше элементов, чем в <tex>R</tex>, так что проверка на пустоту очереди при обычном режиме сводится к проверке на пустоту стека <tex>R</tex>.
 
 
 
Пусть наша очередь <tex>Q</tex> имеет стеки <tex>L1, L2, R, Rc1, Rc2, T</tex>, а также переменные <tex>recopy</tex> и <tex>toCopy</tex>, тогда следующий псевдокод выполняет требуемые операции.
 
=== empty ===
 
<code>
 
empty()
 
    return !recopy and R.size == 0
 
</code>
 
=== push ===
 
<code>
 
push(x)
 
    if !recopy
 
      L1.push(x)
 
      checkRecopy()
 
    else
 
      L2.push(x)
 
      checkNormal()
 
</code>
 
=== pop ===
 
<code>
 
pop()
 
    if !recopy
 
      tmp = R.pop()
 
      Rc1.pop()
 
      checkRecopy()
 
      return tmp
 
    else
 
      tmp = Rc1.pop()
 
      toCopy = toCopy - 1
 
      checkNormal()
 
      return tmp
 
</code>
 
=== checkRecopy ===
 
<code>
 
checkRecopy()
 
    if Rc2.size > 0
 
      Rc2.pop()
 
    recopy = L1.size > R.size
 
    if recopy
 
      toCopy = Rc1.size
 
      additionalOperations()
 
</code>
 
=== checkNormal ===
 
<code>
 
checkNormal()
 
    additionalOperations()
 
    // Если мы не все перекопировали, то у нас не пуст стек T
 
    recopy = T.size != 0
 
</code>
 
=== additionalOperations ===
 
<code>
 
additionalOperations()
 
    // Нам достаточно 3 операций на вызов
 
    toDo = 3
 
    // Пытаемся перекопировать R в T
 
    while toDo > 0 and R.size > 0
 
      T.push(R.pop())
 
      toDo = toDo - 1
 
    // Пытаемся перекопировать L1 в R и Rc2
 
    while toDo > 0 and L1.size > 0
 
      x = L1.pop()
 
      R.push(x)
 
      Rc2.push(x)
 
      toDo = toDo - 1
 
    // Пытаемся перекопировать T в R и Rc2 с учетом toCopy
 
    while toDo > 0 and T.size > 0
 
      x = T.pop()
 
      if toCopy > 0
 
          R.push(x)
 
          Rc2.push(x)
 
          toCopy = toCopy - 1
 
      toDo = toDo - 1
 
    // Если все скопировано, то меняем роли L1, L2 и Rc1, Rc2
 
    if T.size = 0
 
      swap(L1, L2)
 
      swap(Rc1, Rc2)
 
</code>
 
 
 
'''Плюсы''':
 
* <tex>O(1)</tex> реального времени на операцию.
 
* Возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]].
 
 
 
'''Минусы''':
 
* Больше константа на операции.
 
* Больше расход памяти.
 
* Больше сложность реализации.
 
  
 
== См. также ==
 
== См. также ==
 
* [[Стек]]
 
* [[Стек]]
 +
* [[Персистентная очередь]]
  
== Ссылки ==
+
== Источники информации ==
* [http://ru.wikipedia.org/wiki/Очередь_(программирование) Википедия - Очередь (программирование)]
+
* [[wikipedia:ru:Очередь_(программирование)|Википедия {{---}} Очередь (программирование)]]
 
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
 
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
 
* T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262
 
* T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262

Текущая версия на 19:21, 4 сентября 2022

Определение

Fifo new.png

Очередь (англ. queue)  — это структура данных, добавление и удаление элементов в которой происходит путём операций [math] \mathtt{push} [/math] и [math] \mathtt{pop} [/math] соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. first-in, first-out — FIFO). У очереди имеется голова (англ. head) и хвост (англ. tail). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции:

  • [math] \mathtt{empty} [/math] — проверка очереди на наличие в ней элементов,
  • [math] \mathtt {push} [/math] (запись в очередь) — операция вставки нового элемента,
  • [math] \mathtt{pop} [/math] (снятие с очереди) — операция удаления нового элемента,
  • [math] \mathtt{size} [/math] — операция получения количества элементов в очереди.

Реализация циклической очереди на массиве

Очередь, способную вместить не более [math]\mathtt{n}[/math] элементов, можно реализовать с помощью массива [math]\mathtt{elements[0\dots n-1]}[/math]. Она будет обладать следующими полями:

  • [math]\mathtt{head}[/math] — голова очереди,
  • [math]\mathtt{tail}[/math] — хвост очереди.

empty

boolean empty():
  return head == tail

push

function push(x : T):
  if (size() != n)
    elements[tail] = x
    tail = (tail + 1) % n

pop

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

Из-за того что нам не нужно снова выделять память, каждая операция выполняется за [math]O(1)[/math] времени.

Плюсы:

  • проста в разработке,
  • по сравнению с реализацией на списке есть незначительная экономия памяти.

Минусы:

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

Реализация на списке

Для данной реализации очереди необходимо создать список [math]list[/math] и операции работы на созданном списке.

Реализация очереди на односвязном списке:

List

  • ListItem(data : T, next : ListItem) — конструктор,
  • [math]\mathtt{x.value}[/math] — поле, в котором хранится значение элемента,
  • [math]\mathtt{x.next}[/math] — указатель на следующий элемент очереди.

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

Плюсы:

  • каждая операция выполняется за время [math]O(1)[/math].

Минусы:

  • память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве.

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

Очередь можно реализовать на двух стеках [math]\mathtt{leftStack}[/math] и [math]\mathtt{rightStack}[/math]. Поступим следующим образом: [math]\mathtt{leftStack}[/math] будем использовать для операции [math] \mathtt {push} [/math], [math]\mathtt{rightStack}[/math] для операции [math] \mathtt{pop} [/math]. При этом, если при попытке извлечения элемента из [math]\mathtt{rightStack}[/math] он оказался пустым, просто перенесем все элементы из [math]\mathtt{leftStack}[/math] в него (при этом элементы в [math]\mathtt{rightStack}[/math] получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а [math]\mathtt{leftStack}[/math] станет пустым).

  • [math] \mathtt{pushLeft} [/math] и [math] \mathtt{pushRight} [/math] — функции, реализующие операцию [math] \mathtt{push} [/math] для соответствующего стека,
  • [math] \mathtt{popLeft} [/math] и [math] \mathtt{popRight} [/math] — аналогично операции [math] \mathtt {pop} [/math].

push

function push(x : T):
  pushLeft(x)

pop

T pop():
  if not rightStack.empty()
    return popRight() 
  else
    while not leftStack.empty()
      pushRight(popLeft())
    return popRight()

При выполнении операции [math] \mathtt{push} [/math] будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию [math] \mathtt{pop} [/math] из первого стека, третью во второй стек на финальный [math] \mathtt{pop} [/math]. Тогда для операций [math] \mathtt{pop} [/math] учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции [math] \mathtt{push} [/math].

Таким образом, для каждой операции требуется [math]O(1)[/math] монет, а значит, амортизационная стоимость операций [math]O(1)[/math].

Плюсы:

  • эту реализацию несложно модифицировать для получения минимума в текущей очереди за [math]O(1)[/math].

Минусы:

  • если [math]\mathtt{leftStack}[/math] не пуст, то операция [math] \mathtt{pop} [/math] может выполняться [math]O(n)[/math] времени, в отличие от других реализаций, где [math] \mathtt{pop} [/math] всегда выполняется за [math]O(1)[/math].

Реализация на шести стеках

Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим [math]O(n)[/math] времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с [math]O(1)[/math] истинного времени на операцию.

Подробное описание в статье Персистентная очередь.

Отличия от других реализаций

Плюсы:

Минусы:

  • дольше в среднем выполняются операции,
  • больше расход памяти,
  • большая сложность реализации.

См. также

Источники информации