Implementing an efficent priority queue using only stacks

Question

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.

Answer 1

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.

Answer 2

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.