如何使用优先级队列实现堆栈？

Question

如何使用优先级队列实现堆栈？

伙计这是一个面向软件工程师/开发人员的微软面试问题.我只是无法弄清楚问题的含义.所以我很好地发现了这个问题:

可以将堆栈和队列建模为特定类型的优先级队列.在堆栈中,每个插入元素的优先级是单调递增的; 因此,插入的最后一个元素始终是第一个检索的元素.

所以这个问题要我们做什么.作为堆栈(纠正我,如果错了)隐式实现为优先级队列(优先级随着元素的增加而单调递增).

有没有人可以弄清楚这个问题的含义.在面试中提出这类问题时我们应该做什么.

Answer 1

伪代码:

// 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的行为源于这样一个事实,即每个新元素的优先级都高于所有当前元素,因此它将在任何元素之前弹出.

有两种方法可以回答这个面试问题.一个是详细解释上面的结构.第二个是简单地提一下,嘟about一些关于O(lg n)的东西,并说你永远不会以这种方式实现堆栈.

Answer 2

如果您不知道优先级队列是什么,请询问.如果您不知道堆栈是什么,请询问.如果你不明白这个问题,请问.到目前为止,您应该能够确定需要如下所示的适配器.

Stack :
    private:
      q : MaxPriorityQueue
      counter : 0

    public:
      push(x) : q.add(x, counter++)
      pop() : q.remove()