How to Implement Stack Using Priority Queue or Heap?

Implement a stack with the help of a priority queue or a heap.

Priority Queue :

Priority queue data structure is similar to the queue or stack data structure with an addition of priority. Every element is given a priority number. In conclusion, the elements with high priority are prefered or served before elements with low priority.

For Instance :

priority queue = x(priority = 0), y(priority = 1), z(priority = 3). As we can see that the element z has the highest priority, therefore it will be served first.

Example

Input 

push (1)
push (2)
pop ()

Output 

2

Input 
pop ()

Output 

Empty Stack

Method

As we know that the working of the stack is based on LIFO(Last in Forst out) system and in priority queue priority is assigned to the elements. Therefore, to connect the functionality of both data structures we can maintain a variable store or count the number at which an element is being pushed. In the priority queue, this count variable can be used as the key.

Algorithm

1. Create a class stack with the priority queue. In addition to queue initialise a variable count = 0 inside it.
2. Create function push() which accepts an integer value as a parameter. Increment the count and push the pair of count and element in the priority queue.
3. Create function top() and return the element stored in top i.e. second part of the pair stored at top of the priority queue.
4. After that, create function isEmpty(). Return true if the priority queue is empty else return false.
5. Similarly, create function pop() and check if queue is empty print “Empty Stack”. Else decrement the count and pop the top of the priority queue.
6. Finally, traverse the stack and while stack is not empty print the top and pop the top.

C++ Program to implement stack using priority queue or heap

#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<<"Empty Stack!!!";
    } 
    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(1); 
    s->push(2); 
    s->push(3);
    
    while(!s->isEmpty()){ 
        cout<<s->top()<<" "; 
        s->pop(); 
    } 
}

3 2 1

Java Program to implement stack using priority queue or heap

import java.util.*;

class StackPriorityQueue{

    PriorityQueue<StackElement> queue = new PriorityQueue<>(10, new Comparator<StackElement>(){
        @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("Empty Stack");
            return null;
        }
        
        return queue.poll().value;
    }
    
    public static void main(String[] args){
        
        StackPriorityQueue q = new StackPriorityQueue();
        q.push(1);
        q.push(2);
        q.push(3);
        
        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;
    }
}

3 2 1

Complexity Analysis

Time Complexity: O(k) where k is the number of elements.

Auxiliary Space: O(k) because we used space in the priority queue for k pairs.

Reference1  reference2