How to Implement stack using a priority queue(using min heap)?. Asked In: Microsoft, Adobe.
Solution: In priority queue, we assign priority to the elements that are being pushed. A stack requires elements to be processed in Last in First Out manner. The idea is to associate a count that determines when it was pushed. This count works as a key for the priority queue. So the implementation of stack uses a priority queue of pairs, with the first element serving as the key.
CPP
pair& lt;
int, int& gt;
(key, value)
|
See Below Image to understand Better
Below is C++ implementation of the idea.
C++
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
class Stack{
int cnt;
priority_queue<pair<int, int> > pq;
public:
Stack():cnt(0){}
void push(int n);
void pop();
int top();
bool isEmpty();
};
void Stack::push(int n){
cnt++;
pq.push(pi(cnt, n));
}
void Stack::pop(){
if(pq.empty()){ cout<<"Nothing to pop!!!";}
cnt--;
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()<<endl;
s->pop();
}
}
|
Java
import java.util.PriorityQueue;
class Stack
{
int cnt;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
public Stack() {
cnt = 0;
}
public void push(int n) {
cnt++;
pq.offer(new int[]{cnt, n});
}
public void pop() {
if (pq.isEmpty()) {
System.out.println("Nothing to pop!!!");
return;
}
cnt--;
pq.poll();
}
public int top() {
int[] temp = pq.peek();
return temp[1];
}
public boolean isEmpty() {
return pq.isEmpty();
}
public static void main(String[] args) {
Stack s = new Stack();
s.push(3);
s.push(2);
s.push(1);
while (!s.isEmpty()) {
System.out.println(s.top());
s.pop();
}
}
}
|
Python3
import heapq
class Stack:
def __init__(self):
self.cnt = 0
self.pq = []
def push(self, n):
self.cnt += 1
heapq.heappush(self.pq, (-self.cnt, n))
def pop(self):
if not self.pq:
print("Nothing to pop!!!")
self.cnt -= 1
return heapq.heappop(self.pq)[1]
def top(self):
return self.pq[0][1]
def isEmpty(self):
return not bool(self.pq)
s = Stack()
s.push(1)
s.push(2)
s.push(3)
while not s.isEmpty():
print(s.top())
s.pop()
|
C#
using System;
using System.Collections.Generic;
class Stack
{
List<int> stack = new List<int>();
public void Push(int n)
{
stack.Add(n);
}
public int Pop()
{
if (stack.Count == 0)
{
Console.WriteLine("Nothing to pop!!!");
return -1;
}
int lastIndex = stack.Count - 1;
int last = stack[lastIndex];
stack.RemoveAt(lastIndex);
return last;
}
public int Top()
{
if (stack.Count == 0)
{
Console.WriteLine("Nothing to get the top!!!");
return -1;
}
return stack[stack.Count - 1];
}
public bool IsEmpty()
{
return stack.Count == 0;
}
}
class Program
{
static void Main(string[] args)
{
Stack s = new Stack();
s.Push(1);
s.Push(2);
s.Push(3);
while (!s.IsEmpty())
{
Console.WriteLine(s.Top());
s.Pop();
}
}
}
|
Javascript
class Stack {
constructor() {
this.stack = [];
}
push(n) {
this.stack.push(n);
}
pop() {
if (this.stack.length === 0) {
console.log("Nothing to pop!!!");
}
return this.stack.pop();
}
top() {
return this.stack[this.stack.length - 1];
}
isEmpty() {
return this.stack.length === 0;
}
}
let s = new Stack();
s.push(1);
s.push(2);
s.push(3);
while (!s.isEmpty()) {
console.log(s.top());
s.pop();
}
|
Time Complexity: O(logn)
Now, as we can see this implementation takes O(log n) time for both push and pop operations. This can be slightly optimized by using fibonacci heap implementation of priority queue which would give us O(1) time complexity for push operation, but pop still requires O(log n) time.
Auxiliary Space: O(n) where n is size of priority queue
This article is contributed by Mr. Somesh Awasthi. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!