edited by
24,115 views
56 votes
56 votes

A priority queue $Q$ is used to implement a stack 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 implemented as DELETEMIN$(Q)$. For a sequence of operations, the keys chosen are in

  1. non-increasing order

  2. non-decreasing order

  3. strictly increasing order

  4. strictly decreasing order

edited by

5 Answers

Best answer
42 votes
42 votes
Implementing stack using priority queue require first element inserted in stack will be deleted at last, and to implement it using deletemin() operation of queue will require first element inserted in queue must have highest priority.

So the keys must be in strictly decreasing order.

Correct Answer: $D$
edited by
22 votes
22 votes
Here we need to implement stack .

For it last element inserted must be poped  first.

Priority Q can be implemented by min heap or max heap but here priority Q operation is given deleteMin that means in the sense of stack minimum element having the higher priority that means here we are talking about min heap .

 

Means first element of heap should be lastly inserted that means keys must be inserted in decreasing order.

Since it is priority Q and two element doesn't have same priority so strictly decreasing order.
10 votes
10 votes

option A vs option D

https://en.wikipedia.org/wiki/Priority_queue

In a stack, the priority of each inserted element is monotonically increasing; thus, the last element inserted is always the first retrieved. In a queue, the priority of each inserted element is monotonically decreasing; thus, the first element inserted is always the first retrieved.

Explanation :- A priority queue works on the bases of it's element's priority , it doesn't do operation in FIFO or LIFO manner like normal queue and stack do. Like here we defined some operation like DELETEMIN(Q) , so this abstract  data structure will help to delete minimum priority element from priority queue , noe it doesn't matter in which order the element are inserted.

like if elements are like 5,3,2,7,8 DELETEMIN(Q) will delete 2 (see no FIFO).We have to here implement stack using Priority queue (although practically it's not a good approach to implement stack using priority queue)so here element must follow LIFO mechanism. Now if elements are in strictly decreasing order we can implement stack using priority queue successfully but when elements are repeated (non-increasing order) then our priority queue will behave like a normal queue and it will follow FIFO approach but to implement stack element  have to follow LIFO approach , which won't be possible.

elements : $3_{a} , 3_{b},3_{c},3_{d}$    // all elements are same , to take care about order of insertion i named them like $3_{a} , 3_{b}$ and so on...

Here i'm taking the help of https://www.geeksforgeeks.org/implement-stack-using-priority-queue-or-heap/  

to implement stack using priority queue. the key concept is add a count to each variable which will indicate when the element was inserted (think like time)

$3_{a}$ is pushed into stack at t=1

$3_{b}$  is pushed into stack at t=2

$3_{c}$ is pushed into stack at t=3

$3_{d}$ is pushed into stack at t=4

we implement PUSH as

push_stack(data)

{

t++;

PQ.push(pair(t,data));

}

So stack is like

$3_{d}$    (t=4)
$3_{c}$    (t=3)
$3_{b}$    (t=2)
$3_{a}$    (t=1)

We implement POP as

pop_stack(data)

{

t--;

PQ.pop();

}

So we can see the first element the PQ.pop() will pop is on the bases on FIFO order and it would be $3_{a}$  but it's not what stack will pop (stack would have to follow LIFO so it would have to pop $3_{d}$)  so that's why option A would be false.

6 votes
6 votes

Funny answers here, people drawing stack diagram to explain, lol. This is a Stack implementation via a heap, that too a min-heap, you can confirm it from DELETEMIN(Q).

In min heap, the min key element will be at the root ready to be popped anytime. So, if you want to pop, you will have to make the new element that you push in as the root, because this is a stack implementation(LIFO). For that, if you will give your new element a key greater than any of the previous, it will make the element slide down in heap somewhere and if you pop, this last element in won’t be at the root. So, you’ll have to give decreasing keys.

Now, whats the harm with non-increasing, i.e allowing same keys too. Well, if you and your friend’s priority is same, he will be given chance first if he came before you, but stack doesn’t want that, stack wants you(the recently arrived) to be popped, That is why we cannot even use same keys.

I hope this helps, don’t see the stack diagrams everyones drawing, that is not the concept, concept is relating heap with the stack’s “LIFO” statement. Watch this for more clearity : 

https://www.youtube.com/watch?v=A1fc2Robnk0&ab_channel=TECHDOSE

edited by
Answer:

Related questions

28 votes
28 votes
3 answers
1
Kathleen asked Sep 29, 2014
8,541 views
Which of the following is essential for converting an infix expression to the postfix form efficiently?An operator stackAn operand stackAn operand stack and an operator s...
4 votes
4 votes
0 answers
2