2,583 views
1 votes
1 votes
A priority queue  Q is used to implement a stack S that stores characters .PUSH(C) is implemented as Insert(Q,C,K)
 where K is an appropriate integer key chosen by the implementation .POP is implementd as DELETEMIN(Q) .
For a sequence of PUSH operations, the keys chosen are in which order whether strictly increasing or strictly decreasing ?

 

Firstly ,I am unable to get here that even If I attach the keys to the elements inserted in the queue with increasing order still first element which I inserted would be deleted first in any case , while this element would be at the bottom of the stack so then how will I be able to do this ?

2 Answers

Best answer
4 votes
4 votes
In a stack on a POP we want to delete the last inserted element.

So, here keys chosen are in strictly decreasing order, so that when you want to pop, and call deletemin(), it will delete element with lowest key, which is last inserted, and that is what we want.

If keys chosen are decreasing but not strictly decreasing (repetitions can come), then for keys with same values, the first inserted element will be deleted first (priority queue becomes a normal queue for keys with same values) and this is not what we want in a stack.

Related questions

0 votes
0 votes
1 answer
2
rahul sharma 5 asked Dec 17, 2016
983 views
How to implement Priority queue using stack?What will be time complexity for Enqueue and Dequeue operations?Edit:- Updated the question clearly
0 votes
0 votes
1 answer
3
radha gogia asked Jul 13, 2015
556 views
I am unable to understand the implementation of stack using queue , I understood queue implementation using stack but not this one , I searched for a video lecture too bu...
0 votes
0 votes
0 answers
4
srestha asked Dec 22, 2018
582 views
Is priority queue work efficiently with sorted array than unsorted array and heap for insertion and deletion operation? Then why do we apply priority queue in heap specia...