使用堆栈的优先级队列

Question

可以使用堆栈构建优先级队列，使得优先级队列对每个操作具有相同的复杂性。 它可以完成吗？如果是这样的话？如果不是什么是可以完成的最佳解决方案？

使用数组的每个操作都是 $ o（1）$ ，而几乎所有优先级队列的操作是$ O（logn）$ 。 可以使用 $ 2d $ 堆栈来完成实现，堆栈的每个元素都是堆栈。 当主堆栈的第一个元素是另一堆栈的第一元素时。 dequeue操作将需要 $ o（n）$ ，因为它是LIFO，优先级队列是FIFO。

Answer 1

想想它。您可以通过将所有项目添加到优先级队列来对数组进行排序，然后以排序顺序删除项目。

如果您可以在不断的时间运行优先级队列，则可以在线性时间进行排序。但你不能。