Implementing Stack using priority queue. | CODING INTERVIEW ARCHIVES

Implementing Stack using priority queue. | CODING INTERVIEW ARCHIVES

This question demands implementation of stack using a priority queue. Some time constraints are generally associated with this question too, I'll be discussing them later in the post.

So implementing stack using priority queue is pretty straightforward. All we need to do is think of a way to assign priority to the elements that are being pushed. A fairly obvious solution to this would be to associate with each element a count that determines when it was pushed. This count can then serve as the key for the priority queue.

So keeping this in mind our implementation of stack uses a priority queue of pairs, with the first element serving as the key. So a general element in out priority queue is of the format
            
                                     pair<int,int> (key, value)

As for comparing these values, the default comparator function works just fine, as it compares these pairs according to their first element with greater element having higher priority. This works very well for us in this case, although if we ever face a situation where this is not what we want, we can always define our own Comparator class.

Read full article from Implementing Stack using priority queue. | CODING INTERVIEW ARCHIVES