Очередь
Определение
Очередь (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)
element = tail
tail = new list(x, NULL)
if size == 0
head = tail
else
element.next = tail
size++
pop
pop()
if empty()
return
element = head
head = head.next
size--
return element
empty
empty() return size == 0
Каждая операция выполняется за время .
Минусы:
- Память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве
Реализация на двух стеках
Очередь можно реализовать на двух стеках и . Один из стеков будем использовать для операции , другой для операции . При этом, если при попытке извлечения элемента из он оказался пустым, просто перенесем все элементы из в него (при этом элементы в получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а станет пустым).
- и - функции, реализующие операцию для соответствующего стека;
- и - аналогично операции .
push
push(x) pushLeft(x)
pop
if !rigthStack.empty()
return popRight()
else
while !leftStack.empty()
pushRight(popLeft())
return popRight()
При выполнении операции будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию из первого стека, третью во второй стек на финальный . Тогда для операций учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции .
Таким образом, для каждой операции требуется монет, а значит, амортизационная стоимость операций .
Минусы:
- Если не пуст, то операция может выполняться времени, в отличии от других реализаций, где всегда выполняется за
Реализация на шести стеках
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с истинного времени на операцию.
Сначала будем действовать аналогично случаю с двумя стеками. Пусть у нас есть стек для операций и стек для операций . К моменту опустошения стека нам нужно успеть получить стек , содержащий текущие элементы стека в правильном для извлечения порядке. Перекопирование (recopy mode) начнется, когда появится опасность того, что мы не сможем за оставшиеся операций со стеком перекопировать стек в новый стек . Очевидно, это ситуация , пусть такое состояние отражает специальная переменная логического типа .
Понятно, что во время перекопирования могут поступить операции , а стек в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек , в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями и , и вроде бы все станет хорошо.
Однако, если реализовать этот алгоритм, мы получим неприятную вещь: старый стек может и не опустошиться за это время, то есть мы получили два стека с выходными данными, а значит возможен случай (например, когда все поступающие операции ), когда при следующем перекопировании у нас не будет свободного стека для копировании туда элементов . Для преодоления этой проблемы мы принудительно будем извлекать все элементы из стека во вспомогательный стек , затем копировать элементы из стека в , а затем обратно копировать элементы из стека в . Легко показать, что приведенный алгоритм как раз получает на выходе в все элементы стеков в правильном порядке.
Но этого еще недостаточно. Если мы принудительно извлекаем элементы из стека , появляются следующие проблемы:
- Что вернуть при операции ? Для этого заведем себе стек — копию стека , из которого мы и будем извлекать требуемые элементы.
- Как поддерживать корректность такой копии? Поскольку этот стек нужен только для перекопирования, а во время него он занят, нужна запасная копия , в которую мы будем копировать все элементы, которые мы копируем в , а по окончании перекопирования поменяем ролями стеки , как мы делали со стеками .
- Как учесть, что во время перекопирования часть элементов была извлечена из ? Для этого заведем специальную переменную , которая показывает, сколько корректных элементов находится в стеке и уменьшается при каждом извлечении из или операции . К счастью, все некорректные элементы будут нарастать с дна стека, так что мы никогда не извлечем некорректный элемент, если .
Теперь может возникнуть проблема с непустым после завершения перекопирования. Покажем, что мы всегда успеем его опустошить, если будем использовать дополнительное извлечение из него при каждой операции в обычном режиме, для этого полностью проанализируем алгоритм.
Пусть на начало перекопирования в стеке содержится элементов, тогда в стеке находится элементов. Мы корректно можем обработать любое количество операций , а также операций во время перекопирования всегда возвращает , так как мы не можем извлекать элементы из стека , который не пустой. Таким образом, вместе с операцией, активирующей перекопирование, мы гарантированно можем корректно обработать операцию.
Посмотрим на дополнительные действия, которые нам предстоят:
- Переместить содержимое в , действий.
- Переместить содержимое в стеки , действий.
- Переместить первые элементов из в , действий.
- Поменять ролями стеки , , действия.
Таким образом, получили дополнительных действия за операций, или дополнительных действия на операцию в режиме перекопирования, что и требовалось.
Теперь рассмотрим, как изменились наши стеки за весь период перекопирования. Договоримся, что операция не меняет очередь, то есть никакие дополнительные действия не совершаются. Пусть за следующих за активацией меняющих операций () поступило операций , операций . Очевидно, что после перекопирования в новых стеках окажется: элементов в , элементов в , то есть до следующего перекопирования еще операции. С другой стороны, стек содержал всего элементов, так что мы можем очистить его, просто удаляя по одному элементу при каждой операции в обычном режиме.
Итак, очередь будет состоять из шести стеков , а также двух внутренних переменных , которые нужны для корректности перекопирования.
Инвариант очереди (обычный режим):
- — копия
Тогда к следующему перекопированию () мы гарантированно будем иметь пустые стеки , которые нам понадобятся.
Инвариант очереди (режим перекопирования):
- Если , то первые элементов — корректны, то есть действительно содержатся в очереди.
Очередь будет работать в двух режимах:
- Обычный режим, кладем в , извлекаем из и из для поддержания порядка, операция .
- Режим перекопирования, кладем в , извлекаем из , , совершаем дополнительные действия.
Также после операции в обычном режиме следует проверка на активацию перекопирования(), если это так, , совершается первый набор дополнительных действий.
После операции в режиме перекопирования следует проверка на завершение перекопирования (), а при завершении меняются ролями стеки , .
Пусть наша очередь имеет стеки , а также переменные и , тогда следующий псевдокод выполняет требуемые операции.
empty
empty() return !recopy and R.size == 0
push
push(x)
if !recopy
L.push(x)
if Rc'.size > 0
Rc'.pop()
checkRecopy()
else
L'.push(x)
checkNormal()
pop
pop()
if !recopy
tmp = R.pop()
Rc.pop()
if Rc'.size > 0
Rc'.pop()
checkRecopy()
return tmp
else
tmp = Rc.pop()
toCopy = toCopy - 1
checkNormal()
return tmp
checkRecopy
checkRecopy()
recopy = L.size > R.size
if recopy
toCopy = R.size
additionalOperations()
checkNormal
checkNormal() additionalOperations() // Если мы не все перекопировали, то у нас не пуст стек T recopy = T.size != 0
additionalOperations
additionalOperations()
// Нам достаточно 3 операций на вызов
toDo = 3
// Пытаемся перекопировать R в T
while toDo > 0 and R.size > 0
T.push(R.pop())
toDo = toDo - 1
// Пытаемся перекопировать L в R и Rc'
while toDo > 0 and L1.size > 0
x = L.pop()
R.push(x)
Rc'.push(x)
toDo = toDo - 1
// Пытаемся перекопировать T в R и Rc' с учетом toCopy
while toDo > 0 and T.size > 0
x = T.pop()
if toCopy > 0
R.push(x)
Rc'.push(x)
toCopy = toCopy - 1
toDo = toDo - 1
// Если все скопировано, то меняем роли L1, L2 и Rc1, Rc2
if T.size = 0
swap(L, L')
swap(Rc, Rc')
Плюсы:
- реального времени на операцию.
- Возможность дальнейшего улучшения до персистентной очереди, если использовать персистентные стеки.
Минусы:
- Больше константа на операции.
- Больше расход памяти.
- Больше сложность реализации.
См. также
Ссылки
- Википедия - Очередь (программирование)
- Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
- T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262
- Hood R., Melville R. Real Time Queue Operations in Pure LISP. — Cornell University, 1980
