Очередь — различия между версиями
(→Реализация на двух стеках) |
(→Реализация на массиве) |
||
| Строка 15: | Строка 15: | ||
=== push === | === push === | ||
push(x) | push(x) | ||
| − | + | elements[tail] = x | |
| − | + | tail = (tail + 1) % elements.length | |
| − | + | size++ | |
=== pop === | === pop === | ||
pop() | pop() | ||
| − | + | if !empty() | |
| − | + | x = elements[head] | |
| − | + | head = (head + 1) % elements.length | |
| − | + | size-- | |
| − | + | return x | |
=== empty === | === empty === | ||
empty() | empty() | ||
| − | + | return size == 0 | |
Каждая операция выполняется за <tex>O(1)</tex> времени. | Каждая операция выполняется за <tex>O(1)</tex> времени. | ||
Версия 16:36, 6 июня 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()
x = elements[head]
head = (head + 1) % elements.length
size--
return x
empty
empty() return size == 0
Каждая операция выполняется за времени.
Плюсы:
- - прост в разработке
- - по сравнению с реализацией на списке, есть незначительная экономия памяти
Минусы:
- - количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива)
- - при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив
Реализация на списке
Для данной реализации очереди необходимо создать список () и операции работы на созданном списке.
Реализация очереди на односвязном списке:
list
- - поле, в котором хранится значение элемента
- - указатель на следующий элемент очереди
push
push(x)
el = tail
tail.value = x
tail.next = null
if size == 0
then head = tail
else el.next = tail
size++
pop
pop()
if !empty()
then x = head.value
head = head.next
size--
return x
empty
empty()
return size == 0
Каждая операция выполняется за время .
Минусы:
- Память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве
Реализация на двух стеках
Очередь можно реализовать на двух стеках и . Один из стеков будем использовать для операции , другой для операции .
и - функции, реализующие операцию для соответствующего стека; - операция для .
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()
Каждая операция выполняется за амортизированную .
Минусы:
- Много времени тратится на перекладывание элементов из одного стека в другой.
См. также
Ссылки
- Википедия - Очередь (программирование)
- Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
- T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262
