1,010 views
5 votes
5 votes
A stack is used to implement a priority queue where $ENQUEUE(Q, x, p)$ ($p$ denotes priority, higher the better) and $DEQUE(Q)$ are implemented by appropriate PUSH and POP operations such that $DEQUE(Q)$ happens in $O(1)$. Suppose the current content of Stack is $ (1, 0), (45,1), (32,5), (100,6)$, where the second element denotes the priority. No. of POP operations required on the given stack for $ENQUEUE(Q, 2, 0)$ is _____

4 Answers

Best answer
9 votes
9 votes
Given equal priority a Priority Queue must follow FIFO structure.

In the stack, the element with highest priority must be at TOP so that DEQUEUE happens in $O(1).$ So, for $ENQUEUE(Q,2,0)$, we have to POP all elements and insert it at the bottom of stack. 4 POP operations required on the given stack.
selected by
0 votes
0 votes

Just consider implimentation of queue using two stacks.

And in case two elements have same priority,use fifo.

0 votes
0 votes

A stack is used to implement a priority queue

Means that our data structure must behave like a (priority) queue, but the internal mechanism of it is stack.

A task having higher priority would get processed first.

=> In the stack, higher the priority, closer to the top it'll be, because LIFO.

So, elements in the stack are in the order: (1,0),(45,1),(32,5),(100,6).

 

We have to insert (2,0) which has 0 priority.

If we just insert it, stack would look like: (1,0),(45,1),(32,5),(100,6),(2,0)

Then (2,0) would be processed first, which violates priorities.

 

So, we need to pop off priorities greater than 0 first. Pop 3 elements, then stack looks like.

(1,0),(45,1),(32,5),(100,6)

=> (1,0)

 

Now, contents of the stack and (2,0) have equal priority. Since our DS behaves like a queue overall... For equal priority, FIFO property of queue should hold.

=> We gotta pop (1,0) as well.

 

So, in all, we have to pop off 4 elements to push in (2,0).



This really can be solved under 30 seconds if you know the basics.

0 votes
0 votes

This is how I approach this question : 

→ stack [(100-6),(32-5),(45-1),(1-0)] from top to bottom, because with this layout dequeue can be performed in O(1).

Now we want to perform enqueue( (2,0) ), and for that, we have to pop all those elements having priority >= (2,0).

[(100-6),(32-5),(45-1),(1-0),(2-0)] result in total of 4 pop operation.

Answer:

Related questions

2 votes
2 votes
2 answers
2
0 votes
0 votes
1 answer
3
Arjun asked Oct 10, 2016
405 views
The postfix expression for the infix expression$$A + B*C/D +E$$isAB+*CD/E+ABC*D/+E+AB+C*D/E+A+*BCD/E+
0 votes
0 votes
2 answers
4
Arjun asked Oct 10, 2016
482 views
Which of the following permutation can be obtained in the output (in the same order) using a stack assuming that the input is the sequence $1, 2, 3, 4$ in that order?3, 4...