Priority Queue Implementation using Linked List in C++

Linked List implementation can be the preferred choice for Priority Queue when the application uses dynamic data. Priority queues can be either ordered or unordered. In an ordered implementation, the elements are sorted based on their priority. Therefore, the dequeue operation works faster to retrieve the data.

• See Priority Queue Implementation using unordered Linked List to perform insertions faster.
• Alternatively, see Priority Queue Implementation using Array to work with static data.

1. Representation

The elements are enqueued in the order of 10, 20, and 30 and they are sorted as per their priorities P1, P2, and P3.

/**
 * Queue Node Representation
 */
 struct Node {
     int element;
     int priority; // Lowest number indicates high priority
     Node* next;
 };

// Queue front pointer
Node* front = NULL;

2. Priority Queue Implementation using Linked List

/**
 * C++ example to demonstrate the Priority Queue implementation using ordered Linked List
 */
#include <iostream>
using namespace std;

/**
 * Queue Node Representation
 */
 struct Node {
     int element;
     int priority; // Lowest number indicates high priority
     Node* next;
 };

/**
 * Priority Queue implementation using ordered Linked List
 */
class PriorityQueue
{
private:
    // Queue front pointer
    Node* front;
    
public:
    // Constructor
    PriorityQueue() : front(NULL) {}

    // Enqueue new element to Queue
    void enqueue(int element, int priority);

    // Dequeue an element from Queue
    int dequeue();

    // Returns the top element without deleting
    int peek();

    // Print the Queue
    void display(string msg);

    // Check if the Queue is empty
    bool isEmpty();
};

// Enqueue new element to Queue
void PriorityQueue::enqueue(int element, int priority) {		
    // Step 1: Create the new node with priority
    Node* node = new Node();
    if (node == NULL) {
        cout << "System out of memory" << endl;
        return;
    }
    node->element = element;
    node->priority = priority;
	
    // Step 2: Check if the Queue is empty (or) the new node has higher
    // priority than the Front node.        
    if (front == NULL || priority < front->priority) {
		// Step 3. If true, connect the new node at Front and Exit.

        // Link the new node to point the Front
        node->next = front;
		// Set the Front to point the new node
        front = node;			
		return;
    }

    // Step 4. Iterate the list from Front based on the priority and find the node
    // after which the new node can be linked.
    Node* pos = front;
    while (pos->next != NULL && priority >= pos->next->priority) {
        pos = pos->next;
    }

    // Step 5. Link the new node to point the next of identified node
    node->next = pos->next;		
    // Step 6. Link the identified node to point the new node
    pos->next = node;
}

// Dequeue an element from Queue
int PriorityQueue::dequeue() {
    // Step 1. Check if the Queue is empty
    if (front == NULL) {
        return -1;
    }
    
    // Step 2. Retrieve the element at Front
    int element = front->element;
	
    // Step 3. Remember the front node in a temporary pointer
    Node* tmp = front;
	
    // Step 4. Change the Front to point the next node
    front = front->next;
	
    // Step 5. Delete the node referenced in the temporary pointer
    delete tmp;
    
    return element;
}

// Returns the top element without deleting
int PriorityQueue::peek() {
    if (isEmpty()) {
        return -1;
    }
    return front->element;
}

// Print the Queue
void PriorityQueue::display(string msg) {
    cout << msg << endl;
    if (isEmpty()) {
        return;
    }
    
    cout << front->element << " (" << front->priority << ")" << " <-- front" << endl;
    for (Node* node=front->next; node != NULL; node = node->next) {
        cout << node->element << " (" << node->priority << ")" << endl;
    }
    cout << endl;
}

// Check if the Queue is empty
bool PriorityQueue::isEmpty() {
    if (front == NULL) {
        cout << "Queue is Empty" << endl;
        return true;
    }
    return false;
}

// The main function to begin the execution
int main()
{
    // Create a Queue
    PriorityQueue queue;
    
    // Push the elements 10 (3), 20 (1), and 30 (2)
    queue.enqueue(10, 3);
    queue.display("Queue after enqueue(10, 3)");
    queue.enqueue(20, 1);
    queue.display("Queue after enqueue(20, 1)");
    queue.enqueue(30, 2);
    queue.display("Queue after enqueue(30, 2)");

    // Get the peek element
    int element = queue.peek();
    cout << "Peek element returned " << element << endl;
    
    // Pop the elements from Queue one by one
    for (int i=0; i < 3; i++) {
        element = queue.dequeue();
        cout << "Dequeue element returned " << element << endl;
        queue.display("Queue after dequeue()");
    }
}

Output

Queue after enqueue(10, 3)
10 (3) <-- front

Queue after enqueue(20, 1)
20 (1) <-- front
10 (3)

Queue after enqueue(30, 2)
20 (1) <-- front
30 (2)
10 (3)

Peek element returned 20
Dequeue element returned 20
Queue after dequeue()
30 (2) <-- front
10 (3)

Dequeue element returned 30
Queue after dequeue()
10 (3) <-- front

Dequeue element returned 10
Queue after dequeue()
Queue is Empty

3. Operations of Priority Queue

Here, we discuss the operations of a Priority Queue with a sorted Linked List.

3.1. Enqueue with Linked List

The enqueue operation finds the correct position based on its priority value and inserts the element. The original insertion order is preserved in case two elements have the same priority values.

Algorithm

1. Create a new Node with the Priority
2. Check if the Queue is empty (or) if the new node has higher priority than the Front node.
3. If true, connect the new node at the Front and Exit.
   • Link the new node to point to the Front
   • Set the Front to point to the new node
   • Exit
4. Otherwise, iterate the list from the Front based on the priority and find the node after which the new node can be linked.
5. Link the new node to point to the identified node.
6. Link the identified node to point to the new node.

Examples

Let’s take the following queue to proceed with the enqueue. The Priority Queue is initially empty so the Front is NULL.

Enqueue Element (10) with Priority (3). Since the queue is empty, insert the new node at the Front side.

Next, Enqueue the Element (20) with Priority (1). This must be enqueued at Front since it has the highest priority.

Enqueue the Element (30) with Priority (2). The list has to be searched to find the sorted position based on its priority (2). The priority falls between P1 and P3, so insert the node between (20) and (10).

3.2. Dequeue with Linked List

Enqueue operation keeps the nodes sorted as per their priority. The highest priority is available at the Front side. So, the Dequeue always removes from the Front of the Queue. The next node of the Queue becomes the Front after Dequeue. The Front will be pointing to NULL when deleting the last node in the list.

Algorithm

1. Check if the Queue is empty.
2. Retrieve the element from the Front node.
3. Store the front node in a temporary variable.
4. Disconnect the front node by updating the Front pointer to the next node.
5. Finally, delete the node referenced in the temporary variable.

Examples

Let’s Dequeue an Element from the following Priority Queue

Dequeue the highest priority element which is (20). Disconnect the node by updating the Front pointer to the next node (30).

Repeat the same procedure to dequeue the next element (30).

Finally, the queue becomes empty after removing the last element.