Question

Show how to implement a first-in, first-out queue with a priority queue. Also show how to implement a stack with a priority queue. Discuss the running times of each of the procedures you designed for each case.

Answer 1

First in First out using priority queue

In this we give more emphasis to the element which is being pushed. We use <int,int>(key,value)

C++ code for it ;-

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::top()

{

pi temp=pq.top();

return temp.second;

}

bool Stack::isEmpty(){

return pq.empty();

}

int main()

{

Stack* s=new Stack();

s->push(8);

s->pop(8);

while(!s->isEmpty()){

cout<<s->top()<<endl;

s->pop();

}

}

Running time is O(log n) for push and pop operation.