Приоритетная очередь в примере C ++ | Сегодняшняя тема — программа очереди приоритетов C ++. Очередь — это структура данных, реализация которой основана на FIFO (First In First Out), то есть где вставка находится сзади, а удаление — спереди. Приоритетная очередь — это особый тип очереди. Priority Queue не соответствует концепции FIFO, как Queue. Каждый элемент в очереди Priority связан с некоторым приоритетом. Удаление элемента происходит в зависимости от приоритета. Элемент с наивысшим приоритетом — это первый элемент, который удаляется из очереди. Элементы с одинаковым приоритетом сортируются на основе FIFO.
Priority Queue в C ++
Priority Queue реализован как адаптеры контейнера, которые использовать инкапсулированный объект определенного класса контейнера в качестве базового контейнера.
Они содержатся в библиотеке STL библиотеки C ++. Это сортирует самый высокий элемент спереди, а остальные — в порядке убывания. У них есть определенный набор функций-членов для доступа к его элементам.
Основные операции Priority Queue
insert (item, priority)
Вставляет элемент с его приоритетом в очередь приоритетов.
getHighestPriority ()
Возвращает элемент с наивысшим приоритетом в очереди.
delete ()
Удаляет элемент с наивысшим приоритетом и дает удаленный предмет.
isEmpty()
Проверяет, пуста ли очередь.
isFull ()
Проверяет, заполнена ли очередь или нет.
Преимущества очереди с приоритетом
Узлам присваивается вес, что позволяет им двигаться в направлении в голове очереди, а не в хвосте очереди, как в обычной очереди.
Недостатки очереди с приоритетом
Теперь вставка не занимает постоянного времени, как очередь, потому что мы должны применить сортировку вставкой также для вставки элемента на основе их приоритета.
Реализация через связанный список помогает добиться постоянного времени для вставки.
Алгоритм или псевдокод
Insert (item, priority) Первый элемент для вставки: Insert (10,1) Второй элемент для вставки: Insert (30,3) Третий элемент для вставки : Вставить (20,2) Четвертый элемент для вставки: Insert (40,4) Очередь после вставки: 40 30 20 10 Удалить () Первое удаление: 40 Очередь после удаления: 30 20 10 Вставить (50,4) Вставить (60,4) Очередь после вставки: 50 60 30 20 10
Здесь мы видим, что элементы вставляются в зависимости от их приоритета.
Элемент с наивысшим приоритетом находится в начале очереди. При удалении первый элемент очереди удаляется из очереди. Элемент с таким же приоритетом сортируется на основе FIFO..
Программа приоритетной очереди на C ++
Пример 1: Создайте очередь, используя STL и выполнять основные функции.
#include #include #include #include #include using namespace std; struct n//объявление узла {приоритет int; int info; struct n * next;}; class Priority_Queue {private: n * f; public: Priority_Queue () {f = NULL; } пустая вставка (int i, int p) {n * t, * q; t = новый n; т-> информация = я; т-> приоритет = р; if (f == NULL || p приоритет) {t-> next = f; f = t; } else {q = f; while (q-> next! = NULL && q-> next-> priority next; t-> следующий = q-> следующий; q-> следующий = t; }} void delet () {н * т; if (f == NULL)//если очередь равна нулю cout info следующий; бесплатно (t); }} void show ()//очередь печати {{n * ptr; ptr = f; if (f == NULL) cout priority info следующий; }}}}; int main () {int c, я, р; Priority_Queue pq; do {cout > c; switch (c) {case 1: cout > я; cout > p; pq.insert (i, p); перерыв; случай 2: pq.delet (); перерыв; случай 3: pq.show (); перерыв; случай 4: перерыв; по умолчанию: cout См. результат.
Пример 2: Создайте очередь с помощью списка ссылок и выполните необходимые функции.
#include #include с использованием пространства имен std ; void displaypq (priority_queue pq) {priority_queue pqueue = pq; в то время как (! pqueue.empty ()) {cout pq; pq.push (1); pq.push (3); pq.push (5); pq.push (7); pq.push (9); cout См. вывод.
Заключение
Очереди с приоритетом - это тип адаптеров контейнера, специально разработанный таким образом, что первый элемент очереди является наибольшим из всех элементов в очереди, а элементы находятся в невозрастающий порядок.
Наконец, приоритетная очередь в C ++. Пример | Программа очереди приоритетов C ++ завершена.
Рекомендуемые сообщения
Пример очереди в C ++
Deque в примере C ++
Учебник по функциям C ++
Учебник по массивам C ++ с примером
Учебник по итераторам C ++ с примером
