3
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Apr 7, 2020 at 19:25
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 8, 2020 at 7:01
  • $\begingroup$ Neat! Thanks for sharing that. $\endgroup$
    – D.W.
    Apr 8, 2020 at 17:07

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ even if multiple stacks are allowed? $\endgroup$ Apr 9, 2020 at 4:53
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Apr 9, 2020 at 6:31
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Apr 9, 2020 at 16:00
  • $\begingroup$ @gnasher729, absolutely, but the poster said that the programming model doesn't allow random access, so that's not possible here. $\endgroup$
    – D.W.
    Apr 9, 2020 at 23:08
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Can you explain how to obtain such a representation? $\endgroup$ Apr 9, 2020 at 9:28
  • $\begingroup$ 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 $\endgroup$ Apr 9, 2020 at 20:34
  • $\begingroup$ 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! $\endgroup$
    – D.W.
    Apr 9, 2020 at 23:09

Your Answer

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

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