algorithm - 两个栈用一个双端队列，实现它的目的是什么？

Question

来自算法 4th:

1.3.48 Two stacks with a deque. Implement two stacks with a single deque so that each operation takes a constant number of deque operations (see Exercise 1.3.33).

用 1 个双端队列实现 2 个栈是什么意思？有什么实际原因吗？为什么我不直接创建 2 个堆栈？

---

1.3.49 Queue with three stacks. Implement a queue with three stacks so that each queue operation takes a constant (worst-case) number of stack operations. Warning : high degree of difficulty.

相关问题:How to implement a queue with three stacks?

此外，为什么我必须实现一个具有三个堆栈的队列？我也不能直接创建队列吗？

Answer 1

第一个问题看起来更像是一个练习，而不是其他任何问题。我怀疑在很多情况下您想要使用单个双端队列实现两个堆栈，但我很高兴被证明是错误的。不过，我认为这个问题的目的是让你思考双端队列和堆栈的“几何学”。这个问题有一个非常漂亮的解决方案，非常优雅，如果您看到它是如何工作的，它会让您更深入地了解所有这些类型的工作方式。

关于你的第二个问题——在命令式编程语言中，没有太多理由用三个堆栈来实现队列。然而，在像 Lisp 这样的函数式编程语言中，堆栈通常很容易实现，但实际上很难让队列处理每个操作所需的恒定数量的操作。事实上，有一段时间，如果我没记错的话，人们认为这根本不可能。您可以实现一个具有两个堆栈的队列(这是一个非常常见的练习，而且它实际上是一个非常好的练习，因为生成的队列非常快)，但这通常只会提供良好的摊销性能而不是好的最坏情况性能，以及在摊销不是问题或更难实现摊销的函数式语言中不一定是个好主意。从三个具有恒定复杂性的堆栈中获取一个队列是一件大事，因为它解锁了使用许多依赖于队列的经典算法的能力，否则这些算法在功能上下文中将不可用。

但同样，在这两种情况下，这些主要设计为练习，以帮助您更好地理解基础知识。你真的会在实践中做这些事情吗？可能不会——一些图书馆设计师可能会为你做这件事。但是做这些练习会让你更深入地了解这些数据类型的工作原理、它们的优缺点，以及库设计者的工作艰辛吗？是的，完全是!