How to Implement stack using a priority queue(using min heap)?.
Asked In: Microsoft, Adobe.
In priority queue, we assign priority to the elements that are being pushed. A stack requires elements to be processed in Last in First Out manner. The idea is to associate a count that determines when it was pushed. This count works as a key for the priority queue.
So the implementation of stack uses a priority queue of pairs, with the first element serving as the key.
See Below Image to understand Better
Below is C++ implementation of the idea.
3 2 1
Now, as we can see this implementation takes O(log n) time for both push and pop operations. This can be slightly optimized by using fibonacci heap implementation of priority queue which would give us O(1) time complexity for push operation, but pop still requires O(log n) time.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.