Очередь
Определение
Очередь (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()
Если
не пуст, то операция может выполняться времени.При выполнении операции
будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию из первого стека, третью во второй стек на финальный . Тогда для операций учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции .Таким образом, для каждой операции требуется
монет, а значит, cредняя амортизационная стоимость операций .Минусы:
- В отличии от реализации очереди на массиве и списках операции работают за амортизированное
См. также
Ссылки
- Википедия - Очередь (программирование)
- Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
- T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262