Last Updated on December 14, 2022 by Prepbytes
What is a priority queue?
The priority queue is a type of queue data structure having one extra feature of giving priority to every element present in the priority queue. Elements having higher priority will be treated first than the elements with lower priority.
Stack using a priority queue
Stack works on the principle of LIFO (last in first out) and the priority queue works by assigning priority to the elements present in it. So, for implementing a stack using a priority queue, one variable will be used for maintaining the count at which an element is being pushed. This variable will work as the key for the priority queue.
Algorithm
- Initialize one variable count = 0 and create a class stack with a priority queue.
- Create a Push function that will pass an integer as an argument. Increase the value of count with 1 and push the pair of count and integer in the priority queue.
- Create a top function in the stack that will return the second part of the element which is stored at the top.
- Create an isEmpty function that will return true if the priority queue is empty, otherwise, it will return false.
- Create a Pop function that will pop the top element from the priority queue and will decrease the count value by 1. If the queue is empty then it will print “stack underflow”.
- At last, till the stack is not empty, print the top element from the stack and perform the pop operation on it.
Code Implementation
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
class Stack{
int count;
priority_queue<pair<int, int> > pq;
public:
Stack():count(0){}
void push(int n);
void pop();
int top();
bool isEmpty();
};
void Stack::push(int n){
count++;
pq.push(pi(count, n));
}
void Stack::pop(){
if(pq.empty()){
cout<<"Stack Underflow!!!";
}
count--;
pq.pop();
}
int Stack::top(){
pi temp=pq.top();
return temp.second;
}
bool Stack::isEmpty(){
return pq.empty();
}
int main(){
Stack* s=new Stack();
s->push(2);
s->push(4);
s->push(6);
while(!s->isEmpty()){
cout<<s->top()<<" ";
s->pop();
}
}
import java.util.*;
class Stack{
PriorityQueue queue = new PriorityQueue<>(10, new Comparator(){
@Override
public int compare(StackElement o1, StackElement o2) {
return o2.key - o1.key;
}
});
int order = 1;
public void push(int val){
StackElement element = new StackElement(order++,val);
queue.add(element);
}
public Integer pop(){
if(queue.isEmpty()){
System.out.println("Stack Underflow");
return null;
}
return queue.poll().value;
}
public static void main(String[] args){
Stack q = new Stack();
q.push(2);
q.push(4);
q.push(6);
System.out.print(q.pop()+" ");
System.out.print(q.pop()+" ");
System.out.print(q.pop()+" ");
}
}
class StackElement {
int key;
int value;
public StackElement(int key, int value) {
this.key = key;
this.value = value;
}
}
from queue import PriorityQueue
class Stack:
def __init__(self):
self.count = 0
self.stack = PriorityQueue()
def push(self, value):
self.count -= 1
self.stack.put([self.count, value])
def pop(self):
if self.stack.empty():
print("Stack Underflow!!")
return
self.count += 1
self.stack.get()
def top(self):
temp = self.stack.get()
self.stack.put(temp)
return temp[1]
def isEmpty(self):
return self.stack.empty()
s = Stack()
s.push(2)
s.push(4)
s.push(6)
while not s.isEmpty():
print(s.top(), end = " ")
s.pop()
Output: 6 4 2
This article tried to discuss Implementation of stack using Priority Queue or Heap. Hope this blog helps you understand the concept. To practice more problems feel free to check MYCODE | Competitive Programming at Prepbytes.