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

Материал из Викиконспекты
Перейти к: навигация, поиск
(empty)
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
 
[[Файл: Fifo_new.png|right|150px]]
 
[[Файл: Fifo_new.png|right|150px]]
'''Очередь''' (''Queue'')  — это структура данных, добавление и удаление элементов в которой происходит путём операций <math> \mathrm {push} </math> и <math> \mathrm {pop} </math> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (''first-in, first-out FIFO''). У очереди имеется '''голова''' (''head'') и '''хвост''' (''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове.
+
'''Очередь''' (''Queue'')  {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <math> \mathrm {push} </math> и <math> \mathrm {pop} </math> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (''head'') и '''хвост''' (''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове.
*<math> \mathrm {push} </math> (запись в очередь) - операция вставки нового элемента.
+
*<math> \mathrm {push} </math> (запись в очередь) {{---}} операция вставки нового элемента.
*<math> \mathrm {pop} </math> (снятие с очереди) - операция удаления нового элемента.
+
*<math> \mathrm {pop} </math> (снятие с очереди) {{---}} операция удаления нового элемента.
*<math> \mathrm {empty} </math> - проверка очереди на наличие в ней элементов
+
*<math> \mathrm {empty} </math> {{---}} проверка очереди на наличие в ней элементов
  
 
== Реализация на массиве ==
 
== Реализация на массиве ==
Строка 43: Строка 43:
 
Реализация очереди на односвязном списке:
 
Реализация очереди на односвязном списке:
 
=== list ===
 
=== list ===
* <tex>x.value</tex> - поле, в котором хранится значение элемента
+
* <tex>x.value</tex> {{---}} поле, в котором хранится значение элемента
* <tex>x.next</tex> - указатель на следующий элемент очереди
+
* <tex>x.next</tex> {{---}} указатель на следующий элемент очереди
  
 
=== push ===
 
=== push ===
Строка 77: Строка 77:
 
Очередь можно реализовать на двух [[Стек|стеках]] <tex>leftStack</tex> и <tex>rightStack</tex>. Один из стеков <tex>(leftStack)</tex> будем использовать для операции <math> \mathrm {push} </math>, другой для операции <math> \mathrm {pop} </math>. При этом, если при попытке извлечения элемента из <tex>rightStack</tex> он оказался пустым, просто перенесем все элементы из <tex>leftStack</tex> в него (при этом элементы в <tex>rightStack</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>leftStack</tex> станет пустым).
 
Очередь можно реализовать на двух [[Стек|стеках]] <tex>leftStack</tex> и <tex>rightStack</tex>. Один из стеков <tex>(leftStack)</tex> будем использовать для операции <math> \mathrm {push} </math>, другой для операции <math> \mathrm {pop} </math>. При этом, если при попытке извлечения элемента из <tex>rightStack</tex> он оказался пустым, просто перенесем все элементы из <tex>leftStack</tex> в него (при этом элементы в <tex>rightStack</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>leftStack</tex> станет пустым).
  
* <math> \mathrm {pushLeft} </math> и <math> \mathrm {pushRight} </math> - функции, реализующие операцию <tex>push</tex> для соответствующего стека;  
+
* <math> \mathrm {pushLeft} </math> и <math> \mathrm {pushRight} </math> {{---}} функции, реализующие операцию <tex>push</tex> для соответствующего стека;  
* <math> \mathrm {popLeft} </math> и <math> \mathrm {popRight} </math> - аналогично операции <math> \mathrm {pop} </math>.
+
* <math> \mathrm {popLeft} </math> и <math> \mathrm {popRight} </math> {{---}} аналогично операции <math> \mathrm {pop} </math>.
  
 
=== push ===
 
=== push ===

Версия 19:51, 11 июня 2014

Определение

Fifo new.png

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

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

Реализация на массиве

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

  • [math]head[/math] (голова очереди)
  • [math]tail[/math] (хвост очереди)
  • [math]size[/math] (размер очереди)

push

function push(x):
 elements[tail] = x
 tail = (tail + 1) % elements.length
 size++

pop

function pop():
  if !empty()
    x = elements[head]
    head = (head + 1) % elements.length
    size--
    return x

empty

function empty():
  return size == 0

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

Плюсы:

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

Минусы:

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

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

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

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

list

  • [math]x.value[/math] — поле, в котором хранится значение элемента
  • [math]x.next[/math] — указатель на следующий элемент очереди

push

function push(x):
  element = tail
  tail = new list(x, NULL)
  if size == 0
    head = tail
  else 
    element.next = tail
  size++

pop

function pop():
  if empty()
    return
  element = head
  head = head.next
  size--
  return element

empty

function empty():
  return size == 0
Queue.png

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

Минусы:

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

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

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

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

push

function push(x):
  pushLeft(x)

pop

function pop():
  if !rigthStack.empty()
    return popRight() 
  else
    while !leftStack.empty()
      pushRight(popLeft())
    return popRight()

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

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

Минусы:

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

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

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

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

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

Плюсы:

Минусы:

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

См. также

Ссылки