Please don\'t upload images of the writing, I can\'t understand most handwriting
ID: 3803230 • Letter: P
Question
Please don't upload images of the writing, I can't understand most handwriting
Answer the following questions: a) Bill suggested that he can implement a stack ADT using a priority queue and a constant amount of additional space. Recall that a stack supports push and pop operations, and a priority queue supports remove Min and insert operations. Explain how Bill can achieve this by showing the necessary pseudo code for implementing the stack ADT. b) Referring to a) above, what are the tight big-Oh time complexities of the push and pop operations of the newly designed stack given that the priority queue is implemented using a heap? Explain your answer.Explanation / Answer
To create a stack using priority queue you need to assign priority to the elements that are being pushed.
Assigning a priority to each element that is being pushed can act as a priority key to the element. So as you know stack supports push() which inserts element atthe top and pop() which removes the top element.
So, lets create a stack with elements stored in form of map (you can use any other data structure as well).
1. Define typedef map<int,int> myMap (in this first int represents element value and secont int represents its priority.)
2. Define functions and priority queue.
int priority; ( priority acts as a key to priority queue)
priority_queue<map<int,int> > p_q;
public:
void push(int n); ()
void pop();
int top();
bool isEmpty();
};
3. Define push function which increases the priority count and inserts the count with the element value
function push(int n){
priority ++;
p_q.push(myMap(n,priority));
}
4. Define pop function which pops the top element which is by default the one one with the lowest priority as we are increasing priority value while pushing the element and reduces priority count after poping the element.
function pop(){
if(p_q.empty()){ cout<<"Nothing to pop!!!";}
priority--;
pq.pop();
}
5. return true if stack is empty
function isEmpty(){
return p_q.empty();
}
int main(){
Stack* s=new Stack();
s->push(1);
s->push(2);
s->push(3);
}
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.