Очередь
Определение
Очередь (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), в который переходит из обычного режима, когда после очередной операции в стеке становится больше элементов, чем в стеке . При активации инициализируется счетчик , показывающий, сколько находится неизвлеченных элементов в стеке .
Обрабатываем поступающие дальше операции следующим образом: кладет элемент в парный нашему стеку стек , а извлекает элемент только из , при этом уменьшая счетчик . в этом режиме всегда возвращает , так как при перекопировании элементов из всегда остаются в очереди, так как извлечение происходит только из .
Пусть в этот момент в стеке , а значит, и в стеке находились элементов, тогда в стеке их . Заметим, что мы можем корректно обработать все операции и первые операций , то есть у нас есть на перекопирование не меньше операции вместе с активирующей.
Корректной ситуация станет, когда в стеках и парном стеке окажутся все находящиеся на момент активации в очереди и не извлеченные после активации элементы, причем в порядке, правильном для извлечения.
Чтобы получить корректную ситуацию и перейти в обычный режим, нужно:
- Извлечь весь стек в стек , действий.
- Извлечь весь стек в стеки , действие.
- Извлечь элементов в стеки , а оставшиеся выкинуть, действий.
- Назначить текущей копией стека , а — текущим стеком для операций , действия.
Таким образом, получили действий на операций с очередью, то есть выполняя 3 дополнительных действия во время операции мы успеем перекопировать все элементы вовремя. Тогда очередь действительно будет выполнять каждое действие за реального времени.
Теперь рассмотрим, какие изменения произошли за время перекопирования. Пусть среди следующих за активацией операций у нас операций и операций . Тогда в стеке оказалось элементов, а в новом стеке оказалось элементов. Тогда в стеке на больше элементов, чем в стеке , а это значит, что до следующего режима перекопирования операции, и за это время мы успеем очистить старый стек , в котором находится максимум ненужных элементов, просто удаляя при каждой операции в обычном режиме один элемент из , если он непуст.
Заметим, что вышеприведенный алгоритм гарантирует нам, что в обычном режиме в стеке находится не больше элементов, чем в , так что проверка на пустоту очереди при обычном режиме сводится к проверке на пустоту стека .
Пусть наша очередь имеет стеки , а также переменные и , тогда следующий псевдокод выполняет требуемые операции.
empty
empty() return !recopy and R.size == 0
push
push(x)
if !recopy
L1.push(x)
checkRecopy()
else
L2.push(x)
checkNormal()
pop
pop()
if !recopy
tmp = R.pop()
Rc1.pop()
checkRecopy()
return tmp
else
tmp = Rc1.pop()
toCopy = toCopy - 1
checkNormal()
return tmp
checkRecopy
checkRecopy()
if Rc2.size > 0
Rc2.pop()
recopy = L1.size > R.size
if recopy
toCopy = Rc1.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
// Пытаемся перекопировать L1 в R и Rc2
while toDo > 0 and L1.size > 0
x = L1.pop()
R.push(x)
Rc2.push(x)
toDo = toDo - 1
// Пытаемся перекопировать T в R и Rc2 с учетом toCopy
while toDo > 0 and T.size > 0
x = T.pop()
if toCopy > 0
R.push(x)
Rc2.push(x)
toCopy = toCopy - 1
toDo = toDo - 1
// Если все скопировано, то меняем роли L1, L2 и Rc1, Rc2
if T.size = 0
swap(L1, L2)
swap(Rc1, Rc2)
Плюсы:
- реального времени на операцию.
- Возможность дальнейшего улучшения до персистентной очереди, если использовать персистентные стеки.
Минусы:
- Больше константа на операции.
- Больше расход памяти.
- Больше сложность реализации.
См. также
Ссылки
- Википедия - Очередь (программирование)
- Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 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
