1
$\begingroup$

Can one build a priority queue using stacks, such that the priority queue has the same complexity for each operation. Could it be done? If so how? If not what is the best solution that can be done?

Each operation of a stack using an array is $O(1)$ whereas almost all operation of priority queue is $O(logn)$. an implementation can be done using $2D$ stacks, each elements of the stack is again a stack. When the first element of the main stack is the first element of the other stacks. The dequeue operation will take $O(n)$ as it is LIFO and the priority queue is FIFO.

$\endgroup$
  • $\begingroup$ Do you really mean that all you care about is the same complexity for every operation, without caring about how large it is? You would be happy with a solution where every operation takes $O(n)$ time? $\endgroup$ – D.W. Mar 8 '20 at 18:58
  • $\begingroup$ What is $D$? Obviously if the domain of priorities is, say, $[0,D)$, then you can use $D$ stacks/queues to implement a priority queue-like data structure, where each operation takes at most $D$ time (with a very low constant factor). This is very common in operating systems, for example, where thread/task priority is a smallish set of integers. $\endgroup$ – Pseudonym Mar 9 '20 at 3:22
2
$\begingroup$

Think about it. You can sort an array by adding all the items to a priority queue, then removing the items in sorted order.

If you could run a priority queue in constant time, you could sort in linear time. But you can't.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.