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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
 
[[Файл: Fifo_new.png|right|150px]]
 
[[Файл: Fifo_new.png|right|150px]]
'''Очередь''' (англ. ''queue'')  {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <tex> \mathrm {push} </tex> и <tex> \mathrm {pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (англ''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове.
+
'''Очередь''' (англ. ''queue'')  {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <tex> \mathtt{push} </tex> и <tex> \mathtt{pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (англ''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове.
* <tex> \mathrm {empty} </tex> {{---}} проверка очереди на наличие в ней элементов
+
* <tex> \mathtt{empty} </tex> {{---}} проверка очереди на наличие в ней элементов
* <tex> \mathrm {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента.
+
* <tex> \mathtt {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента.
* <tex> \mathrm {pop} </tex> (снятие с очереди) {{---}} операция удаления нового элемента.
+
* <tex> \mathtt{pop} </tex> (снятие с очереди) {{---}} операция удаления нового элемента.
* <tex> \mathrm {size} </tex> {{---}} операция получения количества элементов в очереди
+
* <tex> \mathtt{size} </tex> {{---}} операция получения количества элементов в очереди
  
 
== Реализация циклической очереди на массиве ==
 
== Реализация циклической очереди на массиве ==
Очередь, способную вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>\mathrm{elements[0\dots n-1]}</tex>. Она будет обладать следующими полями:
+
Очередь, способную вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>\mathtt{elements[0\dots n-1]}</tex>. Она будет обладать следующими полями:
* <tex>\mathrm{head}</tex> {{---}} голова очереди
+
* <tex>\mathtt{head}</tex> {{---}} голова очереди
* <tex>\mathrm{tail}</tex> {{---}} хвост очереди
+
* <tex>\mathtt{tail}</tex> {{---}} хвост очереди
  
 
=== empty ===
 
=== empty ===
Строка 48: Строка 48:
 
=== List ===
 
=== List ===
 
* <code>ListItem(data : '''T''', next : '''ListItem''')</code> {{---}} конструктор
 
* <code>ListItem(data : '''T''', next : '''ListItem''')</code> {{---}} конструктор
* <tex>\mathrm{x.value}</tex> {{---}} поле, в котором хранится значение элемента
+
* <tex>\mathtt{x.value}</tex> {{---}} поле, в котором хранится значение элемента
* <tex>\mathrm{x.next}</tex> {{---}} указатель на следующий элемент очереди
+
* <tex>\mathtt{x.next}</tex> {{---}} указатель на следующий элемент очереди
  
 
=== push ===
 
=== push ===
Строка 79: Строка 79:
  
 
== Реализация на двух стеках ==
 
== Реализация на двух стеках ==
Очередь можно реализовать на двух [[Стек|стеках]] <tex>\mathrm{leftStack}</tex> и <tex>\mathrm{rightStack}</tex>.<tex>\mathrm{leftStack}</tex> будем использовать для операции <tex> \mathrm {push} </tex>, <tex>\mathrm{rightStack}</tex> для операции <tex> \mathrm {pop} </tex>. При этом, если при попытке извлечения элемента из <tex>\mathrm{rightStack}</tex> он оказался пустым, просто перенесем все элементы из <tex>\mathrm{leftStack}</tex> в него (при этом элементы в <tex>rightStack</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>\mathrm{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>rightStack</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>\mathtt{leftStack}</tex> станет пустым).
  
* <tex> \mathrm {pushLeft} </tex> и <tex> \mathrm {pushRight} </tex> {{---}} функции, реализующие операцию <tex> \mathrm {push} </tex> для соответствующего стека;  
+
* <tex> \mathtt{pushLeft} </tex> и <tex> \mathtt{pushRight} </tex> {{---}} функции, реализующие операцию <tex> \mathtt{push} </tex> для соответствующего стека;  
* <tex> \mathrm {popLeft} </tex> и <tex> \mathrm {popRight} </tex> {{---}} аналогично операции <tex> \mathrm {pop} </tex>.
+
* <tex> \mathtt{popLeft} </tex> и <tex> \mathtt{popRight} </tex> {{---}} аналогично операции <tex> \mathtt {pop} </tex>.
  
 
=== push ===
 
=== push ===
Строка 96: Строка 96:
 
     '''return''' popRight()
 
     '''return''' popRight()
  
При выполнении операции <tex> \mathrm {push} </tex> будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию <tex> \mathrm {pop} </tex> из первого стека, третью во второй стек на финальный <tex> \mathrm {pop} </tex>. Тогда для операций <tex> \mathrm {pop} </tex> учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции <tex> \mathrm {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>.
Строка 103: Строка 103:
 
* Эту реализацию несложно модифицировать для получения минимума в текущей очереди за <tex>O(1)</tex>.
 
* Эту реализацию несложно модифицировать для получения минимума в текущей очереди за <tex>O(1)</tex>.
 
'''Минусы:'''
 
'''Минусы:'''
* Если <tex>\mathrm{leftStack}</tex> не пуст, то операция <tex> \mathrm {pop} </tex> может выполняться <tex>O(n)</tex> времени, в отличии от других реализаций, где <tex> \mathrm {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>.
  
 
== Реализация на шести стеках ==
 
== Реализация на шести стеках ==

Версия 22:52, 5 мая 2015

Определение

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]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):
  elements[tail] = x
  tail = (tail + 1) % n

pop

T pop():
  x = elements[head]
  head = (head + 1) % n
  return x

size

int size(s : stack<T>)
  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]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 rigthStack.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] истинного времени на операцию.

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

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

Плюсы:

Минусы:

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

См. также

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