The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
3.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

asked in DS by Veteran (59.7k points)
edited by | 3.5k views

3 Answers

+22 votes
Best answer
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.
answered by (351 points)
selected by
+4
what happens when we have keys in non-increasing order,if two elements have same priority..?
+14
Priority queue as the name suggests is used in applications where there is a need of priority. It must be absurd to to implement it in an environment where you have same priority for two things, so that case would not arise. So D) is appropriate
0

what does  DELETEMIN(Q)   means...?

+7
But priority queue can have elements with same priority.but in that case which is inserted first is deleted first which is not the case for stack hence D is the answer
0
Here lower no. represent high priority ?? is it true ?
0
It means it will always pop the minimum element from the queue.
0
it is not queue, it is priority queue,rt?
+12

See at last if we need to perform POP operation on stack, which perform same like DELETEMIN(Q) . If we choose (C) option , it will delete like 5,4,3,2,1. So, min element will not delete first.

Now, if we choose option D) it will delete like 1,2,3,4,5 as expected.

So, for that how we took element at first, i.e. decreasing order.

0
One doubt key can be 1 1 2 3 4(As there not mentioned repeated element not allowed)

So, in that case is not the answer will be A) means ans simply be non increasing order
0
@srestha ,What will be the answer A or D?

I think A should be correct.
0
why not option A , non increasing ?
+2

This is what i got from the question. Hope it helps :)

+12 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.
answered by Boss (26.1k points)
0
One doubt key can be 1 1 2 3 4(As there not mentioned repeated element not allowed)

So, in that case is not the answer will be A) means ans simply be non increasing order
0

@papesh 

@srestha

in the queue the elements are present in the following manner:-

1 | 2 | 3 | 4 | 5

now rear will point to 1 and front will point to 5, according to the rule of queue then it delete 5.

but how deletemin () is deleting the elements from rear??

0
I have drawn it in fig

If figure has any problem?
+4 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.

answered by Boss (12.5k 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 !

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,456 questions
49,912 answers
165,381 comments
65,897 users