Queue: Implement priority queue using Linked List

Problem Statement:

You need to implement Priority Queue using Linked List

Priority Queue is a data structure, where in the elements will be organized on the priority of the values.

Priority is assigned from 0 to n-1 to the elements.

PQ will have the following functions:

1. push() – Insert new data

2. pop() – Removed the element of highest priority

3. peek()/top() – Used to print high priority element in the queue

Example:

Input: 10(priority = 2), 20(priority = 1), 30(priority = 0), 1(priority = 3)

Output:

30, 20, 10, 1

Time Complexity: 

push O(n)
pop O(1)
peek O(1)
Space complexity O(n)

Code Solution

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct Node 
{
    int data;
    int priority;
    Node* next;
  
    Node(int x, int p) 
    {
        data = x;
        priority = p;
        next = NULL;
    }
};

int top(Node* head) 
{

    return head->data;
}

Node* pop(Node* head) 
{

    Node* temp = head;

    head = head->next;

    delete temp;

    return head;
}

Node* push(Node* head, int d, int p) 
{
    Node* start = head;

    Node* temp = new Node(d, p);

    if (head == NULL || head->priority > p) 
    {
        temp->next = head;
        head = temp;
    }
    else 
    {

        while (start->next != NULL &&
               start->next->priority < p) 
        {
            start = start->next;
        }

        temp->next = start->next;
        start->next = temp;
    }
    return head;
}

int checkIsEmpty(Node* head) 
{
    return (head == NULL);
}

int main() 
{

    Node* pq = new Node(40, 4);

    pq = push(pq, 10, 2);
    pq = push(pq, 20, 1);
    pq = push(pq, 30, 0);
    pq = push(pq, 1, 3);

    while (!checkIsEmpty(pq)) {
        cout << " " << top(pq);
        pq = pop(pq);
    }
    return 0;
}

Output

30 20 10 1 40