练习 15：栈和队列

优质

小牛编辑

131浏览

2023-12-01

当处理数据结构时，你将经常遇到类似于另一种结构的结构。Stack类似于练习13中的SingleLinkedList，以及Queue类似于练习14中的DoubleLinkedList，唯一区别是Stack和Queue限制了可能的操作，以简化它们的使用方式。这有助于减少缺陷，因为你不能意外地像Queue那样使用Stack并导致问题。在Stack中，节点被“压入”“栈顶”，然后从顶部“弹出”。在队列中，节点压入“尾部”，之后从“头部”弹出。这些操作都是SingleLinkedList和DoubleLinkedList的简化，其中Stack只允许push和pop操作，Queue只允许shift和unshift。

译者注：实际上是push和unshift。

当可视化堆栈时，你应该想到你的地板上的一堆书。想像我在书架上的那种很重的艺术书，如果我堆叠了20个，可能会重约100磅。当你为这些书构建栈的时候，你不能抬起整个栈，并且把书放在底部，对吧？不，你把书放在栈的顶部。你把它放在那儿，但我们也可以使用“推”描述这个动作。如果你想从栈中获取一本书，你可能会抬起一些书，然后抓住一本书，但是最终你可能要从顶部拿出一些书，才能获取底部得数。你可以从顶部抬起每本书，或者在我们的例子中，我们会说“从顶部弹出一本书”。

如果你想像在银行排队，队列有“头部”和“尾部”，可视化队列是最简单的。通常有一个绳索迷宫，它的末尾有一个入口，出口处是检票员。你可以通过进入这条绳索迷宫的“尾部”进入队列，我们称之为shift，因为这是Queue数据结构中的常见编程属于。一旦你进入银行（队列），你不能越过等候线然后离开，否则其余的人会生气。所以你必须等待，随着你前面的每个人都离开了等候线（对你而言是unshift），你离“头部”更近了。一旦你达到了头部，那么你可以退出，我们称之为unshift。

很多时候，你可以找到数据结构的真实世界示例，来帮助你可视化其工作原理。你现在应该花点时间来绘制这些场景，或者实际上得到书籍的栈并测试这些操作。你可以找到与Stack和Queue类似的其他真实情况吗？

挑战练习

我现在打算让你做一个基于代码的挑战练习，并且从它们的描述中实现数据结构。在这个挑战中，你首先需要使用这里的起始代码，以及你从练习 13 中了解的SingleLinkedList，实现Stack数据结构。完成之后，你将尝试从零开始实现Queue数据结构。

StackNode节点类几乎和SingleLinkedListNode相同，而事实上我只是复制过来并更名：

class StackNode(object):

    def __init__(self, value, nxt):
        self.value = value
        self.next = nxt

    def __repr__(self):
        nval = self.next and self.next.value or None
        return f"[{self.value}:{repr(nval)}]"

Stack控制类和SingleLinkedList十分类似，除了我使用top代替了first。这样匹配Stack的概念。

class Stack(object):

    def __init__(self):
        self.top = None

    def push(self, obj):
        """Pushes a new value to the top of the stack."""

    def pop(self):
        """Pops the value that is currently on the top of the stack."""

    def top(self):
        """Returns a *reference* to the first item, does not remove."""

    def count(self):
        """Counts the number of elements in the stack."""

    def dump(self, mark="----"):
        """Debugging function that dumps the contents of the stack."""

现在你的挑战是实现Stack，并为其执行测试，类似于在练习 13 中进行的测试。请确保你的测试涵盖了每一个操作，你可以以任何方式。记住，尽管如此，堆栈的push操作必须在顶部，所以有到顶部的链接。

一旦你使Stack正常工作，你应该实现Queue，但它基于DoubleLinkedList。（译者注：其实单链表也行，因为只有尾部弹出的操作比较困难。你可以在尾部插入，在头部弹出。）Stack中的内容应该与SingleLinkedList基本内部结构相同，只需更改允许的功能。Queue也一样。花点时间来绘制队列的工作原理，然后弄清楚它如何限制DoubleLinkedList。一旦你完成了，创建你的队列。

破坏它

破坏这些数据结构仅仅是不要维持约束。看看如果一个操作无法使用正确的尾部会发生什么。

你可能还注意到，它有“偏移一位”的持久性错误。在我的设计中，当结构为空时，我设置了self.top = None。这意味着当你达到 0 个元素时，你必须对self.top做一些特殊处理。一个替代方法是使self.top总是指向一个StackNode（伪造的头节点），并假设当你有这个最后的元素时，结构是空的。尝试它，看看它如何改变你的实现。这样会更容易出错还是更不容易出错？

深入学习

这些数据结构有很多操作是非常低效的。回顾你为每个数据结构编写的代码，并尝试猜测哪些函数最慢。一旦你有了想法，尝试解释为什么他们可能很慢。研究其他人对这些数据结构的看法。在练习 18 和 19 中，你将学习对这些数据结构进行一些性能分析并进行调整。

最后，你真的需要实现一个全新的数据结构吗，还是简单地“包装” SingleLinkedList和DoubleLinkedList数据结构？这如何改变你的设计？