Очередь — различия между версиями
Whiplash (обсуждение | вклад) м |
Whiplash (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Определение == | == Определение == | ||
| − | '''Очередь''' (''Queue'') — это динамическое множество, добавление и удаление элементов в котором происходит путём операций ''Push'' и ''Pop'' соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется стратегия «первым вошел — первым вышел» (first-in, first-out — FIFO). | + | [[Файл: Fifo_new.png|thumb|right|150px|Очердь]] |
| + | '''Очередь''' (''Queue'') — это динамическое множество, добавление и удаление элементов в котором происходит путём операций ''Push'' и ''Pop'' соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется стратегия «первым вошел — первым вышел» (''first-in, first-out — FIFO''). Очередь подобна, например, живой очередь в магазине за хлебом. У нее имеется '''голова''' (''head'') и '''хвост''' (''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте, точно так же, как человек занимает очередь последним, чтобы купить хлеб. Из очереди всегда выводится элемент, который находится в её головной части аналогично тому, как человек, который ждал дольше всех, расплачивается за хлеб. | ||
| + | == Реализация на массиве == | ||
| + | Операция вставки нового элемента называется <tex>push</tex> (запись в очередь), а операция удаления - <tex>pop</tex> (снятие с очереди), <tex>empty</tex> - проверка очереди на наличие в ней элементов. Очередь, способная вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>elements[1..n]</tex>. | ||
| − | + | Очередь будет обладать следующими полями: | |
| + | :<tex>head</tex> (голова очереди) | ||
| + | :<tex>tail</tex> (хвост очереди) | ||
| + | :<tex>size</tex> (размер очереди) | ||
| − | + | === 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 |
| − | + | Каждая операция выполняется в течение времени <tex>O(1)</tex>. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | == | ||
| − | |||
| − | |||
| − | == | ||
| − | |||
| − | |||
| − | |||
== См. также == | == См. также == | ||
Версия 21:06, 12 марта 2012
Определение
Очередь (Queue) — это динамическое множество, добавление и удаление элементов в котором происходит путём операций Push и Pop соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется стратегия «первым вошел — первым вышел» (first-in, first-out — FIFO). Очередь подобна, например, живой очередь в магазине за хлебом. У нее имеется голова (head) и хвост (tail). Когда элемент ставится в очередь, он занимает место в её хвосте, точно так же, как человек занимает очередь последним, чтобы купить хлеб. Из очереди всегда выводится элемент, который находится в её головной части аналогично тому, как человек, который ждал дольше всех, расплачивается за хлеб.
Реализация на массиве
Операция вставки нового элемента называется (запись в очередь), а операция удаления - (снятие с очереди), - проверка очереди на наличие в ней элементов. Очередь, способная вместить не более элементов, можно реализовать с помощью массива .
Очередь будет обладать следующими полями:
- (голова очереди)
- (хвост очереди)
- (размер очереди)
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
Каждая операция выполняется в течение времени .
См. также
