in DS
2,254 views
1 vote
1 vote
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 ?
in DS
2.3k views

2 Comments

Can we not have a priority queue having implemented using max Heap instead of min heap.In that case for this question priority can be given in strictly increasing order.
0
0
0
0

2 Answers

4 votes
4 votes
Best answer
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.

1 comment

Thanks Arjun for edit :)
0
0
1 vote
1 vote

Related questions