Очередь

Определение

Очердь

Очередь (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()) 
       then x = elements[head]
            head = (head + 1) % elements.length
            size--
            return x

empty

empty()
   return size == 0

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

См. также

• Стек

Ссылки

http://ru.wikipedia.org/wiki/Очередь_(программирование)