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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Очередь диспетчеризации задач

Из книги автора

Очередь диспетчеризации задач TDE всех задач, которые могут выполняться на процессоре в любой данный момент времени, объединены в структуру данных, называемую очередью диспетчеризации задач TDQ (task dispatching queue). TDQ реализована как связный список в памяти, в котором TDE


8.1.4 Управление приоритетами

Из книги автора

8.1.4 Управление приоритетами Процессы могут управлять своими приоритетами с помощью системной функции nice:nice(value);где value — значение, в процессе пересчета прибавляемое к приоритету процесса:приоритет = (ИЦП/константа) + (базовый приоритет) + (значение nice)Системная функция nice


Очередь видеомонтажа

Из книги автора

Очередь видеомонтажа Окно очереди видеомонтажа, расположенное в левой части окна Video Post (Видеомонтаж), представляет собой список событий, выполняемых последовательно сверху вниз. Если в списке присутствуют события, являющиеся дочерними по отношению к другим событиям


Двусторонняя очередь (Deque)

Из книги автора

Двусторонняя очередь (Deque) deque - вид последовательности, которая, подобно вектору, поддерживает итераторы произвольного доступа. Кроме того она поддерживает операции вставки и стирания в начале или в конце за постоянное время; вставка и стирание в середине занимают


Очередь (Queue)

Из книги автора

Очередь (Queue) Любая последовательность, поддерживающая операции front, push_back и pop_front, может использоваться для модификации queue. В частности, могут использоваться list и deque.template ‹class Container›class queue { friend bool operator==(const queue‹Container›& х, const queue‹Container›& y); friend bool operator‹(const


Очередь с приоритетами (Priority queue)

Из книги автора

Очередь с приоритетами (Priority queue) Любая последовательность, с итератором произвольного доступа и поддерживающая операции front, push_back и pop_front, может использоваться для модификации priority_queue. В частности, могут использоваться vector и deque.template ‹class Container, class Compare = less‹Container::value_type›


Очередь по приоритету

Из книги автора

Очередь по приоритету Фактически, упомянутый пример обусловливает название новой структуры данных, называемой очередью по приоритету. Для очереди по приоритету (priority queue) определены две базовых операции: добавление элемента (как и ранее) и извлечение элемента с


У11.10 Модуль "очередь"

Из книги автора

У11.10 Модуль "очередь" Напишите класс, реализующий очередь (стратегию доступа "первый пришел - первый ушел", FIFO - "first in - first out"). Задайте подходящие утверждения в стиле класса STACK этой


Очередь сообщений

Из книги автора

Очередь сообщений Если вы в данный момент не подключены к Интернету, ваши сообщения будут помещаться в очередь, а потом, когда вы подключитесь, будут отправлены получателям.Для вызова окна очереди SMS выполните команду Сообщения > Очередь SMS. Появится окно c перечнем


Почему республиканский заворот «Обамакэра» бьёт в первую очередь по айтишникам Сергей Голубицкий

Из книги автора

Почему республиканский заворот «Обамакэра» бьёт в первую очередь по айтишникам Сергей Голубицкий Опубликовано 04 октября 2013 В минувшую субботу палата представителей США приняла две поправки, в очередной раз притормозившие реализацию «Закона о