Dark Mode

4 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 _____

8 votes

Best answer

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.

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.

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

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.