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

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

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

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

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

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

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

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