598 views
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 _____

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.
by

@ arjun sir, is equal prority even allowed in priority queue??
What if we wanted to perform ENQUEUE(Q,40,3) , will the no. of pops be 2?

2 pops would suffice that.

Just consider implimentation of queue using two stacks.

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

1 comment

The initial stack you represented is wrong. Element with priority 6 will be at the top so that it can be dequeued in O(1) time.

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.

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.