Priority Queue Implementation using Linked List

Introduction

Raj is gonna get us all in trouble! Our teammate Raj is a really big procrastinator. He doesn’t do the tasks assigned to him on time for the group project. Luckily we have you, our coder friend, to write a code for prioritizing these tasks. 

Let’s implement our idea to define a workflow for our Mr. Procrastinator. The team wants you to write a code implementing a priority queue using linked lists. 

What is a Priority Queue?

So, what is a priority queue? A priority queue is a data structure where data with higher priority is popped or served before data with lower priority. This data is stored in the priority queue irrespective of the order in which it is pushed to the queue.

What about the tasks that have the same priority? Well, in that case, we can choose the First Come First Serve criteria to set the order. 

Suppose the order of tasks and their respective priorities is as follows:

Task1

Priority: 4

Task2

Priority: 1

Task3

Priority: 2

Task4

Priority: 3

The priority queue will store the data in following order:

Task1

Priority: 4

Task2

Priority: 1

Task3

Priority: 2

Task4

Priority: 3

If you look closely, you’ll notice that the priority queue has stored the data in non-decreasing order. So, a particular order is defined by the priority queue.

Smaller priority number has a higher priority. Strange! Isn’t it?. Well, it helps to remember when you study priority based scheduling in OS. However, you can define your criteria for the same. For example, you can decide to give higher priority to the bigger number. 

Structure of Data Item and operations

For our priority queue implementation using a linked list, the information will reside in each node along with the address to the next node. Every task will be given a priority number (priority) and a task name (data). So, every node will look like this -

It’s a good chance to revise our OOPS concepts to implement these nodes using class. Please see the code below for reference;

class Node {

 // Data members of our Node class.
 public:
    string data;
    int priority;
    Node* next;

  // New node constructor.
  Node(string data, int priority) 
  {
      this->data = data;
      this->priority = priority;
      this->next = NULL;
  }
};

Let’s take a quick look at the operations we need to include in our priority queue implementation. 

Functional Requirements

The priority queue implementation involves three operations: PushPeek, and Pop.

To carry out these operations, the following functions may be useful:

  1. push(): Inserts the node based on its priority number.
  2. pop(): Deletes the node from the beginning.
  3. peek(): Retrieves the node present at the beginning.
  4. print(): To check the order of tasks and their respective priorities.
  5. isEmpty(): To check if the priority queue is empty.

Here, print() and isEmpty() act as helper functions to make the code less redundant and insightful. Let’s look at the procedure to understand what’s going under the hood of our priority queue implementation.

Procedure

  1. isEmpty()
    A priority queue will be empty in two cases. Either no data is pushed yet or our Mr. Procrastinator, Raj has popped all the tasks assigned to him. So how do we check if our priority queue is empty? If the ‘NEXT’ pointer of the ‘HEAD’ node points to NULL, then we can say that our priority queue is empty.
     
  2. peek()
    To peek at our priority queue, check the first node of the linked list. The ‘NEXT’ pointer of the ‘HEAD’ node points to the first node of the linked list. If the head is pointing to NULL, that means our priority queue is empty.
    To check the first node of the linked list, we only need to access the ‘HEAD’ node, which is a constant time operation. So, the time complexity for the peek operation is O(1).
     
  3. pop()
    For pop operation, simply set the ‘NEXT’ pointer of ‘HEAD’ to the next of the first node.
    Don’t forget to free the first node!
    What if the priority queue is empty? 
    This is an edge case. If the priority queue is empty, then the ‘HEAD’ points to a NULL pointer. Trying to free a null pointer will result in a runtime error, known as segmentation fault. So, it’s advisable to check if the priority queue is empty before performing the pop operation. Our isEmpty() function can come in handy to check the same.
    Can you guess the time complexity of pop operation? 
    Just as similar to the peek operation, removing the first node of the linked list (if present) requires a constant time operation. So, the time complexity is O(1) for the same.
     
  4. push()
    Keep traversing through the linked list until you find the next node with lower priority (in other words, node with a higher priority number). Insert the newNode after your current node.
    What if there’s no next node?
    In that case, we have reached the end of the linked list and the newNode holds the lowest priority in the queue. Insert the newNode at the end of the linked list.
    For push operations, in the worst case scenario, we may have to traverse through the entire list as the priority of the input may be the lowest in the list. So, the time complexity becomes O(N) in the worst case.
     
  5. print()
    At some point, we will need to check if our priority queue implementation is working right. Or maybe we want to check all the data items present in our priority queue. In either case, we need to print our priority queue.
    To print the items of the priority queue, we need to traverse through the entire linked list. We’ll set a temporary pointer equal to the ‘HEAD’ of our data structure and keep printing the task name and its priority till we reach the end of the linked list.
    How will we know if we have reached the end? 
    Well, if there’s no next node available we can say we have reached the end.
    Traversing through the linked list is a linear-time operation. So, the time complexity for print() is O(N)

C++ Code for Reference

// Priority Queue Implementation.

#include <bits/stdc++.h>
using namespace std;

class Node {
    
    // Data members of Node class.
    public:
        string data;
        int priority;
        Node* next;

    // New node constructor.
    Node(string data, int priority)
    {
        this->data = data;
        this->priority = priority;
        this->next = NULL;
    }
};


class PriorityQueue {
    Node* head;
    
    public:
        PriorityQueue()
        {
            head = new Node("Head", INT_MIN);
        }
        void pop()
        {
        	// List is empty.
          	if(head->next == NULL)
              return;
  
          	// Storing the first node in a temporary variable.
          	Node* temp = head->next;     

          	// Shifting Next pointer of head node.
          	head->next = head->next->next; 

          	// Free the first node.           
          	free(temp);
        }

        void push(string tskNumber, int priority)
        {
            Node* newnode = new Node(tskNumber, priority);
            Node* temp = head;
            if(isEmpty())
            {
                head->next = newnode;
            }
            else
            {
                while(temp->next && temp->next->priority<=priority)
                {
                    temp = temp->next;
                }
                newnode->next = temp->next;
                temp->next = newnode;
            }
      }

      void print()
      {
          Node* temp = head;
          while( temp->next )
          {
              temp = temp->next;
              cout << temp->data << "  Priority:" << temp->priority <<endl;
          }
      }

      void peek()
      {
          // Priority Queue is empty.
          if(isEmpty())
          {
              cout<<"Nothing left to peek!\n";
          }
          else
          {
              cout << head->next->data << endl;
          }
      }

      bool isEmpty()
      {
          // 'head' is pointing to a NULL pointer.
          if(!head->next)
          	return true;
          else
          	return false;
      }

};

int main() 
{

    // Dynamic Binding to the PriorityQueue class.
    PriorityQueue* tasks = new PriorityQueue(); 
    int numTasks;
    cout << "Number of tasks?\n";
    cin >> numTasks;

    for(int i=0; i < numTasks; i++)
    {
        string tskName;
        int priority;
        cin >> tskName >> priority;
        tasks->push( tskName, priority );
    }

    // Let's see the new order of tasks with their priorities.
    cout << "\nOrder of tasks and their respective priority:\n";
    tasks->print();

    // Let's pop elements one by one and check the front of our Priority Queue.
    cout<<"Time to Pop:\n";
    do
    {
      cout << "Task at top: ";
      tasks->peek();
      tasks->pop();
    } while( !tasks->isEmpty() );

}

 

Input

Number of tasks?
3
Task1 3
Task2 1
Task3 2

 

Output

Order of tasks and their respective priorities:
Task2  Priority:1
Task3 Priority:2
Task1 Priority:3
Time to Pop:
Task at top: Task2
Task at top: Task3
Task at top: Task1

Key Takeaways

We understand that you worked really hard in learning about the priority queue implementation and its application to help our friend Raj. We appreciate your efforts. 

A good coder always practices what he/she learns. So head over to our practice platform CodeStudio to practice top problems and many more. CodeStudio also offers interesting interview experiences and blogs like this. So keep learning and Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think