练习 15:栈和队列

原文:Exercise 15: Stacks and Queues

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

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

译者注:实际上是pushunshift

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

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

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

挑战练习

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

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

  1. class StackNode(object):
  2. def __init__(self, value, nxt):
  3. self.value = value
  4. self.next = nxt
  5. def __repr__(self):
  6. nval = self.next and self.next.value or None
  7. return f"[{self.value}:{repr(nval)}]"

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

  1. class Stack(object):
  2. def __init__(self):
  3. self.top = None
  4. def push(self, obj):
  5. """Pushes a new value to the top of the stack."""
  6. def pop(self):
  7. """Pops the value that is currently on the top of the stack."""
  8. def top(self):
  9. """Returns a *reference* to the first item, does not remove."""
  10. def count(self):
  11. """Counts the number of elements in the stack."""
  12. def dump(self, mark="----"):
  13. """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 中,你将学习对这些数据结构进行一些性能分析并进行调整。

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