Очередь
Содержание
Определение
Очередь (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.value = x tail.next = null if size == 0 head = tail else element.next = tail size++
pop
pop() if !empty() 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