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.

Improve this question
$\endgroup$
2
  • $\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, 2020 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, 2020 at 3:22

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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