Очередь и очередь с приоритетами
Абстракция очереди реализует метод доступа 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 можно найти более подробное объяснение и иллюстрации использования такой очереди.)
