基本数据结构——线性结构（栈）

1.什么是线性结构

线性结构是一种有序数据项的集合，其中每个数据项都有唯一的前驱和后继（除了第一个没有前驱，最后一个没有后继）。新的数据项加入到数据集中时，只会加入到原有某个数据项之前或之后。具有这种性质的数据集，就称为线性结构。 不同线性结构的关键区别在于数据项增减的方式。有的结构只允许数据项从一端添加，而有的机构则允许数据项从两端移除。

2.从4个最简单但功能强大的结构入手，开始研究数据结构（栈Stack、队列Queue、双端队列DQeque、列表List）

2.1 栈

2.1.1 什么是栈？

一种有次序的数据项集合。在栈中，数据项的加入和移除仅发生在同一端。这一端叫栈顶(top)，另一端叫栈底(base) 距离栈底越近的数据项留在栈中的时间越长，而新加入栈的数据项会被最先移除。这种次序通常称为“后进先出”(Last in First out,LIFO)。这是一种基于数据项保存时间的次序，时间越短的离栈顶越近，而时间越长的离栈底越近。

2.1.2 抽象数据类型“栈”定义的操作

操作样例

2.1.3 用python实现ADT Stack

#定义ADT Stack 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)#返回栈的大小 #stack测试代码 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())

2.1.4 栈的应用：简单括号匹配

如何构造括号匹配识别算法？

从左到右扫描括号串，最新打开的左括号应该匹配最先遇到的有括号。这样，第一个左括号（最先打开）就应该匹配最后一个右括号（最后遇到）。这种反转的识别，正好符合栈的特性。

#定义ADT Stack 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)#返回栈的大小 #括号匹配问题 def parChecker(symbolString): s=Stack()#创建一个空栈 balanced=True#为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 print(parChecker('((()))')) print(parChecker('(()'))

通用括号匹配算法

#定义ADT Stack 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)#返回栈的大小 #通用括号匹配问题 def parChecker(symbolString): s=Stack()#传建一个空栈 balanced=True#为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) print(parChecker('{{([][])}()}')) print(parChecker('([)'))

2.1.5 栈的应用：十进制转二进制

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) #十进制转二进制 def divideBy2(number): remstack=Stack() while number>0: rem=number%2 #number除以2取余数 remstack.push(rem) number=number//2#number除以2求商 #将保存在栈中的数据输出 binString="" while not remstack.isEmpty(): binString=binString+str(remstack.pop()) return binString print(divideBy2(42))

十进制转十六进制以下的任意进制

#定义ADT Stack 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) #十进制转为十六进制以下的任意进制 def baseConverter(number,base): digits="0123456789ABCDEF" remstack=Stack() while number>0: rem=number%base #number除以base取余数 remstack.push(rem) number=number//base#number除以base求商 #将保存在栈中的数据输出 newString="" while not remstack.isEmpty(): newString=newString+digits[remstack.pop()] return newString print(baseConverter(25,2))#十进制转二进制 print(baseConverter(25,8))#十进制转八进制 print(baseConverter(25,16))#十进制转十六进制

2.1.6 栈的应用：通用的中缀转后缀算法

我们通常看到的表达式像这样：BC，很容易知道这是B乘以C。这种操作符(operator)介于操作数(operand)中间的表示法称为中缀表示法。但是有时候中缀表示法会引起混淆，如"A+BC"表示A+B然后再乘以C还是B*C然后再加A？ 例如中缀表达式A+B 将操作符移到前面，变成“+AB”； 或者将操作符一道最后，变为“AB+” 我们就得到了表达式的另外两种表示法：“前缀”和“后缀”表示法（以操作符相对于操作数的位置来定义）。 举例

中缀表达式转换为前缀和后缀形式的步骤

（1）将中缀表达式转换为全括号形式 （2）将所有的操作符移动到子表达式所在左括号（前缀）或者右括号（后缀）处，替代之，再删除所有括号。

通用的中缀转后缀算法

后面的算法描述中，约定中缀表达式是由空格隔开的一系列单词（token）构成。操作符单词包括*/±()，而操作数单次则是单字母标识符A、B、C等 （1）创建空栈opstack用于暂存操作符，空表postfixList用于保存后缀表达式。 （2）将中缀表达式转换为单词（token）列表 A+BC=split=>[‘A’,’+’,‘B’,’’,‘C’] (3)从左到右扫描中缀表达式单词列表

如果单词是操作数，则直接添加到后缀表达式列表的末尾如果单词是左括号“(”，则压入opstack栈顶如果单词是右括号“)”,则反复弹出opstack栈顶操作符，加入到输出列表末尾，直到碰到左括号如果单词是操作符“*/±”，则压入opstack栈顶（但是咋压入之前，要比较其与栈顶操作符的优先级，如果栈顶的高于或低于它，就要反复弹出栈顶操作符，加入到输出列表末尾，直到栈顶的操作符优先级低于它） （4）中缀表达式单词列表扫描结束后，把opstack栈中的所有剩余操作符依次弹出，添加到输出列表末尾。 （5）把输出列表再用join方法合并成后缀表达式字符串，算法结束。

实例

python代码实现

#定义ADT Stack 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)#返回栈的大小 #通用的中缀表达式转为后缀表达式 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栈顶 opStack.push(token) elif token==')':# 如果单词是右括号“)”,则反复弹出opstack栈顶操作符，加入到输出列表末尾，直到碰到左括号 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():#把opstack栈中的所有剩余操作符依次弹出，添加到输出列表末尾。 postfixList.append(opStack.pop()) return " ".join(postfixList)#合成后缀表达式字符串 print(infixToPostfix('A * B + C * D'))

2.1.7 后缀表达式求值问题

在对后缀表达式从左到右扫描的过程中，由于操作符在操作数后面，所以要暂存操作数，在碰到操作符的时候再将暂存的两个操作数进行实际的计算。

实例

后缀表达式求值算法流程

（1）创建空栈operandStack用于暂存操作数 （2）将后缀表达式用split方法解析为单词（token）的列表 （3）从左到右扫描单词列表

如果但此时一个操作数，将单词转换为整数int，压入operandStack栈顶如果单词是一个操作符（*/±），就开始求值，从栈顶弹出2个操作数，先弹出的是右操作数，后弹出的是左操作数，计算后将值重新呀入栈顶。 （4）单词列表扫描结束后，表达式的值就在栈顶 （5）弹出栈顶的值，返回

python代码实现

#定义ADT Stack 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)#返回栈的大小 #后缀表达式求值 def postfixEval(postfixExpr): operandStack=Stack() tokenList=postfixExpr.split() for token in tokenList: if token in "0123456789":#如果是操作数，将单词转为整数int，压入operandStack栈顶 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 if op=="/": return op1/op2 if op=="+": return op1+op2 else: return op1-op2 print(postfixEval("4 5 6 * +"))