Implementing Stack using priority queue. | CODING INTERVIEW ARCHIVES
This question demands implementation of stack using a priority queue. Some time constraints are generally associated with this question too, I'll be discussing them later in the post.
So implementing stack using priority queue is pretty straightforward. All we need to do is think of a way to assign priority to the elements that are being pushed. A fairly obvious solution to this would be to associate with each element a count that determines when it was pushed. This count can then serve as the key for the priority queue.
So keeping this in mind our implementation of stack uses a priority queue of pairs, with the first element serving as the key. So a general element in out priority queue is of the format
pair<int,int> (key, value)
As for comparing these values, the default comparator function works just fine, as it compares these pairs according to their first element with greater element having higher priority. This works very well for us in this case, although if we ever face a situation where this is not what we want, we can always define our own Comparator class.
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef pair<int,int> pi;
class Stack{
//cnt is used to keep track of the number of
//elements in the stack and also serves as key
//for the priority queue.
int cnt;
priority_queue<pair<int,int> > pq;
public:
Stack():cnt(0){}
void push(int n);
void pop();
int top();
bool isEmpty();
};
//push function increases cnt by 1 and
//inserts this cnt with the original value.
void Stack::push(int n){
cnt++;
pq.push(pi(cnt,n));
}
//pops element and reduces count.
void Stack::pop(){
if(pq.empty()){ cout<<"Nothing to pop!!!";}
cnt--;
pq.pop();
}
//returns the top element in the stack using
//cnt as key to determine top(highest priority),
//default comparator for pairs works fine in this case
int Stack::top(){
pi temp=pq.top();
return temp.second;
}
//return true if stack is empty
bool Stack::isEmpty(){
return pq.empty();
}
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.
Read full article from Implementing Stack using priority queue. | CODING INTERVIEW ARCHIVES
This question demands implementation of stack using a priority queue. Some time constraints are generally associated with this question too, I'll be discussing them later in the post.
So implementing stack using priority queue is pretty straightforward. All we need to do is think of a way to assign priority to the elements that are being pushed. A fairly obvious solution to this would be to associate with each element a count that determines when it was pushed. This count can then serve as the key for the priority queue.
So keeping this in mind our implementation of stack uses a priority queue of pairs, with the first element serving as the key. So a general element in out priority queue is of the format
pair<int,int> (key, value)
As for comparing these values, the default comparator function works just fine, as it compares these pairs according to their first element with greater element having higher priority. This works very well for us in this case, although if we ever face a situation where this is not what we want, we can always define our own Comparator class.
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef pair<int,int> pi;
class Stack{
//cnt is used to keep track of the number of
//elements in the stack and also serves as key
//for the priority queue.
int cnt;
priority_queue<pair<int,int> > pq;
public:
Stack():cnt(0){}
void push(int n);
void pop();
int top();
bool isEmpty();
};
//push function increases cnt by 1 and
//inserts this cnt with the original value.
void Stack::push(int n){
cnt++;
pq.push(pi(cnt,n));
}
//pops element and reduces count.
void Stack::pop(){
if(pq.empty()){ cout<<"Nothing to pop!!!";}
cnt--;
pq.pop();
}
//returns the top element in the stack using
//cnt as key to determine top(highest priority),
//default comparator for pairs works fine in this case
int Stack::top(){
pi temp=pq.top();
return temp.second;
}
//return true if stack is empty
bool Stack::isEmpty(){
return pq.empty();
}
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.
Read full article from Implementing Stack using priority queue. | CODING INTERVIEW ARCHIVES
