# Implementing an efficent priority queue using only stacks

Is it possible to implement an efficient priority queue (as efficient as a heap) only using the stack data structure?

The usual efficiency for a priority queue which is implemented using a heap is :

• get min - $$O(1)$$
• extract min - $$O(\log n)$$
• add - $$O(\log n)$$

Would it be possible to do something with the same complexity using only stacks?

I want to implement A* (which uses a priority queue to prioritize nodes) as a pathfinding algorithm inside Minecraft, but Minecraft doesn't allow random access, and the most efficent dynamic structure that can be implemented in it is a stack.

• Can you share the motivation for why we'd want to do that? If you encountered this somewhere, what's the context or source where you encountered this task?
– D.W.
Apr 7 '20 at 19:25
• I want to implement A* (which uses a priority queue to prioritize nodes) as a pathfinding algorithm inside Minecraft, but Minecraft doesn't allow random access, and the most efficent dynamic structure that can be implemented in it is a stack. Apr 8 '20 at 7:01
• Neat! Thanks for sharing that.
– D.W.
Apr 8 '20 at 17:07

Unfortunately, it's not possible. The order you extract items from the stack depends only on the order they're pushed, regardless of the values in those items; a priority queue needs items to be removed in an order that depends on the value of the items.

• even if multiple stacks are allowed? Apr 9 '20 at 4:53
• @CommandMaster, you need to specify the model of computation (about what computation we're allowed to do, e.g., to decide which stack to push on), but given what information you've provided so far, I expect so, yes.
– D.W.
Apr 9 '20 at 6:31
• If you have n stacks of size 1, and can use an index which stack to use, then obviously you can do anything that you can do with an array, including implementing a priority queue. Apr 9 '20 at 16:00
• @gnasher729, absolutely, but the poster said that the programming model doesn't allow random access, so that's not possible here.
– D.W.
Apr 9 '20 at 23:08

You can do such a perfect representation of priority queues using (binary) heaps data structure, using it you can implement stacks and queues...

In priority queues it's a matter of preference, not FILO principle like in stacks.

You can find all of this in Cormen et al., Introduction to Algorithms, 3rd edition.

okay, implementation of priority queues using heaps is related to the property of the heap, max_heap or min_heap so Min_priority_queue can be implemented using min_heap by using the procedures used for heaps like BUILD_HEAP() first, MAX_HEAPIFY(), INCREASE_KEY(), INSERTION and DELETION.

note that (binary)heap itself is an array object can be shown as a nearly complete binary search tree...

for stack implementation (there is psudo code)

class Stack
Inner class Element
int priority   // priority of the element.
Key element    // the element it self

MAX_PRIORITY_QUEUE<Element> queue;
next_priority = 0;

void push(Key x) // value of the pushed element
q.push(Element(next_priority++, x))

Key pop()
// as popping some element the next push must take its place
next_priority--
return queue.pop().element


To implement queue using priority queue(HEAP) the same but the priority decreases one after another.

• Can you explain how to obtain such a representation? Apr 9 '20 at 9:28
• For stacks we keep adding elements in increasing priority as when you pop some element it will return the element with largest key... as follows Apr 9 '20 at 20:34
• How do you plan to implement efficiently without arrays or random access? Can you show pseudocode? Please don't answer in the comments -- edit your answer. Thank you!
– D.W.
Apr 9 '20 at 23:09