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

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

Внимание! Вы не авторизовались на сайте. Ваш 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'')  {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <tex> \mathrm {push} </tex> и <tex> \mathrm {pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (''head'') и '''хвост''' (''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове.
* <tex> \mathtt{empty} </tex> {{---}} проверка очереди на наличие в ней элементов,
+
* <tex> \mathrm {empty} </tex> {{---}} проверка очереди на наличие в ней элементов
* <tex> \mathtt {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента,
+
* <tex> \mathrm {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента.
* <tex> \mathtt{pop} </tex> (снятие с очереди) {{---}} операция удаления нового элемента,
+
* <tex> \mathrm {pop} </tex> (снятие с очереди) {{---}} операция удаления нового элемента.
* <tex> \mathtt{size} </tex> {{---}} операция получения количества элементов в очереди.
+
* <tex> \mathrm {size} </tex> {{---}} операция получения количества элементов в очереди
  
 
== Реализация циклической очереди на массиве ==
 
== Реализация циклической очереди на массиве ==
Очередь, способную вместить не более <tex>\mathtt{n}</tex> элементов, можно реализовать с помощью массива <tex>\mathtt{elements[0\dots n-1]}</tex>. Она будет обладать следующими полями:
+
Очередь, способную вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>elements[0..n-1]</tex>. Она будет обладать следующими полями:
* <tex>\mathtt{head}</tex> {{---}} голова очереди,
+
* <tex>head</tex> {{---}} голова очереди
* <tex>\mathtt{tail}</tex> {{---}} хвост очереди.
+
* <tex>tail</tex> {{---}} хвост очереди
  
 
=== empty ===
 
=== empty ===
Строка 17: Строка 17:
  
 
=== push ===
 
=== push ===
  '''function''' push(x : '''T'''):
+
  '''function''' push(x : T):
   '''if''' (size() != n)
+
   elements[tail] = x
    elements[tail] = x
+
  tail = (tail + 1) % n
    tail = (tail + 1) % n
 
  
 
=== pop ===
 
=== pop ===
 
  '''T''' pop():
 
  '''T''' pop():
   '''if''' (empty())
+
   '''if''' '''not''' empty()
    '''return null'''
+
    x = elements[head]
  x = elements[head]
+
    head = (head + 1) % n
  head = (head + 1) % n
+
    '''return''' x
  '''return''' x
 
  
 
=== size ===
 
=== size ===
  '''int''' size()
+
  '''int''' size(s : stack<T>)
 
   '''if''' head > tail
 
   '''if''' head > tail
 
     '''return''' n - head + tail
 
     '''return''' n - head + tail
 
   '''else'''
 
   '''else'''
 
     '''return''' tail - head
 
     '''return''' tail - head
Из-за того что нам не нужно снова выделять память, каждая операция выполняется за <tex>O(1)</tex> времени.
+
Из-за того что нам не нужно перевыделять память, каждая операция выполняется за <tex>O(1)</tex> времени.
  
 
'''Плюсы:'''
 
'''Плюсы:'''
* проста в разработке,
+
* прост в разработке
* по сравнению с реализацией на списке есть незначительная экономия памяти.
+
* по сравнению с реализацией на списке есть незначительная экономия памяти
 
'''Минусы:'''
 
'''Минусы:'''
* количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива),
+
* количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива)
* при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив.
+
* при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив
  
 
== Реализация на списке ==
 
== Реализация на списке ==
Строка 50: Строка 48:
 
Реализация очереди на односвязном списке:
 
Реализация очереди на односвязном списке:
 
=== List ===
 
=== List ===
* <code>ListItem(data : '''T''', next : '''ListItem''')</code> {{---}} конструктор,
+
* <code>list(T data, list next)</code> {{---}} конструктор
* <tex>\mathtt{x.value}</tex> {{---}} поле, в котором хранится значение элемента,
+
* <tex>x.value</tex> {{---}} поле, в котором хранится значение элемента
* <tex>\mathtt{x.next}</tex> {{---}} указатель на следующий элемент очереди.
+
* <tex>x.next</tex> {{---}} указатель на следующий элемент очереди
  
 
=== push ===
 
=== push ===
  '''function''' push(x : '''T'''):
+
  '''function''' push(x : T):
 
   element = tail
 
   element = tail
   tail = ListItem(x, NULL)
+
   tail = list(x, NULL)
 
   '''if''' size == 0
 
   '''if''' size == 0
 
     head = tail
 
     head = tail
 
   '''else'''  
 
   '''else'''  
 
     element.next = tail
 
     element.next = tail
  size++
 
  
 
=== pop ===
 
=== pop ===
  '''T''' pop():  
+
  '''T''' pop():
   size--
+
   '''if''' empty()
 +
    '''return'''
 
   element = head
 
   element = head
 
   head = head.next
 
   head = head.next
Строка 75: Строка 73:
 
   '''return''' head == tail
 
   '''return''' head == tail
 
[[Файл: 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> \mathrm {push} </tex>, другой для операции <tex> \mathrm {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> \mathrm {pushLeft} </tex> и <tex> \mathrm {pushRight} </tex> {{---}} функции, реализующие операцию <tex> \mathrm {push} </tex> для соответствующего стека;
* <tex> \mathtt{popLeft} </tex> и <tex> \mathtt{popRight} </tex> {{---}} аналогично операции <tex> \mathtt {pop} </tex>.
+
* <tex> \mathrm {popLeft} </tex> и <tex> \mathrm {popRight} </tex> {{---}} аналогично операции <tex> \mathrm {pop} </tex>.
  
 
=== push ===
 
=== push ===
  '''function''' push(x : '''T'''):
+
  '''function''' push(x : T):
 
   pushLeft(x)
 
   pushLeft(x)
 
=== pop ===
 
=== pop ===
 
  '''T''' pop():
 
  '''T''' pop():
   '''if''' '''not''' rightStack.empty()
+
   '''if''' '''not''' rigthStack.empty()
 
     '''return''' popRight()  
 
     '''return''' popRight()  
 
   '''else'''
 
   '''else'''
Строка 99: Строка 96:
 
     '''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> \mathrm {push} </tex> будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию <tex> \mathrm {pop} </tex> из первого стека, третью во второй стек на финальный <tex> \mathrm {pop} </tex>. Тогда для операций <tex> \mathrm {pop} </tex> учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции <tex> \mathrm {push} </tex>.
  
 
Таким образом, для каждой операции требуется <tex>O(1)</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> \mathrm {pop} </tex> может выполняться <tex>O(n)</tex> времени, в отличии от других реализаций, где <tex> \mathrm {pop} </tex> всегда выполняется за <tex>O(1)</tex>
  
 
== Реализация на шести стеках ==
 
== Реализация на шести стеках ==
Строка 116: Строка 113:
 
=== Отличия от других реализаций ===
 
=== Отличия от других реализаций ===
  
'''Плюсы:'''
+
'''Плюсы''':
* <tex>O(1)</tex> реального времени на операцию,
+
* <tex>O(1)</tex> реального времени на операцию.
* возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]].  
+
* Возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]].  
  
'''Минусы:'''
+
'''Минусы''':
* дольше в среднем выполняются операции,
+
* Дольше в среднем выполняются операции.
* больше расход памяти,
+
* Больше расход памяти.
* большая сложность реализации.
+
* Большая сложность реализации.
  
 
== См. также ==
 
== См. также ==
Строка 129: Строка 126:
 
* [[Персистентная очередь]]
 
* [[Персистентная очередь]]
  
== Источники информации ==
+
== Ссылки ==
 
* [[wikipedia:ru:Очередь_(программирование)|Википедия {{---}} Очередь (программирование)]]
 
* [[wikipedia:ru:Очередь_(программирование)|Википедия {{---}} Очередь (программирование)]]
 
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
 
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262

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

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

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

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