6.17. Очередь и очередь с приоритетами

6.17. Очередь и очередь с приоритетами

Абстракция очереди реализует метод доступа FIFO (first in, first out – “первым вошел, первым вышел”): объекты добавляются в конец очереди, а извлекаются из начала. Стандартная библиотека предоставляет две разновидности этого метода: очередь FIFO, или простая очередь, и очередь с приоритетами, которая позволяет сопоставлять элементы с их приоритетами. Текущий элемент помещается не в конец такой очереди, а перед элементами с более низким приоритетом. Программист, определяющий такую структуру, задает способ вычисления приоритетов. В реальной жизни подобное можно увидеть, скажем, при регистрации багажа в аэропорту. Как правило, пассажиры, чей рейс через 15 минут, передвигаются в начало очереди, чтобы не опоздать на самолет. Примером из практики программирования служит планировщик операционной системы, определяющий последовательность выполнения процессов.

Для использования queue и priority_queue необходимо включить заголовочный файл:

#include queue

Полный набор операций с контейнерами queue и priority_queue приведен в таблице 6.6.

Таблица 6.6. Операции с queue и priority_queue

Операция

Действие

empty()

Возвращает true, если очередь пуста, и false в противном случае

size()

Возвращает количество элементов в очереди

pop()

Удаляет первый элемент очереди, но не возвращает его значения. Для очереди с приоритетом первым является элемент с наивысшим приоритетом

front()

Возвращает значение первого элемента очереди, но не удаляет его. Применимо только к простой очереди

back()

Возвращает значение последнего элемента очереди, но не удаляет его. Применимо только к простой очереди

top()

Возвращает значение элемента с наивысшим приоритетом, но не удаляет его. Применимо только к очереди с приоритетом

push(item)

Помещает новый элемент в конец очереди. Для очереди с приоритетом позиция элемента определяется его приоритетом.

Элементы priority_queue отсортированы в порядке убывания приоритетов. По умолчанию упорядочение основывается на операции “меньше”, определенной над парами элементов. Конечно, можно явно задать указатель на функцию или объект-функцию, которая будет использоваться для сортировки. (В разделе 12.3 можно найти более подробное объяснение и иллюстрации использования такой очереди.)