algorithm - 两个栈和一个deque，实现它的目的是什么？

Question

从算法 4开始：

1.3.48 两个栈和一个双端队列。使用单个双端队列实现两个堆栈，以便每个操作都采用恒定数量的双端队列操作（参见练习 1.3.33）。

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

---

1.3.49 队列与三个堆栈。实现一个具有三个堆栈的队列，以便每个队列操作采用恒定（最坏情况）数量的堆栈操作。警告：高难度。

相关问题：如何实现具有三个堆栈的队列？

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

标签： algorithmdata-structures

Answer 1

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

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

但同样，在这两种情况下，这些主要是作为练习设计的，以帮助您更好地理解基础知识。你真的会在实践中做这些事情吗？可能不会——一些图书馆设计师可能会为你做这件事。但是做这些练习会让你更深入地了解这些数据类型是如何工作的，它们擅长和不擅长的事情，以及对图书馆设计人员的努力工作的欣赏吗？是的，完全！