小结

线性数据结构以有序的方式来维护其数据。
栈是简单的数据结构，其排序原则是 LIFO，即后进先出。
栈的基本操作有 push、pop 和 isEmpty。
队列是简单的数据结构，其排序原则是 FIFO，即先进先出。
队列的基本操作有 enqueue、dequeue 和 isEmpty。
表达式有 3 种写法：前序、中序和后序。
栈在计算和转换表达式的算法中十分有用。
栈具有反转特性。
队列有助于构建时序模拟。
模拟程序使用随机数生成器来模拟实际情况，并且帮助我们回答 “如果” 问题。
双端队列是栈和队列的结合。
双端队列的基本操作有 addFront、addRear、removeFront、removeRear和isEmpty。
列表是元素的集合，其中每一个元素都有一个相对于其他元素的位置。
链表保证逻辑顺序，对实际的存储顺序没有要求。
修改链表头部是一种特殊情况。

讨论题

使用 “除以2” 算法将下列值转换成二进制数。列出转换过程中的余数。
- 17
- 45
- 96
使用完全括号法，将下列中序表达式转换成前序表达式。
- (A + B) * (C + D) * (E + F)
- A + B + C) * (D + E
- A * B * C * D + E + F
使用完全括号法，将上面的中序表达式转换成后序表达式。
使用直接转换法，将上面的中序表达式转换成后序表达式。展示转换过程中栈的变化。
计算下列后序表达式。展示计算过程中栈的变化。
- 23 * 4
- 12 + 3 + 4 + 5
- 12 34 5 *+ *+
队列抽象数据类型的另一种实现方式是使用列表，并使得列表的后端是队列的尾部。这种实现的大 O 性能如何？
在链表的 add 方法中，颠倒两个步骤的执行顺序会是什么结果？引用的结果会是怎么样？会出现什么问题？
假设需要移除链表中的最后一个节点，解释如何实现 remove 方法。
假设链表只有一个节点，解释如何实现 remove 方法。

编程练习

修改从中序到后序的转换算法，使其能处理异常情况。
修改计算后序表达式的算法，使其能处理异常情况。
结合从中序到后序的转换算法以及计算后序表达式的算法，实现直接的中序计算。在计算时，应该使用两个栈从左往右处理中序表达式标记。一个栈用于保存运算符，另一个用于保存操作数。
将在练习 3 中实现的算法做成一个计算器。
使用列表实现队列抽象数据类型，将列表的后端作为队列的尾部。
设计和实现一个实验，对比两种队列实现的性能。能从该实验中学到什么？
实现一个队列，使其添加操作和移除操作的平均时间复杂度为 \$O(1)\$。这意味着在大多数情况下，两个操作的时间复杂度都是 \$O(1)\$，仅在一种特殊情况下，移除操作为 \$O(n)\$。
考虑现实生活中的一个场景。完整地定义问题，并且设计一个模拟来解答它。以下是一些例子：
- 排队等待洗车；
- 在超市等待结账；
- 飞机的起飞和降落；
- 银行出纳员。
- 请说明你所做的任何假设，并且提供所需的概率数据。
修改传土豆模拟程序，允许随机计数，从而使每一轮的结果都不可预测。
实现一个基数排序器。十进制数的基数排序利用 1 个主桶和 10 个数位桶。每个桶就像一个队列，并且根据数字到达的先后顺序来维持其中的值。该算法首先将所有的数都放在主桶中，然后按照数值中的每一个数位来考察这些值。第一个值从主桶中移除并且根据在考察的数位将其放到对应的数位桶中。如果考察的是个位，那么 534 将被放在 4 号数位桶中，667 则将被放在 7 号数位桶中。一旦所有的值都被放在了相应的数位桶中，便依次从 0 号到 9 号数位桶中将值放回主桶。重复整个过程到数字的十位、百位等。在最后一个数位被处理完之后，主桶里面就是排好序的值。
除了本章所举的例子，HTML 中也存在括号匹配问题。标签有开始和结束两种形式，并且需要互相匹配才能正确描述网页内容。下面是简单的 HTML 文档，用于展示标签的匹配和嵌套。写一个程序来检查 HTML 文档中的标签是否正确匹配。
```
<html>
    <head>
      <title>
          Example
      </title>
    </head>
    <body>
      <h1>Hello, world</h1>
    </body>
</html>
```
扩展代码清单3-15 中的回文检测器，使其可以处理包含空格的回文。如果忽略其中的空格，那么 I PREFER PI 就是回文。
本章通过计算列表中节点的个数来实现 length 方法。另一种做法是将节点个数作为额外的信息保存在列表头中。请修改 UnorderedList 类的实现，使其包含节点个数信息，并且重新实现 length 方法。
实现 remove 方法，使其能正确处理待移除元素不在列表中的情况。
修改列表类，使其能支持重复元素。这一改动会影响到哪些方法？
实现 UnorderedList 类的 __str__ 方法。列表适合用什么样的字符串来表示？
实现 __str__ 方法，使列表按照 Python 的方式来显示（使用方括号）。
实现无序列表抽象数据类型剩余的方法：append、index、pop 和 insert。
实现 UnorderedList 类的 slice 方法。该方法接受 start 和 stop 两个参数，并且返回一个从 start 位置开始，到 stop 位置结束的新列表（但不包含 stop 位置上的元素）。
实现有序列表抽象数据类型剩余的方法。
思考有序列表和无序列表的关系。能否利用继承关系来构建更高效的实现？试着实现这个继承结构。
使用链表实现栈。
使用链表实现队列。
使用链表实现双端队列。
设计和实现一个实验，比较用链表实现的列表与 Python 列表的性能。
设计和实现一个实验，比较基于 Python 列表的栈和队列与相应链表实现的性能。
由于每个节点都只有一个引用指向其后的节点，因此本章给出的链表实现称为单向链表。另一种实现称为双向链表。在这种实现中，每一个节点都有指向后一个节点的引用（通常称为 next）和指向前一个节点的引用（通常称为 back）。头引用同样也有两个引用，一个指向链表中的第一个节点，另一个指向最后一个节点。请用 Python 实现双向链表。
为队列创建一个实现，使得添加操作和移除操作的平均时间复杂度是 \$O(1)\$。