How to Implement stack using priority queue?

Question

How to Implement stack using priority queue?

Guys this is a Microsoft Interview Question for Software Engineer/Developer.I just can't make out the meaning of the question.So I goggled and found this:

Stacks and queues may be modeled as particular kinds of priority queues. In a stack, the priority of each inserted element is monotonically increasing; thus, the last element inserted is always the first retrieved.

So what this question wants us to do.As stacks (Correct me if am wrong) are implicitly implemented as priority queues (priority being monotonically increasing as elements are added).

Does anybody can make out the meaning of this question.What we are supposed to do when such type of question is asked in an interview.

Answer 1

Pseudocode:

// stack of Key
class Stack {
    class Element { int prio, Key elem; };
    MaxPriorityQueue<Element> q;
    int top_priority = 0;

    void push(Key x) { q.push(Element(top_priority++, x)); }
    Key pop() { top_priority--; return q.pop().elem; }
};

LIFO behavior follows from the fact that every new element is pushed with a priority higher than all the current elements, so it will be popped before any of them.

There are two ways to respond to this interview question. One is to explain in detail the structure above. The second is to briefly mention it, mumble something about O(lg n) and say you'd never implement a stack this way.