如何使用优先级队列来实现栈？ [英] How to Implement stack using priority queue?

问题描述

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

大家好，这是一个微软面试问题的软件工程师/开发。我只是不能分辨出question.So的意思我瞪大眼睛，发现这样的：

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:

栈和队列可被建模为特定种类的优先级队列。在一个堆栈，每个插入元件的优先级被单调递增;因此，插入的最后一个元素始终是第一位获得。的

那么，这个问题希望我们do.As栈（纠正我，如果我错了）的隐含实现优先级队列（优先级为单调的元素加入增加）。

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.

推荐答案

伪code：

// 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行为遵循的事实，每一个新的元素被推了优先级比当前的所有元素较高，所以它会在任何人被弹出。

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.

有两种方式，以本次采访的问题作出回应。一个是在详细解释上述的结构。二是简单地提到它，约0喃喃的东西（LG的 N 的），说你从来没有实现堆栈这种方式。

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.

这篇关于如何使用优先级队列来实现栈？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！