Priority Queue

In this lesson, we will explore the concept of a priority queue and how to implement it using arrays and heaps.

A priority queue is a special type of queue where each element has an associated priority. The element with the highest priority is dequeued first.

Implementation

To implement a priority queue, we can use an array of fixed size. In this implementation, we assume that higher values indicate higher priorities. The enqueue operation inserts an element into the priority queue based on its priority, and the dequeue operation removes the element with the highest priority.

Here is a C++ implementation of a priority queue using arrays:

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

const int MAX_SIZE = 100;

​

class PriorityQueue {

private:

    int arr[MAX_SIZE];

    int size;

​

public:

    PriorityQueue() {

        size = 0;

    }

​

    bool isEmpty() {

        return size == 0;

    }

​

    bool isFull() {

        return size == MAX_SIZE;

    }

​

    void enqueue(int item) {

        if (isFull()) {

            cout << "Priority Queue is full. Unable to enqueue." << endl;

        } else {

            int i;

            for (i = size - 1; i >= 0; i--) {