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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (push)
м (empty)
Строка 27: Строка 27:
 
  empty()
 
  empty()
 
     return size == 0
 
     return size == 0
Каждая операция выполняется за <tex>O(1)</tex> времени.
+
Из-за того что нам не нужно перевыделять память, каждая операция выполняется за <tex>O(1)</tex> времени.
  
 
'''Плюсы:'''
 
'''Плюсы:'''

Версия 17:33, 10 июня 2012

Определение

Fifo new.png

Очередь (Queue)  — это структура данных, добавление и удаление элементов в которой происходит путём операций Push и Pop соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (first-in, first-out — FIFO). Очередь подобна, например, живой очереди к врачу. У нее имеется голова (head) и хвост (tail). Когда элемент ставится в очередь, он занимает место в её хвосте, точно так же, как человек занимает очередь последним, чтобы попасть к врачу. Из очереди всегда выводится элемент, который находится в ее голове части аналогично тому, как в кабинете врача всегда заходит больной, который ждал дольше всех.

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

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

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

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

push

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

pop

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

empty

empty()
   return size == 0

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

Плюсы:

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

Минусы:

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

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

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

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

list

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

push

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

pop

pop()
   if !empty()
      element = head
      delete head
      head = element.next
      size--
      return element

empty

empty()
   return size == 0
Queue.png

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

Минусы:

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

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

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

[math]pushLeft[/math] и [math]pushRight[/math] - функции, реализующие операцию [math]push[/math] для соответствующего стека; [math]popStack[/math] - операция [math]pop[/math] для [math]rightStack[/math].

push

push(x)
   leftStack.pushLeft(x)

pop

if !rigthStack.empty()
   return rightStack.popStack()

else
   if !leftStack.empty()
      while !leftStack.empty()
         rightPush(leftStack[leftSize])
         leftSize--
      return rightStack.popStack()

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

Минусы:

  • Много времени тратится на перекладывание элементов из одного стека в другой.

См. также

Ссылки