第3章：基本数据结构

思考并回答以下问题：

本章涵盖：

• 理解栈、队列、双端队列、列表等抽象数据类型。
• 能够使用Python列表实现栈、队列和双端队列。
• 理解基础线性数据结构的性能。
• 理解前序、中序和后序表达式。
• 使用栈来计算后序表达式。
• 使用栈将中序表达式转换成后序表达式。
• 使用队列进行基本的时序模拟。
• 理解栈、队列以及双端队列适用于解决何种问题。
• 能够使用“节点与引用”模式将列表实现为链表。
• 能够从性能方面比较自己的链表实现与Python的列表实现。

何谓线性数据结构

我们首先学习4种简单而强大的数据结构。栈、队列、双端队列和列表都是有序的数据集合，其元素的顺序取决于添加顺序或移除顺序。一旦某个元素被添加进来，它与前后元素的相对位置将保持不变。这样的数据集合经常被称为线性数据结构。

线性数据结构可以看作有两端。这两端有时候被称作“左端”和“右端”，有时候也被称作“前端”和“后端”。当然，它们还可以被称作“顶端”和“底端”。名字本身并不重要，真正区分线性数据结构的是元素的添加方式和移除方式，尤其是添加操作和移除操作发生的位置。举例来说，某个数据结构可能只允许在一端添加新元素，有些则允许从任意一端移除元素。

上述不同催生了计算机科学中最有用的一些数据结构。它们出现在众多的算法中，并且可用于解决许多重要的问题。

栈

何谓栈

栈有时也被称作“下推栈”。它是有序集合，添加操作和移除操作总发生在同一端，即“顶端”，另一端则被称为“底端”。

栈中的元素离底端越近，代表其在栈中的时间越长，因此栈的底端具有非常重要的意义。最新添加的元素将被最先移除。这种排序原则被称作LIFO（last-in first-out），即后进先出。它提供了一种基于在集合中的时间来排序的方式。最近添加的元素靠近顶端，旧元素则靠近底端。

栈的例子在日常生活中比比皆是。几乎所有咖啡馆都有一个由托盘或盘子构成的栈，你可以从顶部取走一个，下一个顾客则会取走下面的托盘或盘子。图3-1是由书构成的栈，唯一露出封面的书就是顶部的那本。为了拿到其他某本书，需要移除压在其上面的书。图3-2展示了另一个栈，它包含一些原生的Python数据对象。

图3-1 由书构成的栈

图3-2 由原生的Python数据对象构成的栈

观察元素的添加顺序和移除顺序，就能理解栈的重要思想。假设桌面一开始是空的，每次只往桌上放一本书。如此堆叠，便能构建出一个栈。取书的顺序正好与放书的顺序相反。由于可用于反转元素的排列顺序，因此栈十分重要。元素的插入顺序正好与移除顺序相反。图3-3展示了Python数据对象栈的创建过程和拆除过程。请仔细观察数据对象的顺序。

图3-3 栈的反转特性

考虑到栈的反转特性，我们可以想到在使用计算机时的一些例子。例如，每一个浏览器都有返回按钮。当我们从一个网页跳转到另一个网页时，这些网页——实际上是URL——都被存放在一个栈中。当前正在浏览的网页位于栈的顶端，最早浏览的网页则位于底端。如果点击返回按钮，便开始反向浏览这些网页。

栈抽象数据类型

栈抽象数据类型由下面的结构和操作定义。如前所述，栈是元素的有序集合，添加操作与移除操作都发生在其顶端。栈的操作顺序是LIFO，它支持以下操作。

• Stack() 创建一个空栈。它不需要参数，且会返回一个空栈。
• push(item) 将一个元素添加到栈的顶端。它需要一个参数item，且无返回值。
• pop() 将栈顶端的元素移除。它不需要参数，但会返回顶端的元素，并且修改栈的内容。
• peek() 返回栈顶端的元素，但是并不移除该元素。它不需要参数，也不会修改栈的内容。
• isEmpty() 检查栈是否为空。它不需要参数，且会返回一个布尔值。
• size() 返回栈中元素的数目。它不需要参数，且会返回一个整数。

假设s是一个新创建的空栈。表3-1展示了对s进行一系列操作的结果。在“栈内容”一列中，栈顶端的元素位于最右侧。

栈操作	栈内容	返回值
s.isEmpty()	[]	True
s.push(4)	[4]
s.push(‘dog’)	[4, ‘dog’]
s.peek()	[4, ‘dog’]	‘dog’
s.push(True)	[4, ‘dog’, True]
s.size()	[4, ‘dog’, True]	3
s.isEmpty()	[4, ‘dog’, True]	False
s.push(8.4)	[4, ‘dog’, True, 8.4]
s.pop()	[4, ‘dog’, True]	8.4
s.pop()	[4, ‘dog’]	True
s.size()	[4, ‘dog’]	2

用Python实现栈

明确定义栈抽象数据类型之后，我们开始用Python来将其实现。如前文所述，抽象数据类型的实现常被称为数据结构。

正如第1章所述，和其他面向对象编程语言一样，每当需要在Python中实现像栈这样的抽象数据类型时，就可以创建新类。栈的操作通过方法实现。更进一步地说，因为栈是元素的集合，所以完全可以利用Python提供的强大、简单的原生集合来实现。这里，我们将使用列表。

Python列表是有序集合，它提供了一整套方法。举例来说，对于列表[2, 5, 3, 6, 7, 4]，只需要考虑将它的哪一边视为栈的顶端。一旦确定了顶端，所有的操作就可以利用append和pop等列表方法来实现。

代码清单3-1是栈的实现，它假设列表的尾部是栈的顶端。当栈增长时（即进行push操作），新的元素会被添加到列表的尾部。pop操作同样会修改这一端。

代码清单3-1　用Python实现栈

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

以下展示了表3-1中的栈操作及其返回结果。

>>> s = Stack()
>>> s.isEmpty()
True
>>> s.push(4)
>>> s.push('dog')
>>> s.peek()
'dog'
>>> s.push(True)
>>> s.size()
3
>>> s.isEmpty()
False
>>> s.push(8.4)
>>> s.pop()
8.4
>>> s.pop()
True
>>> s.size()
2

值得注意的是，也可以选择将列表的头部作为栈的顶端。不过在这种情况下，便无法直接使用pop方法和append方法，而必须要用pop方法和insert方法显式地访问下标为0的元素，即列表中的第1个元素。代码清单3-2展示了这种实现。

代码清单3-2 栈的另一种实现

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.insert(0, item)

    def pop(self):
        return self.items.pop(0)

    def peek(self):
        return self.items[0]

    def size(self):
        return len(self.items)

改变抽象数据类型的实现却保留其逻辑特征，这种能力体现了抽象思想。不过，尽管上述两种实现都可行，但是二者在性能方面肯定有差异。append方法和pop()方法的时间复杂度都是$O(1)$，这意味着不论栈中有多少个元素，第一种实现中的push操作和pop操作都会在恒定的时间内完成。第二种实现的性能则受制于栈中的元素个数，这是因为insert(0)和pop(0)的时间复杂度都是$O(n)$，元素越多就越慢。显而易见，尽管两种实现在逻辑上是相等的，但是它们在进行基准测试时耗费的时间会有很大的差异。

匹配括号

接下来，我们使用栈解决实际的计算机科学问题。我们都写过如下所示的算术表达式。

(5 + 6) * (7 + 8) / (4 + 3)

其中的括号用来改变计算顺序。像Lisp这样的编程语言有如下语法结构。

(defun square(n)
     (* n n))

它定义了一个名为square的函数，该函数会返回参数n的平方值。Lisp所用括号之多，令人咋舌。

在以上两个例子中，括号都前后匹配。匹配括号是指每一个左括号都有与之对应的一个右括号，并且括号对有正确的嵌套关系。下面是正确匹配的括号串。

(()()()())

(((())))

(()((())()))

下面的这些括号则是不匹配的。

((((((())

()))

(()()(()

能够分辨括号匹配得正确与否，对于识别编程语言的结构来说非常重要。

我们的挑战就是编写一个算法，它从左到右读取一个括号串，然后判断其中的括号是否匹配。为了解决这个问题，需要注意到一个重要现象。当从左到右处理括号时，最右边的无匹配左括号必须与接下来遇到的第一个右括号相匹配，如图3-4所示。并且，在第一个位置的左括号可能要等到处理至最后一个位置的右括号时才能完成匹配。相匹配的右括号与左括号出现的顺序相反。这一规律暗示着能够运用栈来解决括号匹配问题。

图3-4　匹配括号

一旦认识到用栈来保存括号是合理的，算法编写起来就会十分容易。由一个空栈开始，从左往右依次处理括号。如果遇到左括号，便通过push操作将其加入栈中，以此表示稍后需要有一个与之匹配的右括号。反之，如果遇到右括号，就调用pop操作。只要栈中的所有左括号都能遇到与之匹配的右括号，那么整个括号串就是匹配的；如果栈中有任何一个左括号找不到与之匹配的右括号，则括号串就是不匹配的。在处理完匹配的括号串之后，栈应该是空的。代码清单3-3展示了实现这一算法的Python代码。

代码清单3-3　匹配括号

from pythonds.basic import Stack

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
         symbol = symbolString[index]
          if symbol == "(":
             s.push(symbol)
          else:
           if s.isEmpty():
               balanced = False
           else:
              s.pop()

         index = index + 1

     if balanced and s.isEmpty():
         return True
    else:
        return False

parChecker函数假设Stack类可用，并且会返回一个布尔值来表示括号串是否匹配。注意，布尔型变量balanced的初始值是True，这是因为一开始没有任何理由假设其为False。如果当前的符号是左括号，它就会被压入栈中（第9~10行）。注意第15行，仅通过pop()将一个元素从栈中移除。由于移除的元素一定是之前遇到的左括号，因此并没有用到pop()的返回值。在第19~22行，只要所有括号匹配并且栈为空，函数就会返回True，否则返回False。

普通情况：匹配符号

符号匹配是许多编程语言中的常见问题，括号匹配问题只是一个特例。匹配符号是指正确地匹配和嵌套左右对应的符号。例如，在Python中，方括号[和]用于列表；花括号{和}用于字典；括号(和)用于元组和算术表达式。只要保证左右符号匹配，就可以混用这些符号。以下符号串是匹配的，其中不仅每一个左符号都有一个右符号与之对应，而且两个符号的类型也是一致的。

{{([][])}()}

[[{{(())}}]]

[][][](){}

以下符号串则是不匹配的。

([)]

((()]))

[{()]

要处理新类型的符号，可以轻松扩展3.3.4节中的括号匹配检测器。每一个左符号都将被压入栈中，以待之后出现对应的右符号。唯一的区别在于，当出现右符号时，必须检测其类型是否与栈顶的左符号类型相匹配。如果两个符号不匹配，那么整个符号串也就不匹配。同样，如果整个符号串处理完成并且栈是空的，那么就说明所有符号正确匹配。

代码清单3-4展示了实现上述算法的Python程序。唯一的改动在第17行，我们调用了一个辅助函数来匹配符号。必须检测每一个从栈顶移除的符号是否与当前的右符号相匹配。如果不匹配，布尔型变量balanced就被设成False。

代码清单3-4　匹配符号

from pythonds.basic import Stack
    def parChecker(symbolString):
        s = Stack()

        balanced = True
        index = 0

        while index < len(symbolString) and balanced:
            symbol = symbolString[index]
            if symbol in "([{":
                s.push(symbol)
            else:
                if s.isEmpty():
                    balanced = False
                else:
                    top = s.pop()
            if not matches(top, symbol):
                balanced = False

            index = index + 1

            if balanced and s.isEmpty():
                return True
            else:
                return False
  
    def matches(open, close):
        opens = "([{"
        closers = ")]}"

        return opens.index(open) == closers.index(close)

以上两个例子说明，在处理编程语言的语法结构时，栈是十分重要的数据结构。几乎所有记法都有某种需要正确匹配和嵌套的符号。除此之外，栈在计算机科学中还有其他一些重要的应用场景，让我们继续探索。

将十进制数转换成二进制数

在学习计算机科学的过程中，我们基本上都接触过二进制数。由于所有存储在计算机中的值都是由0和1组成的字符串，因此二进制在计算机科学中非常重要。如果不能在二进制表达方式和常见表达方式之间转换，我们与计算机的交互就会非常麻烦。

整数是常见的数据项，它们在计算机程序中无处不在。我们在数学课上学习过整数，并且会用十进制或者以10为基来表示它们。十进制数233_{10} 及其对应的二进制数11101001_2可以分别按下面的形式表示。

$\begin{aligned}&2\times10^2+3\times1)^1+3\times10^0\\&1\times2^7+1\times2^6+1\times2^5+0\times2^4+1\times2^3+0\times2^2+0\times2^1+1\times2^0\end{aligned}$

如何才能简便地将整数值转换成二进制数呢？答案是利用一种叫作“除以2”的算法，该算法使用栈来保存二进制结果的每一位。

“除以2”算法假设待处理的整数大于0。它用一个简单的循环不停地将十进制数除以2，并且记录余数。第一次除以2的结果能够用于区分偶数和奇数。如果是偶数，则余数为0，因此个位上的数字为0；如果是奇数，则余数为1，因此个位上的数字为1。可以将要构建的二进制数看成一系列数字；计算出的第一个余数是最后一位。如图3-5所示，这又一次体现了反转特性，因此用栈来解决该问题是合理的。

图3-5 将十进制数转换成二进制数

代码清单3-5展示了“除以2”算法的Python实现。divideBy2函数接受一个十进制数作为参数，然后不停地将其除以2。第6行使用了内建的取余运算符%，第7行将求得的余数压入栈中。当除法过程遇到0之后，第10-12行就会构建一个二进制数字串。第10行创建一个空串。随后，二进制数字从栈中被逐个取出，并添加到数字串的最右边。最后，函数返回该二进制数字串。

代码清单3-5 “除以2”算法的Python实现

from pythonds.basic import Stack
def divideBy2(decNumber):
   remstack = Stack()

      while decNumber > 0:
                 rem = decNumber % 2
          remstack.push(rem)
          decNumber = decNumber // 2

      binString = ""
      while not remstack.isEmpty():
         binString = binString + str(remstack.pop())

     return binString

这个将十进制数转换成二进制数的算法很容易扩展成对任何进制的转换。在计算机科学中，常常使用不同编码的数字，其中最常见的是二进制、八进制和十六进制。

十进制数$233_{10}$对应的八进制数$351_8$和十六进制数${\rm E}9_{16}$可以分别按下面的形式表示。

$\begin{aligned}&3\times8^2+5\times8^1+1\times8^0\\&15\times16^1+9\times16^0\end{aligned}$

可以将divideBy2函数修改成接受一个十进制数以及希望转换的进制基数，“除以2”则变成“除以基数”。在代码清单3-6中，baseConverter函数接受一个十进制数和一个2-16的基数作为参数。处理方法仍然是将余数压入栈中，直到被处理的值为0。之前的从左到右构建数字串的方法只需要修改一处。以2-10为基数时，最多只需要10个数字，因此0-9这10个整数够用。当基数超过10时，就会遇到问题。不能再直接使用余数，这是因为余数本身就是两位的十进制数。因此，需要创建一套数字来表示大于9的余数。

一种解决方法是添加一些字母字符到数字中。例如，十六进制使用10个数字以及前6个字母来代表16位数字。在代码清单3-6中，为了实现这一方法，第3行创建了一个数字字符串来存储对应位置上的数字。0在位置0，1在位置1，A在位置10，B在位置11，依此类推。当从栈中移除一个余数时，它可以被用作访问数字的下标，对应的数字会被添加到结果中。如果从栈中移除的余数是13，那么字母D将被添加到结果字符串的最后。

代码清单3-6 将十进制数转换成任意进制数

    from pythonds.basic import Stack
def baseConverter(decNumber, base):
     digits = "0123456789ABCDEF"

     remstack = Stack()

     while decNumber > 0:
                 rem = decNumber % base
          remstack.push(rem)
        decNumber = decNumber // base

     newString = ""
      while not remstack.isEmpty():
        newString = newString + digits[remstack.pop()]

     return newString

前序、中序和后序表达式

对于像B * C这样的算术表达式，可以根据其形式来正确地运算。在B * C的例子中，由于乘号*出现在两个变量之间，因此我们知道应该用变量B乘以变量C。因为运算符出现在两个操作数的中间，所以这种表达式被称作中序表达式。

来看另一个中序表达式的例子：A + B * C。虽然运算符+和*都在操作数之间，但是存在一个问题：它们分别作用于哪些操作数？+是否作用于A和B？*是否作用于B和C？这个表达式看起来存在歧义。

事实上，我们经常读写这类表达式，并且没有遇到任何问题。这是因为，我们知道+和*的特点。每一个运算符都有一个优先级。在运算时，高优先级的运算符先于低优先级的运算符。唯一能够改变运算顺序的就是括号。乘法和除法的优先级高于加法和减法。如果两个运算符的优先级相同，那就按照从左到右或者结合性的顺序运算。

让我们从运算符优先级的角度来理解A + B * C。首先计算B C，然后再将A与该乘积相加。(A + B) \ C则是先计算A与B之和，然后再进行乘法运算。在表达式A + B + C中，根据优先级法则（或者结合性），最左边的+会首先参与运算。

尽管这些规律对于人来说显而易见，计算机却需要明确地知道以何种顺序进行何种运算。一种杜绝歧义的写法是完全括号表达式。这种表达式对每一个运算符都添加一对括号。由括号决定运算顺序，没有任何歧义，并且不必记忆任何优先级规则。

A + B * C + D可以被重写成((A + (B * C)) + D)，以表明乘法优先，然后计算左边的加法表达式。由于加法运算从左往右结合，因此A + B + C + D可以被重写成(((A + B) + C) + D)。

还有另外两种重要的表达式，也许并不能一目了然地看出它们的含义。考虑中序表达式A + B。如果把运算符放到两个操作数之前，就得到+ A B。同理，如果把运算符移到最后，会得到A B +。这两种表达式看起来有点奇怪。

通过改变运算符与操作数的相对位置，我们分别得到前序表达式和后序表达式。前序表达式要求所有的运算符出现在它所作用的两个操作数之前，后序表达式则相反。表3-2列出了一些例子。

表3-2 中序、前序与后序表达式

中序表达式	前序表达式	后序表达式
A + B	+ A B	A B +
A + B * C	+ A * B C	A B C * +

A + B * C可以被重写为前序表达式+ A * B C。乘号出现在B和C之前，代表着它的优先级高于加号。加号出现在A和乘法结果之前。

A + B * C对应的后序表达式是A B C * +。运算顺序仍然得以正确保留，这是由于乘号紧跟B和C出现，意味着它的优先级比加号更高。尽管运算符被移到了操作数的前面或者后面，但是运算顺序并没有改变。

现在来看看中序表达式(A + B) * C。括号用来保证加号的优先级高于乘号。但是，当A + B被写成前序表达式时，只需将加号移到操作数之前，即+ A B。于是，加法结果就成了乘号的第一个操作数。乘号被移到整个表达式的最前面，从而得到 * + A B C。同理，后序表达式A B +保证优先计算加法。乘法则在得到加法结果之后再计算。因此，正确的后序表达式为A B + C *。

表3-3列出了上述3个表达式。请注意一个非常重要的变化。在后两个表达式中，括号去哪里了？为什么前序表达式和后序表达式不需要括号？答案是，这两种表达式中的运算符所对应的操作数是明确的。只有中序表达式需要额外的符号来消除歧义。前序表达式和后序表达式的运算顺序完全由运算符的位置决定。鉴于此，中序表达式是最不理想的算式表达法。

表3-3 括号的变化

中序表达式	前序表达式	后序表达式
(A + B) * C	* + A B C	A B + C *

表3-4展示了更多的中序表达式及其对应的前序表达式和后序表达式。请确保自己明白对应的表达式为何在运算顺序上是等价的。

表3-4 中序、前序与后序表达式示例

中序表达式	前序表达式	后序表达式
A + B * C + D	+ + A * B C D	A B C * + D +
(A + B) * (C + D)	* + A B + C D	A B + C D + *
A B + C D	+ A B C D	A B C D +
A + B + C + D	+ + + A B C D	A B + C + D +

从中序向前序和后序转换

到目前为止，我们使用了特定的方法来将中序表达式转换成对应的前序表达式和后序表达式。正如你所想，存在通用的算法，可用于正确转换任意复杂度的表达式。

首先使用完全括号表达式。如前所述，可以将A + B * C写作(A + (B * C))，以表示乘号的优先级高于加号。进一步观察后会发现，每一对括号其实对应着一个中序表达式（包含两个操作数以及其间的运算符）。

观察子表达式(B * C)的右括号。如果将乘号移到右括号所在的位置，并且去掉左括号，就会得到B C *，这实际上是将该子表达式转换成了对应的后序表达式。如果把加号也移到对应的右括号所在的位置，并且去掉对应的左括号，就能得到完整的后序表达式，如图3-6所示。

图3-6 向右移动运算符，以得到后序表达式

如果将运算符移到左括号所在的位置，并且去掉对应的右括号，就能得到前序表达式，如图3-7所示。实际上，括号对的位置就是其包含的运算符的最终位置。

图3-6 向左移动运算符，以得到前序表达式

因此，若要将任意复杂的中序表达式转换成前序表达式或后序表达式，可以先将其写作完全括号表达式，然后将括号内的运算符移到左括号处（前序表达式）或者右括号处（后序表达式）。

下面来看一个更复杂的表达式：(A + B) * C - (D - E) * (F + G)。图3-8展示了将其转换成前序表达式和后序表达式的过程。

图3-8 将复杂的中序表达式转换成前序表达式和后序表达式

从中序到后序的通用转换法

我们需要开发一种将任意中序表达式转换成后序表达式的算法。为了完成这个目标，让我们进一步观察转换过程。

再一次研究A + B * C这个例子。如前所示，其对应的后序表达式为A B C * +。操作数A、B和C的相对位置保持不变，只有运算符改变了位置。再观察中序表达式中的运算符。从左往右看，第一个出现的运算符是+。但是在后序表达式中，由于*的优先级更高，因此*先于+出现。在本例中，中序表达式的运算符顺序与后序表达式的相反。

在转换过程中，由于运算符右边的操作数还未出现，因此需要将运算符保存在某处。同时，由于运算符有不同的优先级，因此可能需要反转它们的保存顺序。本例中的加号与乘号就是这种情况。由于中序表达式中的加号先于优先级更高的乘号出现，因此后序表达式需要反转它们的出现顺序。鉴于这种反转特性，使用栈来保存运算符就显得十分合理。

对于(A + B) * C，情况会如何呢？它对应的后序表达式为A B + C *。从左往右看，首先出现的运算符是+。不过，由于括号改变了运算符的优先级，因此当处理到*时，+已经被放入结果表达式中了。现在可以来总结转换算法：当遇到左括号时，需要将其保存，以表示接下来会遇到高优先级的运算符；那个运算符需要等到对应的右括号出现才能确定其位置（回忆一下完全括号表达式的转换法）；当右括号出现时，便可以将运算符从栈中取出来。

在从左往右扫描中序表达式时，我们利用栈来保存运算符。这样做可以提供反转特性。栈的顶端永远是最新添加的运算符。每当遇到一个新的运算符时，都需要对比它与栈中运算符的优先级。

假设中序表达式是一个以空格分隔的标记串。其中，运算符标记有*、/、+和-，括号标记有(和)，操作数标记有A、B、C等。下面的步骤会生成一个后序标记串。

(1) 创建用于保存运算符的空栈opstack，以及一个用于保存结果的空列表。

(2) 使用字符串方法split将输入的中序表达式转换成一个列表。

(3) 从左往右扫描这个标记列表。

• 如果标记是操作数，将其添加到结果列表的末尾。
• 如果标记是左括号，将其压入opstack栈中。
• 如果标记是右括号，反复从opstack栈中移除元素，直到移除对应的左括号。将从栈中取出的每一个运算符都添加到结果列表的末尾。
• 如果标记是运算符，将其压入opstack栈中。但是，在这之前，需要先从栈中取出优先级更高或相同的运算符，并将它们添加到结果列表的末尾。

(4) 当处理完输入表达式以后，检查opstack。将其中所有残留的运算符全部添加到结果列表的末尾。

图3-9展示了利用上述算法转换A * B + C * D的过程。注意，第一个*在处理至+时被移出栈。由于乘号的优先级高于加号，因此当第二个*出现时，+仍然留在栈中。在中序表达式的最后，进行了两次出栈操作，用于移除两个运算符，并将+放在后序表达式的末尾。

图3-9 将中序表达式A * B + C * D转换为后序表达式A B * C D * +

为了在Python中实现这一算法，我们使用一个叫作prec的字典来保存运算符的优先级值。该字典把每一个运算符都映射成一个整数。通过比较对应的整数，可以确定运算符的优先级（本例随意地使用了3、2、1）。左括号的优先级值最小。这样一来，任何与左括号比较的运算符都会被压入栈中。我们也将导入string模块，它包含一系列预定义变量。本例使用一个包含所有大写字母的字符串（string.ascii_uppercase）来代表所有可能出现的操作数。代码清单3-7展示了完整的转换函数。

代码清单3-7 用Python实现从中序表达式到后序表达式的转换

1.   from pythonds.basic import Stack
2.   import string
3.
4.   def infixToPostfix(infixexpr):
5.       prec = {}
6.       prec["*"] = 3
7.       prec["/"] = 3
8.       prec["+"] = 2
9.       prec["-"] = 2
10.      prec["("] = 1
11.
12.      opStack = Stack()
13.      postfixList = []
14.
15.      tokenList = infixexpr.split()
16.
17.      for token in tokenList:
18.          if token in string.ascii_uppercase:
19.              postfixList.append(token)
20.          elif token == '(':
21.              opStack.push(token)
22.          elif token == ')':
23.              topToken = opStack.pop()
24.              while topToken != '(':
25.                  postfixList.append(topToken)
26.                  topToken = opStack.pop()
27.          else:
28.              while (not opStack.isEmpty()) and \
29.                  (prec[opStack.peek()] >= prec[token]):
30.                      postfixList.append(opStack.pop())
31.              opStack.push(token)
32.
33.      while not opStack.isEmpty():
34.          postfixList.append(opStack.pop())
35.
36.      return " ".join(postfixList)

以下是一些例子的执行结果。

>>> infixtopostfix("( A + B ) * ( C + D )")
'A B + C D + *'
>>> infixtopostfix("( A + B ) * C")
'A B + C *'
>>> infixtopostfix("A + B * C")
'A B C * +'

计算后序表达式

最后一个关于栈的例子是计算后序表达式。在这个例子中，栈再一次成为适合选择的数据结构。不过，当扫描后序表达式时，需要保存操作数，而不是运算符。换一个角度来说，当遇到一个运算符时，需要用离它最近的两个操作数来计算。

为了进一步理解该算法，考虑后序表达式4 5 6 * +。当从左往右扫描该表达式时，首先会遇到操作数4和5。在遇到下一个符号之前，我们并不确定要对它们进行什么运算。将它们都保存在栈中，便可以在需要时取用。

在本例中，紧接着出现的符号又是一个操作数。因此，将6也压入栈中，并继续检查后面的符号。现在遇到运算符*，这意味着需要将最近遇到的两个操作数相乘。通过执行两次出栈操作，可以得到相应的操作数，然后进行乘法运算（本例的结果是30）。

接着，将结果压入栈中。这样一来，当遇到后面的运算符时，它就可以作为操作数。当处理完最后一个运算符之后，栈中只剩一个值。将这个值取出来，并作为表达式的结果返回。图3-10展示了栈的内容在整个计算过程中的变化。

图3-10 栈的内容在整个计算过程中的变化

图3-11展示了一个更复杂的例子：7 8 + 3 2 + /。有两处需要注意。首先，伴随着子表达式的计算，栈增大、缩小，然后再一次增大。其次，处理除法运算时需要非常小心。由于后序表达式只改变运算符的位置，因此操作数的位置与在中序表达式中的位置相同。当从栈中取出除号的操作数时，它们的顺序颠倒了。由于除号不是可交换的运算符（15/5和5/15的结果不相同），因此必须保证操作数的顺序没有颠倒。

图3-11 一个更复杂的例子

假设后序表达式是一个以空格分隔的标记串。其中，运算符标记有*、/、+和-，操作数标记是一位的整数值。结果是一个整数。

(1) 创建空栈operandStack。

(2) 使用字符串方法split将输入的后序表达式转换成一个列表。

(3) 从左往右扫描这个标记列表。

• 如果标记是操作数，将其转换成整数并且压入operandStack栈中。
• 如果标记是运算符，从operandStack栈中取出两个操作数。第一次取出右操作数，第二次取出左操作数。进行相应的算术运算，然后将运算结果压入operandStack栈中。

(4) 当处理完输入表达式时，栈中的值就是结果。将其从栈中返回。

代码清单3-8是计算后序表达式的完整函数。为了方便运算，我们定义了辅助函数doMath。它接受一个运算符和两个操作数，并进行相应的运算。

代码清单3-8 用Python实现后序表达式的计算

1.   from pythonds.basic import Stack
2.   def postfixEval(postfixExpr):
3.       operandStack = Stack()
4.
5.       tokenList = postfixExpr.split()
6.
7.       for token in tokenList:
8.           if token in "0123456789":
9.               operandStack.push(int(token))
10.          else:
11.              operand2 = operandStack.pop()
12.              operand1 = operandStack.pop()
13.              result = doMath(token, operand1, operand2)
14.              operandStack.push(result)
15.
16.      return operandStack.pop()
17.
18.  def doMath(op, op1, op2):
19.      if op  == "*":
20.          return op1 * op2
21.      elif op == "/":
22.          return op1 / op2
23.      elif op == "+":
24.          return op1 + op2
25.      else:
26.          return op1 - op2

需要注意的是，在后序表达式的转换和计算中，我们都假设输入表达式没有错误。在以上两个程序的基础上，添加错误检测和报告功能并不难。本章最后将此作为一个编程练习。

队列

接下来学习另一个线性数据结构：队列。与栈类似，队列本身十分简单，却能用来解决众多重要问题。

何谓队列

队列是有序集合，添加操作发生在“尾部”，移除操作则发生在“头部”。新元素从尾部进入队列，然后一直向前移动到头部，直到成为下一个被移除的元素。

最新添加的元素必须在队列的尾部等待，在队列中时间最长的元素则排在最前面。这种排序原则被称作FIFO（first-in first-out），即先进先出，也称先到先得。

在日常生活中，我们经常排队，这便是最简单的队列例子。进电影院要排队，在超市结账要排队，买咖啡也要排队（等着从盘子栈中取盘子）。好的队列只允许一头进，另一头出，不可能发生插队或者中途离开的情况。图3-12展示了一个由Python数据对象组成的简单队列。

图3-12 由Python数据对象组成的队列

计算机科学中也有众多的队列例子。我的计算机实验室有30台计算机，它们都与同一台打印机相连。当学生需要打印的时候，他们的打印任务会进入一个队列。该队列中的第一个任务就是即将执行的打印任务。如果一个任务排在队列的最后面，那么它必须等到前面的任务都执行完毕后才能执行。我们稍后会更深入地探讨这个有趣的例子。

操作系统使用一些队列来控制计算机进程。调度机制往往基于一个队列算法，其目标是尽可能快地执行程序，同时服务尽可能多的用户。在打字时，我们有时会发现字符出现的速度比击键速度慢。这是由于计算机正在做其他的工作。击键操作被放入一个类似于队列的缓冲区，以便对应的字符按正确的顺序显示。

队列抽象数据类型

队列抽象数据类型由下面的结构和操作定义。如前所述，队列是元素的有序集合，添加操作发生在其尾部，移除操作则发生在头部。队列的操作顺序是FIFO，它支持以下操作。

• Queue() 创建一个空队列。它不需要参数，且会返回一个空队列。
• enqueue(item) 在队列的尾部添加一个元素。它需要一个元素作为参数，不返回任何值。
• dequeue() 从队列的头部移除一个元素。它不需要参数，且会返回一个元素，并修改队列的内容。
• isEmpty() 检查队列是否为空。它不需要参数，且会返回一个布尔值。
• size() 返回队列中元素的数目。它不需要参数，且会返回一个整数。

假设q是一个新创建的空队列。表3-5展示了对q进行一系列操作的结果。在“队列内容”一列中，队列的头部位于右端。4是第一个被添加到队列中的元素，因此它也是第一个被移除的元素。

表3-5 队列操作示例

队列操作	队列内容	返回值
q.isEmpty()	[]	True
q.enqueue(4)	[4]
q.enqueue(‘dog’)	[‘dog’, 4]
q.enqueue(True)	[True, ‘dog’, 4]
q.size()	[True, ‘dog’, 4]	3
q.isEmpty()	[True, ‘dog’, 4]	False
q.enqueue(8.4)	[8.4, True, ‘dog’, 4]
q.dequeue()	[8.4, True, ‘dog’]	4
q.dequeue()	[8.4, True]	‘dog’
q.size()	[8.4, True]	2

Python实现队列

创建一个新类来实现队列抽象数据类型是十分合理的。像之前一样，我们利用简洁强大的列表来实现队列。

需要确定列表的哪一端是队列的尾部，哪一端是头部。代码清单3-9中的实现假设队列的尾部在列表的位置0处。如此一来，便可以使用insert函数向队列的尾部添加新元素。pop则可用于移除队列头部的元素（列表中的最后一个元素）。这意味着添加操作的时间复杂度是O(n)，移除操作则是O(1)。

代码清单3-9 用Python实现队列

1.   class Queue:
2.       def __init__(self):
3.           self.items = []
4.
5.       def isEmpty(self):
6.           return self.items == []
7.
8.       def enqueue(self, item):
9.           self.items.insert(0, item)
10.
11.      def dequeue(self):
12.          return self.items.pop()
13.
14.      def size(self):
15.          return len(self.items)
``` 

以下展示了表3-5中的队列操作及其返回结果。

```bash
>>> q = Queue()
>>> q.isEmpty()
True
>>> q.enqueue('dog')
>>> q.enqueue(4)
>>> q = Queue()
>>> q.isEmpty()
True
>>> q.enqueue(4)
>>> q.enqueue('dog')
>>> q.enqueue(True)
>>> q.size()
3
>>> q.isEmpty()
False
>>> q.enqueue(8.4)
>>> q.dequeue()
4
>>> q.dequeue()
'dog'
>>> q.size()
2

模拟：传土豆

展示队列用法的一个典型方法是模拟需要以FIFO方式管理数据的真实场景。考虑这样一个儿童游戏：传土豆。在这个游戏中，孩子们围成一圈，并依次尽可能快地传递一个土豆，如图3-13所示。在某个时刻，大家停止传递，此时手里有土豆的孩子就得退出游戏。重复上述过程，直到只剩下一个孩子。

图3-13 六人传土豆游戏

这个游戏其实等价于著名的约瑟夫斯问题。弗拉维奥·约瑟夫斯是公元1世纪著名的历史学家。相传，约瑟夫斯当年和39个战友在山洞中对抗罗马军队。眼看着即将失败，他们决定舍生取义。于是，他们围成一圈，从某个人开始，按顺时针方向杀掉第7人。约瑟夫斯同时也是卓有成就的数学家。据说，他立刻找到了自己应该站的位置，从而使自己活到了最后。当只剩下他时，约瑟夫斯加入了罗马军队，而不是自杀。这个故事有很多版本，有的说是每隔两个人，有的说最后一个人可以骑马逃跑。不管如何，问题都是一样的。

我们将针对传土豆游戏实现通用的模拟程序。该程序接受一个名字列表和一个用于计数的常量num，并且返回最后一人的名字。至于这个人之后如何，就由你来决定吧。

我们使用队列来模拟一个环，如图3-14所示。假设握着土豆的孩子位于队列的头部。在模拟传土豆的过程中，程序将这个孩子的名字移出队列，然后立刻将其插入队列的尾部。随后，这个孩子会一直等待，直到再次到达队列的头部。在出列和入列num次之后，此时位于队列头部的孩子出局，新一轮游戏开始。如此反复，直到队列中只剩下一个名字（队列的大小为1）。

图3-14 使用队列模拟传土豆游戏

代码清单3-10展示了对应的程序。

代码清单3-10 传土豆模拟程序

1.   from pythonds.basic import Queue
2.   def hotPotato(namelist, num):
3.       simqueue = Queue()
4.       for name in namelist:
5.           simqueue.enqueue(name)
6.
7.       while simqueue.size() > 1:
8.           for i in range(num):
9.               simqueue.enqueue(simqueue.dequeue())
10.
11.          simqueue.dequeue()
12.
13.      return simqueue.dequeue()

调用hotPotato函数，使用7作为计数常量，将得到以下结果。

>>> hotPotato(["Bill", "David", "Susan", "Jane", "Kent", "Brad"], 7)
'Susan'

注意，在上例中，计数常量大于列表中的名字个数。这不会造成问题，因为队列模拟了一个环。同时需要注意，当名字列表载入队列时，列表中的第一个名字出现在队列的头部。在上例中，Bill是列表中的第一个元素，因此处在队列的最前端。

在章末的编程练习中，你将修改这一实现，使程序允许随机计数。

模拟：打印任务

一个更有趣的例子是模拟前文提到的打印任务队列。学生向共享打印机发送打印请求，这些打印任务被存在一个队列中，并且按照先到先得的顺序执行。这样的设定可能导致很多问题。其中最重要的是，打印机能否处理一定量的工作。如果不能，学生可能会由于等待过长时间而错过要上的课。

考虑计算机科学实验室里的这样一个场景：在任何给定的一小时内，实验室里都有约10个学生。他们在这一小时内最多打印2次，并且打印的页数从1到20不等。实验室的打印机比较老旧，每分钟只能以低质量打印10页。可以将打印质量调高，但是这样做会导致打印机每分钟只能打印5页。降低打印速度可能导致学生等待过长时间。那么，应该如何设置打印速度呢？

可以通过构建一个实验室模型来解决该问题。我们需要为学生、打印任务和打印机构建对象，如图3-15所示。当学生提交打印任务时，我们需要将它们加入等待列表中，该列表是打印机上的打印任务队列。当打印机执行完一个任务后，它会检查该队列，看看其中是否还有需要处理的任务。我们感兴趣的是学生平均需要等待多久才能拿到打印好的文章。这个时间等于打印任务在队列中的平均等待时间。

图3-15 模拟打印任务队列

在模拟时，需要应用一些概率学知识。举例来说，学生打印的文章可能有1-20页。如果各页数出现的概率相等，那么打印任务的实际时长可以通过1-20的一个随机数来模拟。

如果实验室里有10个学生，并且在一小时内每个人都打印两次，那么每小时平均就有20个打印任务。在任意一秒，创建一个打印任务的概率是多少？回答这个问题需要考虑任务与时间的比值。每小时20个任务相当于每180秒1个任务。

可以通过1-180的一个随机数来模拟每秒内产生打印任务的概率。如果随机数正好是180，那么就认为有一个打印任务被创建。注意，可能会出现多个任务接连被创建的情况，也可能很长一段时间内都没有任务。这就是模拟的本质。我们希望在常用参数已知的情况下尽可能准确地模拟。

主要模拟步骤

下面是主要的模拟步骤。

(1) 创建一个打印任务队列。每一个任务到来时都会有一个时间戳。一开始，队列是空的。

(2) 针对每一秒（currentSecond），执行以下操作。

是否有新创建的打印任务？如果是，以currentSecond作为其时间戳并将该任务加入到队列中。
如果打印机空闲，并且有正在等待执行的任务，执行以下操作：
从队列中取出第一个任务并提交给打印机；
用currentSecond减去该任务的时间戳，以此计算其等待时间；
将该任务的等待时间存入一个列表，以备后用；
根据该任务的页数，计算执行时间。
打印机进行一秒的打印，同时从该任务的执行时间中减去一秒。
如果打印任务执行完毕，或者说任务需要的时间减为0，则说明打印机回到空闲状态。

(3) 当模拟完成之后，根据等待时间列表中的值计算平均等待时间。

Python实现

我们创建3个类：Printer、Task和PrintQueue。它们分别模拟打印机、打印任务和队列。

Printer类（代码清单3-11）需要检查当前是否有待完成的任务。如果有，那么打印机就处于工作状态（第13-17行），并且其工作所需的时间可以通过要打印的页数来计算。其构造方法会初始化打印速度，即每分钟打印多少页。tick方法会减量计时，并且在执行完任务之后将打印机设置成空闲状态（第11行）。

代码清单3-11　Printer类

1.   class Printer:
2.       def __init__(self, ppm):
3.           self.pagerate = ppm
4.           self.currentTask = None
5.           self.timeRemaining = 0
6.
7.       def tick(self):
8.           if self.currentTask != None:
9.               self.timeRemaining = self.timeRemaining - 1
10.              if self.timeRemaining <= 0:
11.                  self.currentTask = None
12.
13.      def busy(self):
14.          if self.currentTask != None:
15.              return True
16.          else:
17.              return False
18.
19.      def startNext(self, newtask):
20.          self.currentTask = newtask
21.          self.timeRemaining = newtask.getPages() \
22.                               * 60/self.pagerate

Task类（代码清单3-12）代表单个打印任务。当任务被创建时，随机数生成器会随机提供页数，取值范围是1~20。我们使用random模块中的randrange函数来生成随机数。

>>> import random
>>> random.randrange(1, 21)
18
>>> random.randrange(1, 21)
8

代码清单3-12　Task类

1.   import random
2.   class Task:
3.       def __init__(self, time):
4.           self.timestamp = time
5.           self.pages = random.randrange(1, 21)
6.
7.       def getStamp(self):
8.           return self.timestamp
9.
10.      def getPages(self):
11.          return self.pages
12.
13.      def waitTime(self, currenttime):
14.          return currenttime - self.timestamp

每一个任务都需要保存一个时间戳，用于计算等待时间。这个时间戳代表任务被创建并放入打印任务队列的时间。waitTime方法可以获得任务在队列中等待的时间。

主模拟程序（代码清单3-13）实现了之前描述的算法。printQueue对象是队列抽象数据类型的实例。布尔辅助函数newPrintTask判断是否有新创建的打印任务。我们再一次使用random模块中的randrange函数来生成随机数，不过这一次的取值范围是1-180。平均每180秒有一个打印任务。通过从随机数中选取180（第34行），可以模拟这个随机事件。该模拟程序允许设置总时间和打印机每分钟打印多少页。

代码清单3-13 打印任务模拟程序

1.   from pythonds.basic import Queue
2.
3.   import random
4.
5.   def simulation(numSeconds, pagesPerMinute):
6.
7.       labprinter = Printer(pagesPerMinute)
8.       printQueue = Queue()
9.       waitingtimes = []
10.
11.      for currentSecond in range(numSeconds):
12.
13.          if newPrintTask():
14.             task = Task(currentSecond)
15.             printQueue.enqueue(task)
16.
17.          if (not labprinter.busy()) and \
18.                      (not printQueue.isEmpty()):
19.              nexttask = printQueue.dequeue()
20.              waitingtimes.append( \
21.                      nexttask.waitTime(currentSecond))
22.              labprinter.startNext(nexttask)
23.
24.          labprinter.tick()
25.
26.      averageWait=sum(waitingtimes)/len(waitingtimes)
27.      print("Average Wait %6.2f secs %3d tasks remaining."\
28.                      %(averageWait, printQueue.size()))
29.
30.
31.
32.  def newPrintTask():
33.      num = random.randrange(1, 181)
34.      if num == 180:
35.          return True
36.      else:
37.          return False

每次模拟的结果不一定相同。对此，我们不需要在意。这是由于随机数的本质导致的。我们感兴趣的是当参数改变时结果出现的趋势。下面是一些结果。

>>>for i in range(10):
      simulation(3600, 5)

Average Wait 165.38 secs 2 tasks remaining.
Average Wait  95.07 secs 1 tasks remaining.
Average Wait  65.05 secs 2 tasks remaining.
Average Wait  99.74 secs 1 tasks remaining.
Average Wait  17.27 secs 0 tasks remaining.
Average Wait 239.61 secs 5 tasks remaining.
Average Wait  75.11 secs 1 tasks remaining.
Average Wait  48.33 secs 0 tasks remaining.
Average Wait  39.31 secs 3 tasks remaining.
Average Wait 376.05 secs 1 tasks remaining.

首先，模拟60分钟（3600秒）内打印速度为每分钟5页。并且，我们进行10次这样的模拟。由于模拟中使用了随机数，因此每次返回的结果都不同。

在模拟10次之后，可以看到平均等待时间是122.092秒，并且等待时间的差异较大，从最短的17.27秒到最长的376.05秒。此外，只有2次在给定时间内完成了所有任务。

现在把打印速度改成每分钟10页，然后再模拟10次。由于加快了打印速度，因此我们希望一小时内能完成更多打印任务。

>>>for i in range(10):
      simulation(3600, 10)

Average Wait   1.29 secs 0 tasks remaining.
Average Wait   7.00 secs 0 tasks remaining.
Average Wait  28.96 secs 1 tasks remaining.
Average Wait  13.55 secs 0 tasks remaining.
Average Wait  12.67 secs 0 tasks remaining.
Average Wait   6.46 secs 0 tasks remaining.
Average Wait  22.33 secs 0 tasks remaining.
Average Wait  12.39 secs 0 tasks remaining.
Average Wait   7.27 secs 0 tasks remaining.
Average Wait  18.17 secs 0 tasks remaining.

讨论

在之前的内容中，我们试图解答这样一个问题：如果提高打印质量并降低打印速度，打印机能否及时完成所有任务？我们编写了一个程序来模拟随机提交的打印任务，待打印的页数也是随机的。

上面的输出结果显示，按每分钟5页的打印速度，任务的等待时间在17.27秒和376.05秒之间，相差约6分钟。提高打印速度之后，等待时间在1.29秒和28.96秒之间。此外，在每分钟5页的速度下，10次模拟中有8次没有按时完成所有任务。

可见，降低打印速度以提高打印质量，并不是明智的做法。学生不能等待太长时间，当他们要赶去上课时尤其如此。6分钟的等待时间实在是太长了。

这种模拟分析能帮助我们回答很多“如果”问题。只需改变参数，就可以模拟感兴趣的任意行为。以下是几个例子。

如果实验室里的学生增加到20个，会怎么样？
如果是周六，学生不需要上课，他们是否愿意等待？
如果每个任务的页数变少了，会怎么样？（因为Python既强大又简洁，所以学生不必写太多行代码。）
这些问题都能通过修改本例中的模拟程序来解答。但是，模拟的准确度取决于它所基于的假设和参数。真实的打印任务数量和学生数目是准确构建模拟程序必不可缺的数据。

3.5　双端队列
接下来学习另一个线性数据结构。与栈和队列不同的是，双端队列的限制很少。注意，不要把它的英文名deque（与deck同音）和队列的移除操作dequeue搞混了。

3.5.1　何谓双端队列
双端队列是与队列类似的有序集合。它有一前、一后两端，元素在其中保持自己的位置。与队列不同的是，双端队列对在哪一端添加和移除元素没有任何限制。新元素既可以被添加到前端，也可以被添加到后端。同理，已有的元素也能从任意一端移除。某种意义上，双端队列是栈和队列的结合。图3-16展示了由Python数据对象组成的双端队列。

图3-16　由Python数据对象组成的双端队列

值得注意的是，尽管双端队列有栈和队列的很多特性，但是它并不要求按照这两种数据结构分别规定的LIFO原则和FIFO原则操作元素。具体的排序原则取决于其使用者。

3.5.2　双端队列抽象数据类型
双端队列抽象数据类型由下面的结构和操作定义。如前所述，双端队列是元素的有序集合，其任何一端都允许添加或移除元素。双端队列支持以下操作。

Deque()创建一个空的双端队列。它不需要参数，且会返回一个空的双端队列。
addFront(item)将一个元素添加到双端队列的前端。它接受一个元素作为参数，没有返回值。
addRear(item)将一个元素添加到双端队列的后端。它接受一个元素作为参数，没有返回值。
removeFront()从双端队列的前端移除一个元素。它不需要参数，且会返回一个元素，并修改双端队列的内容。
removeRear()从双端队列的后端移除一个元素。它不需要参数，且会返回一个元素，并修改双端队列的内容。
isEmpty()检查双端队列是否为空。它不需要参数，且会返回一个布尔值。
size()返回双端队列中元素的数目。它不需要参数，且会返回一个整数。
假设d是一个新创建的空双端队列，表3-6展示了对d进行一系列操作的结果。注意，前端在列表的右端。记住前端和后端的位置可以防止混淆。

表3-6　双端队列操作示例

双端队列操作

双端队列内容

返回值

d.isEmpty()

[]

True

d.addRear(4)

[4]

d.addRear(‘dog’)

[‘dog’, 4]

d.addFront(‘cat’)

[‘dog’, 4, ‘cat’]

d.addFront(True)

[‘dog’, 4, ‘cat’, True]

d.size()

[‘dog’, 4, ‘cat’, True]

4

d.isEmpty()

[‘dog’, 4, ‘cat’, True]

False

d.addRear(8.4)

[8.4, ‘dog’, 4, ‘cat’, True]

d.removeRear()

[‘dog’, 4, ‘cat’, True]

8.4

d.removeFront()

[‘dog’, 4, ‘cat’]

True

3.5.3　用Python实现双端队列
和前几节一样，我们通过创建一个新类来实现双端队列抽象数据类型。Python列表再一次提供了很多简便的方法来帮助我们构建双端队列。在代码清单3-14中，我们假设双端队列的后端是列表的位置0处。

代码清单3-14　用Python实现双端队列

1. class Deque:
2. def init(self):
3. self.items = []
   4.
4. def isEmpty(self):
5. return self.items == []
   7.
6. def addFront(self, item):
7. self.items.append(item)
   10.
8. def addRear(self, item):
9. self.items.insert(0, item)
   13.
10. def removeFront(self):
11. return self.items.pop()
    16.
12. def removeRear(self):
13. return self.items.pop(0)
    19.
14. def size(self):
15. return len(self.items)
    removeFront使用pop方法移除列表中的最后一个元素，removeRear则使用pop(0)方法移除列表中的第一个元素。同理，之所以addRear使用insert方法，是因为append方法只能在列表的最后添加元素。

以下展示了表3-6中的双端队列操作及其返回结果。

d = Deque()
d.isEmpty()
True
d.addRear(4)
d.addRear(‘dog’)
d.addFront(‘cat’)
d.addFront(True)
d.size()
4
d.isEmpty()
False
d.addRear(8.4)
d.removeRear()
8.4
d.removeFront()
True
实现双端队列的Python代码与实现栈和队列的有许多相似之处。在双端队列的Python实现中，在前端进行的添加操作和移除操作的时间复杂度是O(1)，在后端的则是O(n)。考虑到实现时采用的操作，这不难理解。再次强调，记住前后端的位置非常重要。

3.5.4　回文检测器
运用双端队列可以解决一个非常有趣的经典问题：回文问题。回文是指从前往后读和从后往前读都一样的字符串，例如radar、toot，以及madam。我们将构建一个程序，它接受一个字符串并且检测其是否为回文。

该问题的解决方案是使用一个双端队列来存储字符串中的字符。按从左往右的顺序将字符串中的字符添加到双端队列的后端。此时，该双端队列类似于一个普通的队列。然而，可以利用双端队列的双重性，其前端是字符串的第一个字符，后端是字符串的最后一个字符，如图3-17所示。

图3-17　双端队列示例

由于可以从前后两端移除元素，因此我们能够比较两个元素，并且只有在二者相等时才继续。如果一直匹配第一个和最后一个元素，最终会处理完所有的字符（如果字符数是偶数），或者剩下只有一个元素的双端队列（如果字符数是奇数）。任意一种结果都表明输入字符串是回文。代码清单3-15展示了完整的回文检测程序。

代码清单3-15　用Python实现回文检测器

1. from pythonds.basic import Deque
2. def palchecker(aString):
3. chardeque = Deque()
   4.
4. for ch in aString:
5. chardeque.addRear(ch)
   7.
6. stillEqual = True
   9.
7. while chardeque.size() > 1 and stillEqual:
8. first = chardeque.removeFront()
9. last = chardeque.removeRear()
10. if first != last:
11. stillEqual = False
    15.
12. return stillEqual
    调用palchecker函数的示例如下所示。

palchecker(“lsdkjfskf”)
False
palchecker(“toot”)
True
3.6　列表
本章使用了Python列表来实现其他抽象数据类型。列表是简洁而强大的元素集合，它为程序员提供了很多操作。但是，并非所有编程语言都有列表。对于不提供列表的编程语言，程序员必须自己动手实现。

列表是元素的集合，其中每一个元素都有一个相对于其他元素的位置。更具体地说，这种列表称为无序列表。可以认为列表有第一个元素、第二个元素、第三个元素，等等；也可以称第一个元素为列表的起点，称最后一个元素为列表的终点。为简单起见，我们假设列表中没有重复元素。

假设54, 26, 93, 17, 77, 31是考试分数的无序列表。注意，列表通常使用逗号作为分隔符。这个列表在Python中显示为[54, 26, 93, 17, 77, 31]。

3.6.1　无序列表抽象数据类型
如前所述，无序列表是元素的集合，其中每一个元素都有一个相对于其他元素的位置。以下是无序列表支持的操作。

List()创建一个空列表。它不需要参数，且会返回一个空列表。
add(item)假设元素item之前不在列表中，并向其中添加item。它接受一个元素作为参数，无返回值。
remove(item)假设元素item已经在列表中，并从其中移除item。它接受一个元素作为参数，并且修改列表。
search(item)在列表中搜索元素item。它接受一个元素作为参数，并且返回布尔值。
isEmpty()检查列表是否为空。它不需要参数，并且返回布尔值。
length()返回列表中元素的个数。它不需要参数，并且返回一个整数。
append(item)假设元素item之前不在列表中，并在列表的最后位置添加item。它接受一个元素作为参数，无返回值。
index(item)假设元素item已经在列表中，并返回该元素在列表中的位置。它接受一个元素作为参数，并且返回该元素的下标。
insert(pos, item)假设元素item之前不在列表中，同时假设pos是合理的值，并在位置pos处添加元素item。它接受两个参数，无返回值。
pop()假设列表不为空，并移除列表中的最后一个元素。它不需要参数，且会返回一个元素。
pop(pos)假设在指定位置pos存在元素，并移除该位置上的元素。它接受位置参数，且会返回一个元素。
3.6.2　实现无序列表：链表
为了实现无序列表，我们要构建链表。无序列表需要维持元素之间的相对位置，但是并不需要在连续的内存空间中维护这些位置信息。以图3-18中的元素集合为例，这些元素的位置看上去都是随机的。如果可以为每一个元素维护一份信息，即下一个元素的位置（如图3-19所示），那么这些元素的相对位置就能通过指向下一个元素的链接来表示。

图3-18　看似随意摆放的元素

图3-19　通过链接维护相对位置信息

需要注意的是，必须指明列表中第一个元素的位置。一旦知道第一个元素的位置，就能根据其中的链接信息访问第二个元素，接着访问第三个元素，依此类推。指向链表第一个元素的引用被称作头。最后一个元素需要知道自己没有下一个元素。

Node类

节点（node）是构建链表的基本数据结构。每一个节点对象都必须持有至少两份信息。首先，节点必须包含列表元素，我们称之为节点的数据变量。其次，节点必须保存指向下一个节点的引用。代码清单3-16展示了Node类的Python实现。在构建节点时，需要为其提供初始值。执行下面的赋值语句会生成一个包含数据值93的节点对象，如图3-20所示。需要注意的是，一般会像图3-21所示的那样表示节点。Node类也包含访问和修改数据的方法，以及指向下一个元素的引用。

temp = Node(93)
temp.getData()
93

图3-20　节点对象包含元素及指向下一个节点的引用

图3-21　节点的常见表示法

特殊的Python引用值None在Node类以及之后的链表中起到了重要的作用。指向None的引用代表着后面没有元素。注意，Node的构造方法将next的初始值设为None。由于这有时被称为“将节点接地”，因此我们使用接地符号来代表指向None的引用。将None作为next的初始值是不错的做法。

代码清单3-16　Node类

1. class Node:
2. def init(self, initdata):
3. self.data = initdata
4. self.next = None
   5.
5. def getData(self):
6. return self.data
   8.
7. def getNext(self):
8. return self.next
   11.
9. def setData(self, newdata):
10. self.data = newdata
    14.
11. def setNext(self, newnext):
12. self.next = newnext
    UnorderedList类

如前所述，无序列表（unordered list）是基于节点集合来构建的，每一个节点都通过显式的引用指向下一个节点。只要知道第一个节点的位置（第一个节点包含第一个元素），其后的每一个元素都能通过下一个引用找到。因此，UnorderedList类必须包含指向第一个节点的引用。代码清单3-17展示了UnorderedList类的构造方法。注意，每一个列表对象都保存了指向列表头部的引用。

代码清单3-17　UnorderedList类的构造方法

1. class UnorderedList:
2. def init(self):
3. self.head = None
   最开始构建列表时，其中没有元素。赋值语句mylist = UnorderedList()将创建如图3-22所示的链表。与在Node类中一样，特殊引用值None用于表明列表的头部没有指向任何节点。最终，前面给出的样例列表将由如图3-23所示的链表来表示。列表的头部指向包含列表第一个元素的节点。这个节点包含指向下一个节点（元素）的引用，依此类推。非常重要的一点是，列表类本身并不包含任何节点对象，而只有指向整个链表结构中第一个节点的引用。

图3-22　空列表

图3-23　由整数组成的链表

在代码清单3-18中，isEmpty方法检查列表的头部是否为指向None的引用。布尔表达式self.head == None当且仅当链表中没有节点时才为真。由于新的链表是空的，因此构造方法必须和检查是否为空的方法保持一致。这体现了使用None表示链表末尾的好处。在Python中，None可以和任何引用进行比较。如果两个引用都指向同一个对象，那么它们就是相等的。我们将在后面的方法中经常使用这一特性。

代码清单3-18　isEmpty方法

1. def isEmpty(self):
2. return self.head == None
   为了将元素添加到列表中，需要实现add方法。但在实现之前，需要解决一个重要问题：新元素要被放在链表的哪个位置？由于本例中的列表是无序的，因此新元素相对于已有元素的位置并不重要。新的元素可以在任意位置。因此，将新元素放在最简便的位置是最合理的选择。

由于链表只提供一个入口（头部），因此其他所有节点都只能通过第一个节点以及next链接来访问。这意味着添加新节点最简便的位置就是头部，或者说链表的起点。我们把新元素作为列表的第一个元素，并且把已有的元素链接到该元素的后面。

通过多次调用add方法，可以构建出如图3-23所示的链表。

mylist.add(31)
mylist.add(77)
mylist.add(17)
mylist.add(93)
mylist.add(26)
mylist.add(54)
注意，由于31是第一个被加入列表的元素，因此随着后续元素不断被加入列表，它最终成了最后一个元素。同理，由于54是最后一个被添加的元素，因此它成为链表中第一个节点的数据值。

代码清单3-19展示了add方法的实现。列表中的每一个元素都必须被存放在一个节点对象中。第2行创建一个新节点，并且将元素作为其数据。现在需要将新节点与已有的链表结构链接起来。这一过程需要两步，如图3-24所示。第1步（第3行），将新节点的next引用指向当前列表中的第一个节点。这样一来，原来的列表就和新节点正确地链接在了一起。第2步，修改列表的头节点，使其指向新创建的节点。第4行的赋值语句完成了这一操作。

代码清单3-19　add方法

1. def add(self, item):
2. temp = Node(item)
3. temp.setNext(self.head)
4. self.head = temp

图3-24　通过两个步骤添加新节点

上述两步的顺序非常重要。如果颠倒第3行和第4行的顺序，会发生什么呢？如果先修改列表的头节点，将得到如图3-25所示的结果。由于头节点是唯一指向列表节点的外部引用，因此所有的已有节点都将丢失并且无法访问。

图3-25　先修改列表的头节点将导致已有节点丢失

接下来要实现的方法——length、search以及remove——都基于链表遍历这个技术。遍历是指系统地访问每一个节点，具体做法是用一个外部引用从列表的头节点开始访问。随着访问每一个节点，我们将这个外部引用通过“遍历”下一个引用来指向下一个节点。

为了实现length方法，需要遍历链表并且记录访问过多少个节点。代码清单3-20展示了计算列表中节点个数的Python代码。current就是外部引用，它在第2行中被初始化为列表的头节点。在计算开始时，由于没有访问到任何节点，因此count被初始化为0。第4~6行实现遍历过程。只要current引用没有指向列表的结尾（None），就将它指向下一个节点（第6行）。引用能与None进行比较，这一特性非常重要。每当current指向一个新节点时，将count加1。最终，循环完成后返回count。图3-26展示了整个处理过程。

代码清单3-20　length方法

1. def length(self):
2. current = self.head
3. count = 0
4. while current != None:
5. count = count + 1
6. current = current.getNext()
   7.
7. return count

图3-26　从头到尾遍历链表

在无序列表中搜索一个值同样也会用到遍历技术。每当访问一个节点时，检查该节点中的元素是否与要搜索的元素相同。在搜索时，可能并不需要完整遍历列表就能找到该元素。事实上，如果遍历到列表的末尾，就意味着要找的元素不在列表中。如果在遍历过程中找到所需的元素，就没有必要继续遍历了。

代码清单3-21展示了search方法的实现。与在length方法中相似，遍历从列表的头部开始（第2行）。我们使用布尔型变量found来标记是否找到所需的元素。由于一开始时并未找到该元素，因此第3行将found初始化为False。第4行的循环既考虑了是否到达列表末尾，也考虑了是否已经找到目标元素。只要还有未访问的节点并且还没有找到目标元素，就继续检查下一个节点。第5行检查当前节点中的元素是否为目标元素。如果是，就将found设为True。

代码清单3-21　search方法

1. def search(self, item):
2. current = self.head
3. found = False
4. while current != None and not found:
5. if current.getData() == item:
6. found = True
7. else:
8. current = current.getNext()
   9.
9. return found
   以下调用search方法来寻找元素17。

mylist.search(17)
True
由于17在列表中，因此遍历过程只需进行到含有17的节点即可。此时，found变量被设为True，从而使while循环退出，最终得到上面的输出结果。图3-27展示了这一过程。

图3-27　成功搜索到元素17

remove方法在逻辑上需要分两步。第1步，遍历列表并查找要移除的元素。一旦找到该元素（假设元素在列表中），就必须将其移除。第1步与search非常相似。从一个指向列表头节点的外部引用开始，遍历整个列表，直到遇到需要移除的元素。由于假设目标元素已经在列表中，因此我们知道循环会在current抵达None之前结束。这意味着可以在判断条件中使用布尔型变量found。

当found被设为True时，current将指向需要移除的节点。该如何移除它呢？一种做法是将节点包含的值替换成表示其已被移除的值。这种做法的问题是，节点的数量和元素的数量不再匹配。更好的做法是移除整个节点。

为了将包含元素的节点移除，需要将其前面的节点中的next引用指向current之后的节点。然而，并没有反向遍历链表的方法。由于current已经指向了需要修改的节点之后的节点，此时做修改为时已晚。

这一困境的解决方法就是在遍历链表时使用两个外部引用。current与之前一样，标记在链表中的当前位置。新的引用previous总是指向current上一次访问的节点。这样一来，当current指向需要被移除的节点时，previous就刚好指向真正需要修改的节点。

代码清单3-22展示了完整的remove方法。第2~3行对两个引用进行初始赋值。注意，current与其他遍历例子一样，从列表的头节点开始。由于头节点之前没有别的节点，因此previous的初始值是None，如图3-28所示。布尔型变量found再一次被用来控制循环。

代码清单3-22　remove方法

1. def remove(self, item):
2. current = self.head
3. previous = None
4. found = False
5. while not found:
6. if current.getData() == item:
7. found = True
8. else:
9. previous = current
10. current = current.getNext()
    11.
11. if previous == None:
12. self.head = current.getNext()
13. else:
14. previous.setNext(current.getNext())

图3-28　previous和current的初始值

第6~7行检查当前节点中的元素是否为要移除的元素。如果是，就设found为True。如果否，则将previous和current往前移动一次。这两条语句的顺序十分重要。必须先将previous移动到current的位置，然后再移动current。这一过程经常被称为“蠕动”，因为previous必须在current向前移动之前指向其当前位置。图3-29展示了在遍历列表寻找包含17的节点的过程中，previous和current的移动过程。

图3-29　previous和current的移动过程

一旦搜索过程结束，就需要执行移除操作。图3-30展示了修改过程。有一种特殊情况需要注意：如果被移除的元素正好是链表的第一个元素，那么current会指向链表中的第一个节点，previous的值则是None。在这种情况下，需要修改链表的头节点，而不是previous指向的节点，如图3-31所示。

图3-30　移除位于链表中段的节点

图3-31　移除链表中的第一个节点

第12行检查是否遇到上述特殊情况。如果previous没有移动，当found被设为True时，它的值仍然是None。在这种情况下（第13行），链表的头节点被修改成指向当前头节点的下一个节点，从而达到移除头节点的效果。但是，如果previous的值不是None，则说明需要移除的节点在链表结构中的某个位置。在这种情况下，previous指向了next引用需要被修改的节点。第15行使用previous的setNext方法来完成移除操作。注意，在两种情况中，修改后的引用都指向current.getNext()。一个常被提及的问题是，已有的逻辑能否处理移除最后一个节点的情况。这个问题留给你来思考。

剩下的方法append、insert、index和pop都留作练习。注意，每一个方法都需要考虑操作是发生在链表的头节点还是别的位置。此外，insert、index和pop需要提供元素在链表中的位置。请假设位置是从0开始的整数。

3.6.3　有序列表抽象数据类型
接下来学习有序列表。如果前文中的整数列表是以升序排列的有序列表，那么它会被写作17, 26, 31, 54, 77, 93。由于17是最小的元素，因此它就成了列表的第一个元素。同理，由于93是最大的元素，因此它在列表的最后一个位置。

在有序列表中，元素的相对位置取决于它们的基本特征。它们通常以升序或者降序排列，并且我们假设元素之间能进行有意义的比较。有序列表的众多操作与无序列表的相同。

OrderedList()创建一个空有序列表。它不需要参数，且会返回一个空列表。
add(item)假设item之前不在列表中，并向其中添加item，同时保持整个列表的顺序。它接受一个元素作为参数，无返回值。
remove(item)假设item已经在列表中，并从其中移除item。它接受一个元素作为参数，并且修改列表。
search(item)在列表中搜索item。它接受一个元素作为参数，并且返回布尔值。
isEmpty()检查列表是否为空。它不需要参数，并且返回布尔值。
length()返回列表中元素的个数。它不需要参数，并且返回一个整数。
index(item)假设item已经在列表中，并返回该元素在列表中的位置。它接受一个元素作为参数，并且返回该元素的下标。
pop()假设列表不为空，并移除列表中的最后一个元素。它不需要参数，且会返回一个元素。
pop(pos)假设在指定位置pos存在元素，并移除该位置上的元素。它接受位置参数，且会返回一个元素。
3.6.4　实现有序列表
在实现有序列表时必须记住，元素的相对位置取决于它们的基本特征。整数有序列表17, 26, 31, 54, 77, 93可以用如图3-32所示的链式结构来表示。

图3-32　有序列表

OrderedList类的构造方法与UnorderedList类的相同。head引用指向None，代表这是一个空列表，如代码清单3-23所示。

代码清单3-23　OrderedList类的构造方法

1. class OrderedList:
2. def init(self):
3. self.head = None
   因为isEmpty和length仅与列表中的节点数目有关，而与实际的元素值无关，所以这两个方法在有序列表中的实现与在无序列表中一样。同理，由于仍然需要找到目标元素并且通过更改链接来移除节点，因此remove方法的实现也一样。剩下的两个方法，search和add，需要做一些修改。

在无序列表中搜索时，需要逐个遍历节点，直到找到目标节点或者没有节点可以访问。这个方法同样适用于有序列表，但前提是列表包含目标元素。如果目标元素不在列表中，可以利用元素有序排列这一特性尽早终止搜索。

举一个例子。图3-33展示了在有序列表中搜索45的情况。从列表的头节点开始遍历，首先比较45和17。由于17不是要查找的元素，因此移向下一个节点，即26。它也不是要找的元素，所以继续向前比较31和之后的54。由于54不是要查找的元素，因此在无序列表中，我们会继续搜索。但是，在有序列表中不必这么做。一旦节点中的值比正在查找的值更大，搜索就立刻结束并返回False。这是因为，要查找的元素不可能存在于链表后序的节点中。

图3-33　在有序列表中查找元素

代码清单3-24展示了完整的search方法。通过增加新的布尔型变量stop，并将其初始化为False（第4行），可以将上述条件轻松整合到代码中。当stop是False时，我们可以继续搜索链表（第5行）。如果遇到其值大于目标元素的节点，则将stop设为True（第9~10行）。之后的代码与无序列表中的一样。

代码清单3-24　有序列表的search方法

1. def search(self, item):
2. current = self.head
3. found = False
4. stop = False
5. while current != None and not found and not stop:
6. if current.getData() == item:
7. found = True
8. else:
9. if current.getData() > item:
10. stop = True
11. else:
12. current = current.getNext()
    13.
13. return found
    需要修改最多的是add方法。对于无序列表，add方法可以简单地将一个节点放在列表的头部，这是最简便的访问点。不巧，这种做法不适合有序列表。我们需要在已有链表中为新节点找到正确的插入位置。

假设要向有序列表17, 26, 54, 77, 93中添加31。add方法必须确定新元素的位置在26和54之间。图3-34展示了我们期望的结果。像之前解释的一样，需要遍历链表来查找新元素的插入位置。当访问完所有节点（current是None）或者当前值大于要添加的元素时，就找到了插入位置。在本例中，遇到54使得遍历过程终止。

图3-34　向有序列表中添加元素

和无序列表一样，由于current无法提供对待修改节点的访问，因此使用额外的引用previous是十分必要的。代码清单3-25展示了完整的add方法。第2~3行初始化两个外部引用，第9~10行保证previous一直跟在current后面。只要还有节点可以访问，并且当前节点的值不大于要插入的元素，判断条件就会允许循环继续执行。在循环停止时，就找到了新节点的插入位置。

代码清单3-25　有序列表的add方法

1. def add(self, item):
2. current = self.head
3. previous = None
4. stop = False
5. while current != None and not stop:
6. if current.getData() > item:
7. stop = True
8. else:
9. previous = current
10. current = current.getNext()
    11.
11. temp = Node(item)
12. if previous == None:
13. temp.setNext(self.head)
14. self.head = temp
15. else:
16. temp.setNext(current)
17. previous.setNext(temp)
    一旦创建了新节点，唯一的问题就是它会被添加到链表的开头还是中间某个位置。previous == None（第13行）可以提供答案。

剩下的方法留作练习。需要认真思考，在无序列表中的实现是否可用于有序列表。

链表分析

在分析链表操作的时间复杂度时，考虑其是否需要遍历列表。以有n个节点的链表为例，isEmpty方法的时间复杂度是O(1)，这是因为它只需要执行一步操作，即检查head引用是否为None。length方法则总是需要执行n步操作，这是因为只有完全遍历整个列表才能知道究竟有多少个元素。因此，length方法的时间复杂度是O(n)。向无序列表中添加元素是O(1)，这是因为只是简单地将新节点放在链表的第一个位置。但是，有序列表的search、remove以及add都需要进行遍历操作。尽管它们平均都只需要遍历一半的节点，但是这些方法的时间复杂度都是O(n)。这是因为在最坏情况下，它们都需要遍历所有节点。

我们注意到，本节实现的链表在性能上和Python列表有差异。这意味着Python列表并不是通过链表实现的。实际上，Python列表是基于数组实现的。第8章将深入讨论。

3.7　小结
线性数据结构以有序的方式来维护其数据。
栈是简单的数据结构，其排序原则是LIFO，即后进先出。
栈的基本操作有push、pop和isEmpty。
队列是简单的数据结构，其排序原则是FIFO，即先进先出。
队列的基本操作有enqueue、dequeue和isEmpty。
表达式有3种写法：前序、中序和后序。
栈在计算和转换表达式的算法中十分有用。
栈具有反转特性。
队列有助于构建时序模拟。
模拟程序使用随机数生成器来模拟实际情况，并且帮助我们回答“如果”问题。
双端队列是栈和队列的结合。
双端队列的基本操作有addFront、addRear、removeFront、removeRear和isEmpty。
列表是元素的集合，其中每一个元素都有一个相对于其他元素的位置。
链表保证逻辑顺序，对实际的存储顺序没有要求。
修改链表头部是一种特殊情况。
3.8　关键术语
FIFO LIFO 遍历链表 队列 后序
回文 节点 链表 列表 模拟
匹配括号 前序 数据变量 双端队列 头部
完全括号 线性数据结构 优先级 栈 中序
3.9　讨论题
使用“除以2”算法将下列值转换成二进制数。列出转换过程中的余数。

17
45
96
使用完全括号法，将下列中序表达式转换成前序表达式。

(A + B) (C + D) (E + F)
A + ((B + C) (D + E))
A B C D + E + F
使用完全括号法，将上面的中序表达式转换成后序表达式。

使用直接转换法，将上面的中序表达式转换成后序表达式。展示转换过程中栈的变化。
计算下列后序表达式。展示计算过程中栈的变化。

2 3 4 +
1 2 + 3 + 4 + 5 +
1 2 3 4 5 + * +
队列抽象数据类型的另一种实现方式是使用列表，并使得列表的后端是队列的尾部。这种实现的大O性能如何？

在链表的add方法中，颠倒两个步骤的执行顺序会是什么结果？引用的结果会是怎么样？会出现什么问题？
假设需要移除链表中的最后一个节点，解释如何实现remove方法。
假设链表只有一个节点，解释如何实现remove方法。
3.10　编程练习
修改从中序到后序的转换算法，使其能处理异常情况。
修改计算后序表达式的算法，使其能处理异常情况。
结合从中序到后序的转换算法以及计算后序表达式的算法，实现直接的中序计算。在计算时，应该使用两个栈从左往右处理中序表达式标记。一个栈用于保存运算符，另一个用于保存操作数。
将在练习3中实现的算法做成一个计算器。
使用列表实现队列抽象数据类型，将列表的后端作为队列的尾部。
设计和实现一个实验，对比两种队列实现的性能。能从该实验中学到什么？
实现一个队列，使其添加操作和移除操作的平均时间复杂度为O(1)。这意味着在大多数情况下，两个操作的时间复杂度都是O(1)，仅在一种特殊情况下，移除操作为O(n)。
考虑现实生活中的一个场景。完整地定义问题，并且设计一个模拟来解答它。以下是一些例子：

排队等待洗车；
在超市等待结账；
飞机的起飞和降落；
银行出纳员。
请说明你所做的任何假设，并且提供所需的概率数据。
修改传土豆模拟程序，允许随机计数，从而使每一轮的结果都不可预测。

实现一个基数排序器。十进制数的基数排序利用1个主桶和10个数位桶。每个桶就像一个队列，并且根据数字到达的先后顺序来维持其中的值。该算法首先将所有的数都放在主桶中，然后按照数值中的每一个数位来考察这些值。第一个值从主桶中移除并且根据在考察的数位将其放到对应的数位桶中。如果考察的是个位，那么534将被放在4号数位桶中，667则将被放在7号数位桶中。一旦所有的值都被放在了相应的数位桶中，便依次从0号到9号数位桶中将值放回主桶。重复整个过程到数字的十位、百位等。在最后一个数位被处理完之后，主桶里面就是排好序的值。
除了本章所举的例子，HTML中也存在括号匹配问题。标签有开始和结束两种形式，并且需要互相匹配才能正确描述网页内容。下面是简单的HTML文档，用于展示标签的匹配和嵌套。写一个程序来检查HTML文档中的标签是否正确匹配。

Hello, world

</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)。