4.5k views

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

in DS
edited | 4.5k views

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$
by (351 points)
edited
0

@srestha mam i have shared with timing please check that once

0
what timing??
0

just play the video given above @srestha mam

0
I have heard this lecture.
0

there clearly mentioned

the nodes as containing the priority of the element and the element is sitting somewhere here also.

0
...
0

@srestha mam if still, your doubt is not clear then this will clear

So D is the correct option no doubt about that

CLRS Book page:163-164

0

I cannot agree with u still now.

Even see here , they are also disagree why key will be stricly decreasing https://stackoverflow.com/questions/35043596/how-to-implement-a-stack-using-a-priority-queue

(A) non-increasing order can not be true because two same (identical) numbers can not have same priority as priority should be distinguishable for each number.

So, option A) canceled.

Now ,

As given “POP is implemented as DELETEMIN(Q)” that means Stack returns minimum element always.

and  according to stack overflow,

Priority queue, maintain heap property. According to this elements must be ordered

So, elements either return max-heap or min-heap. And for this not unsorted elements will be allowed here.  And as we delete minimum element first, So, insertion of element must be decreasing order.

@Satbir

priority queue nothing but heap here.In ur diagram is it maintaining heap property??

https://www.geeksforgeeks.org/gate-gate-cs-1997-question-32/

I hope all doubt now gone for this question.

+1

@srestha,

He has given you the link to the NPTEL video, CLRS what more do you want ?

I Don't want to discuss it anymore.

0
............
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.
by Boss (25.4k points)
0

@srestha mam

they have taken first element as highest priority (front point here) it means element at rear will be lowest priority there too

0
first element inserted in queue must have highest priority. see selected answer @srestha mam
+1

tell me this

When we implement queue to implement a stack, We need atleast 2 queue.

But here we implementing with one priority queue. Now if we  insert 1,1,2,3,4  then according to stack it should remove 4,3,2,1,1

right??

Then how min delete first?? 4 will remove first according to stack.

Secondly according to ur dia, if $4$ remove first, then lowest priority element will remove first. That means priority comes in min-delete 1,2,3,4,5 , which will be an increasing order.

right??

0

@srestha mam

INSERT $(Q,C,K)$ where $K$ is an appropriate integer key chosen by the implementation.

0

@srestha mam check this insertion by decrementing key(k) and deletion by incrementing the index(key k)

0
That is not maintaining stack property then.  Because in stack which inserted last should remove first
0

@srestha yes mam diagram was wrong

0

Have u got correct diagram for it?? Though ur logic is valid I think.

0

I think priority queue implementation is nothing but 'Min-heap' implementation. So, if we insert values like 5,4,3,2,1 it always give 1,2,3,4,5 as output. right??

So, you mentioned priority separately, but that is not needed. right??

But one thing, if priority queue takes max heap as representation , then D) will not be answer. right?? So, what about max-heap??

0

@srestha

Yes mam you are right,

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.

by Boss (14.1k points)
0
which can be an appropriate text book to refer such topics of data structure?

In CLRS, its not mentioned in depth, if I am not wrong. Please someone suggest !

1
+1 vote