algorithm - 仅使用一个堆栈实现优先级队列

Question

使用两个堆栈实现队列或优先级队列并不难。

现在问题是

1. 如何使用仅一个堆栈来实现优先级队列？
2. 如何使用仅一个堆栈来实现普通队列？

它们甚至可能吗？

附注当然，如果需要，你应该使用 constant 除了 ONE 堆栈之外的额外空间

Answer 1

不，不可能仅使用通过堆栈接口(interface)提供的方法(即仅使用 push 和 pop 方法)和恒定的额外空间。 ^[1]

考虑尝试使用堆栈模拟队列。

入队时，如果我们简单地压入堆栈，我们将以另一个元素结束，我们需要对其执行一些操作才能到达队列的前面以​​进行出队。很容易看出一堆入队将使下一个出队不可能占用恒定的空间量，因为所有这些入队的元素都需要被弹出才能到达队列的前面。我们也可以将入队元素从栈顶开始放置固定数量的元素，但这也没什么用——它下面的元素需要先出队，所以我们遇到了同样的问题。尝试将入队元素放置在距离堆栈顶部超过恒定数量的元素的位置当然会占用超过恒定数量的空间。

现在考虑一个优先级队列，其中每个新项目的优先级都低于队列中已有项目的优先级。这是简单队列的同义词，从上面的论点来看，不能使用具有恒定空间的单个堆栈来模拟它。

[1]:如果堆栈是作为数组或链表实现的，就像通常那样，当然可以使用这些功能，但我确定这不是您要问的。