基本数据结构

基本数据结构

目标

  • 理解抽象数据类型的栈,队列,deque 和列表。
  • 能够使用 Python 列表实现 ADT 堆栈,队列和 deque。
  • 了解基本线性数据结构实现的性能。
  • 了解前缀,中缀和后缀表达式格式。
  • 使用栈来实现后缀表达式。
  • 使用栈将表达式从中缀转换为后缀。
  • 使用队列进行基本时序仿真。
  • 能够识别问题中栈,队列和 deques 数据结构的适当使用。
  • 能够使用节点和引用将抽象数据类型列表实现为链表。
  • 能够比较我们的链表实现与 Python 的列表实现的性能。

    什么是线性数据结构

    我们从四个简单但重要的概念开始研究数据结构。栈,队列,deques, 列表是一类数据的容器,它们数据项之间的顺序由添加或删除的顺序决定。一旦一个数据项被添加,它相对于前后元素一直保持该位置不变。诸如此类的数据结构被称为线性数据结构。

线性数据结构有两端,有时被称为左右,某些情况被称为前后。你也可以称为顶部和底部,名字都不重要。将两个线性数据结构区分开的方法是添加和移除项的方式,特别是添加和移除项的位置。例如一些结构允许从一端添加项,另一些允许从另一端移除项。

这些变种的形式产生了计算机科学最有用的数据结构。他们出现在各种算法中,并可以用于解决很多重要的问题。

什么是栈

(有时称为“后进先出栈”)是一个项的有序集合,其中添加移除新项总发生在同一端。这一端通常称为“顶部”。与顶部对应的端称为“底部”。

栈的底部很重要,因为在栈中靠近底部的项是存储时间最长的。最近添加的项是最先会被移除的。这种排序原则有时被称为LIFO,后进先出。它基于在集合内的时间长度做排序。较新的项靠近顶部,较旧的项靠近底部。

栈的例子很常见。几乎所有的自助餐厅都有一堆托盘或盘子,你从顶部拿一个,就会有一个新的托盘给下一个客人。想象桌上有一堆书(Figure 1), 只有顶部的那本书封面可见,要看到其他书的封面,只有先移除他们上面的书。Figure 2展示了另一个栈,包含了很多按Python对象。
figure1Figure 1
figure2Figure 2

和栈相关的最有用的想法之一来自对它的观察。假设从一个干净的桌面开始,现在把书一本本叠起来,你在构造一个栈。考虑下移除一本书会发生什么。移除的顺序跟刚刚被放置的顺序相反。栈之所以重要是因为它能反转项的顺序。插入跟删除顺序相反,Figure 3展示了Python数据对象创建和删除的过程,注意观察他们的顺序。
figure3Figure 3

想想这种反转的属性,你可以想到使用计算机的时候所碰到的例子。例如,每个 web 浏览器都有一个返回按钮。当你浏览网页时,这些网页被放置在一个栈中(实际是网页的网址)。你现在查看的网页在顶部,你第一个查看的网页在底部。如果按‘返回’按钮,将按相反的顺序浏览刚才的页面。

栈的抽象数据类型

栈的抽象数据类型由以下结构和操作定义。如上所述,栈被构造为项的有序集合,其中项被添加和从末端移除的位置称为“顶部”。栈是有序的LIFO。栈操作如下。

  • Stack() 创建一个空的新栈。 它不需要参数,并返回一个空栈。
  • push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。
  • pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。
  • peek() 从栈返回顶部项,但不会删除它。不需要参数。 不修改栈。
  • isEmpty() 测试栈是否为空。不需要参数,并返回布尔值。
  • size() 返回栈中的 item 数量。不需要参数,并返回一个整数。

例如,s是已经创建的空栈,Table1展示了栈操作序列的结果。栈中,顶部项列在最右边。
table1Table 1

Python实现栈

现在我们已经将栈清楚地定义了抽象数据类型,我们将把注意力转向使用Python实现栈。回想一下,当我们给抽象数据类型一个物理实现时,我们将实现称为数据结构。
正如我们在第1章中所描述的,在Python中,与任何面向对象编程语言一样,抽象数据类型(如栈)的选择的实现是创建一个新类。栈操作实现为类的方法。此外,为了实现作为元素集合的栈,使用由Python提供的原语集合的能力是有意义的。我们将使用列表作为底层实现。
回想一下,Python中的列表类提供了有序集合机制和一组方法。例如,如果我们有列表[2,5,3,6,7,4],我们只需要确定列表的哪一端将被认为是栈的顶部。一旦确定,可以使用诸如appendpop的列表方法来实现操作。
以下栈实现(ActiveCode 1)假定列表的结尾将保存栈的顶部元素。随着栈增长(push操作),新项将被添加到列表的末尾。pop也操作列表末尾的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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)

ActiveCode 1
记住我们只定义类的实现,我们需要创建一个栈,然后使用它。ActiveCode 2展示了我们通过实例化Stack类执行Table 1中的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
s=Stack()

print(s.isEmpty())
s.push(4)
s.push('dog')
print(s.peek())
s.push(True)
print(s.size())
print(s.isEmpty())
s.push(8.4)
print(s.pop())
print(s.pop())
print(s.size())

ActiveCode 2

中缀,前缀和后缀表达式

当你编写一个算术表达式如B*C时,表达式的形式使你能够正确理解它。在这种情况下,你知道B乘以C, 因为乘法运算符*出现在表达式中。这种类型的符号称为中缀,因为运算符在它处理的两个操作数之间。看另外一个中缀示例,A+B*C,运算符+*仍然出现在操作数之间。这里面有个问题是,他们分别作用于哪个运算数上,+作用于AB, 还是*作用于B和C?表达式似乎有点模糊。

事实上,你已经读写过这些类型的表达式很长一段时间,所以它们对你不会导致什么问题。这是因为你知道运算符+*。每个运算符都有一个优先级。优先级较高的运算符在优先级较低的运算符之前使用。唯一改变顺序的是括号的存在。算术运算符的优先顺序是将乘法和除法置于加法和减法之上。如果出现具有相等优先级的两个运算符,则使用从左到右的顺序排序或关联。

我们使用运算符优先级来解释下表达式A+B*CBC首先相乘,然后将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 +,这样看起来有点奇怪。

改变操作符的位置得到了两种新的表达式格式,前缀和后缀。前缀表达式符号要求所有运算符在它们处理的两个操作数之前。另一个方面,后缀要求其操作符在相应的操作数之后。看下更多的例子 (见 Table 2)
A+BC 将在前缀中写为 + A B C 。乘法运算符紧接在操作数 B 和 C 之前,表示 优先于 +。然后加法运算符出现在 A 和乘法的结果之前。
在后缀中,表达式将是 A B C
+,再次,操作的顺序被保留,因为 紧接在 B 和 C 之后出现,表示 具有高优先级,+ 优先级低。虽然操作符在它们各自的操作数前后移动,但是顺序相对于彼此保持完全相同。
3.9.中缀后缀和后缀表达式.table2

Table 2
现在考虑中缀表达式 (A + B) C,回想下,在这种情况下,中缀需要括号在乘法之前强制执行加法。然而,当 A+B 写到前缀中时,加法运算符简单的移动到操作数 + A B 之前。这个操作的结果成为乘法的第一个操作数。乘法运算符移动到整个表达式的前面,得出 + A B C,同样,在后缀 A B +中,强制先加法。可以直接对该结果和剩余的操作数 C 相乘。然后,得出后缀表达式为 A B + C *。
再次考虑这三个表达式(见 Table 3),括号不见了。为什么在前缀和后缀的时候不需要括号了呢?答案是操作符对于他们的操作数不再模糊,只有中缀才需要括号,前缀和后缀表达式的操作顺序完全由操作符的顺序决定。
3.9.中缀后缀和后缀表达式.table3

Table 3
Table 4 展示了一些其他的例子
3.9.中缀后缀和后缀表达式.table4

Table 4
3.9.1.中缀表达式转换前缀和后缀
到目前为止,我们已经使用特定方法在中缀表达式和等效前缀和后缀表达式符号之间进行转换。正如你可能期望的,有一些算法来执行转换,允许任何复杂表达式转换。
我们考虑的第一种技术使用前面讨论的完全括号表达式的概念。回想一下,A + B C可以写成(A +(B C)),以明确标识乘法优先于加法。然而,仔细观察,你可以看到每个括号对还表示操作数对的开始和结束,中间有相应的运算符。
看上面的子表达式(B C)中的右括号。 如果我们将乘法符号移动到那个位置,并删除匹配的左括号,得到 B C ,我们实际上已经将子表达式转换为后缀符号。 如果加法运算符也被移动到其相应的右括号位置并且匹配的左括号被去除,则将得到完整的后缀表达式(见 Figure 6)。
3.9.中缀后缀和后缀表达式.figure6

Figure 6
如果我们不是将符号移动到右括号的位置,我们将它向左移动,我们得到前缀符号(见 Figure 7)。圆括号对的位置实际上是包含的运算符的最终位置的线索。 3.9.中缀后缀和后缀表达式.figure7
Figure 7
所以为了转换表达式,无论是对前缀还是后缀符号,先根据操作的顺序把表达式转换成完全括号表达式。然后将包含的运算符移动到左或右括号的位置,具体取决于需要前缀或后缀符号。
这里面有个更复杂的例子, (A + B) C - (D - E) (F + G) ,Figure 8 显示了如何转换为后缀和前缀。
3.9.中缀后缀和后缀表达式.figure8

Figure 8
3.9.2.中缀转后缀通用法
我们需要开发一个算法来将任何中缀表达式转换为后缀表达式。 为了做到这一点,我们仔细看看转换过程。
再次考虑表达式 A + B C。如上所示,A B C +是等价的后缀表达式。 我们已经注意到,操作数 A,B 和 C 保持在它们的相对位置。只有操作符改变位置。再看中缀表达式中的运算符。从左到右出现的第一个运算符为 +。 然而,在后缀表达式中,+ 在结束位置,因为下一个运算符 的优先级高于加法。 原始表达式中的运算符的顺序在生成的后缀表达式中相反。
当我们处理表达式时,操作符必须保存在某处,因为它们相应的右操作数还没有看到。 此外,这些保存的操作符的顺序可能由于它们的优先级而需要反转。这是在该示例中的加法和乘法的情况,由于加法运算符在乘法运算符之前,并且具有较低的优先级,因此需要在使用乘法运算符之后出现。 由于这种顺序的反转,考虑使用栈来保存运算符直到用到它们是有意义的。
(A + B)
C的情况会是什么样呢? 回想一下,A B + C 是等价的后缀表达式。从左到右处理此中缀表达式,我们先看到 +。 在这种情况下,当我们看到 ,+已经放置在结果表达式中,由于括号它的优先级高于。 我们现在可以开始看看转换算法如何工作。当我们看到左括号时,我们保存它,表示高优先级的另一个运算符将出现。该操作符需要等到相应的右括号出现以表示其位置(回忆完全括号的算法)。 当右括号出现时,可以从栈中弹出操作符。
当我们从左到右扫描中缀表达式时,我们将使用栈来保留运算符。这将提供我们在第一个例子中注意到的反转。 堆栈的顶部将始终是最近保存的运算符。每当我们读取一个新的运算符时,我们需要考虑该运算符如何与已经在栈上的运算符(如果有的话)比较优先级。
假设中缀表达式是一个由空格分隔的标记字符串。 操作符标记是
,/,+和 - ,以及左右括号。操作数是单字符 A,B,C 等。 以下步骤将后缀顺序生成一个字符串。
创建一个名为 opstack 的空栈以保存运算符。给输出创建一个空列表。
通过使用字符串方法拆分将输入的中缀字符串转换为标记列表。
从左到右扫描标记列表。
如果标记是操作数,将其附加到输出列表的末尾。
如果标记是左括号,将其压到 opstack 上。
如果标记是右括号,则弹出 opstack,直到删除相应的左括号。将每个运算符附加到输出列表的末尾。
如果标记是运算符,,/,+或 - ,将其压入 opstack。但是,首先删除已经在 opstack 中具有更高或相等优先级的任何运算符,并将它们加到输出列表中。
当输入表达式被完全处理时,检查 opstack。仍然在栈上的任何运算符都可以删除并加到输出列表的末尾。
Figure 9 展示了对表达式 A
B + C D 的转换算法。注意,第一个 在看到 + 运算符时被删除。另外,当第二个 * 出现时, + 保留在栈中,因为乘法优先级高于加法。在中缀表达式的末尾,栈被弹出两次,删除两个运算符,并将 + 作为后缀表达式中的最后一个运算符。
3.9.中缀后缀和后缀表达式.figure9

Figure 9
为了在 Python 中编写算法,我们使用一个名为 prec 的字典来保存操作符的优先级。这个字典将每个运算符映射到一个整数,可以与其他运算符的优先级(我们使用整数3,2和1)进行比较。左括号将赋予最低的值。这样,与其进行比较的任何运算符将具有更高的优先级,将被放置在它的顶部。第15行将操作数定义为任何大写字符或数字。完整的转换函数见 ActiveCode 1。
from pythonds.basic.stack import Stack

def infixToPostfix(infixexpr):
prec = {}
prec[“*”] = 3
prec[“/“] = 3
prec[“+”] = 2
prec[“-“] = 2
prec[“(“] = 1
opStack = Stack()
postfixList = []
tokenList = infixexpr.split()

for token in tokenList:
    if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
        postfixList.append(token)
    elif token == '(':
        opStack.push(token)
    elif token == ')':
        topToken = opStack.pop()
        while topToken != '(':
            postfixList.append(topToken)
            topToken = opStack.pop()
    else:
        while (not opStack.isEmpty()) and \
           (prec[opStack.peek()] >= prec[token]):
              postfixList.append(opStack.pop())
        opStack.push(token)

while not opStack.isEmpty():
    postfixList.append(opStack.pop())
return " ".join(postfixList)

print(infixToPostfix(“A B + C D”))
print(infixToPostfix(“( A + B ) C - ( D - E ) ( F + G )”))
执行结果如下

infixtopostfix(“( A + B ) ( C + D )”)
‘A B + C D +

infixtopostfix(“( A + B ) C”)
‘A B + C

infixtopostfix(“A + B C”)
‘A B C
+’

3.9.3.后缀表达式求值
作为最后栈的示例,我们考虑对后缀符号中的表达式求值。在这种情况下,栈再次是我们选择的数据结构。但是,在扫描后缀表达式时,它必须等待操作数,而不像上面的转换算法中的运算符。 解决问题的另一种方法是,每当在输入上看到运算符时,计算两个最近的操作数。
要详细的了解这一点,考虑后缀表达式 4 5 6 +, 首先遇到操作数 4 和 5,此时,你还不确定如何处理它们,直到看到下一个符号。将它们放置到栈上,确保它们在下一个操作符出现时可用。
在这种情况下,下一个符号是另一个操作数。所以,像先前一样,压入栈中。并检查下一个符号。现在我们看到了操作符
,这意味着需要将两个最近的操作数相乘。通过弹出栈两次,我们可以得到正确的两个操作数,然后执行乘法(这种情况下结果为 30)。
我们现在可以通过将其放回栈中来处理此结果,以便它可以表示为表达式后面的运算符的操作数。当处理最后一个操作符时,栈上只有一个值,弹出并返回它作为表达式的结果。Figure 10 展示了整个示例表达式的栈的内容。
3.9.中缀后缀和后缀表达式.figure10

Figure 10
Figure 11 是个稍微复杂的示例,7 8 + 3 2 + / 。在这个例子中有两点需要注意,首先,栈的大小增长收缩,然后再子表达式求值的时候再次增长。第二,除法操作需要谨慎处理。回想下,后缀表达式的操作符顺序没变,仅仅改变操作符的位置。当用于除法的操作符从栈中弹出时,它们被反转。由于除法不是交换运算符,换句话说 15/5和 5/15 不同,因此我们必须保证操作数的顺序不会交换。
3.9.中缀后缀和后缀表达式.figure11

Figure 11
假设后缀表达式是一个由空格分隔的标记字符串。 运算符为,/,+和 - ,操作数假定为单个整数值。 输出将是一个整数结果。
创建一个名为 operandStack 的空栈。
拆分字符串转换为标记列表。
从左到右扫描标记列表。
如果标记是操作数,将其从字符串转换为整数,并将值压到operandStack。
如果标记是运算符
,/,+或-,它将需要两个操作数。弹出operandStack 两次。 第一个弹出的是第二个操作数,第二个弹出的是第一个操作数。执行算术运算后,将结果压到操作数栈中。
当输入的表达式被完全处理后,结果就在栈上,弹出 operandStack 并返回值。
用于计算后缀表达式的完整函数见 ActiveCode 2,为了辅助计算,定义了一个函数 doMath, 它将获取两个操作数和运算符,执行相应的计算。
from pythonds.basic.stack import Stack

def postfixEval(postfixExpr):
operandStack = Stack()
tokenList = postfixExpr.split()

for token in tokenList:
    if token in "0123456789":
        operandStack.push(int(token))
    else:
        operand2 = operandStack.pop()
        operand1 = operandStack.pop()
        result = doMath(token,operand1,operand2)
        operandStack.push(result)
return operandStack.pop()

def doMath(op, op1, op2):
if op == ““:
return op1
op2
elif op == “/“:
return op1 / op2
elif op == “+”:
return op1 + op2
else:
return op1 - op2

print(postfixEval(‘7 8 + 3 2 + /‘))