Очередь
Содержание
Определение
Очередь (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()) then 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
Плюсы:
- размер очереди ограничен лишь объемом памяти
Минусы:
- сложение в разработке
- требуется больше памяти
См. также