数据结构和算法是计算机技术的基本功之一，北京大学的课程深入浅出，使用Python作为载体简化了编程难度。今天浏览了17-21，主要介绍了【栈】作为一种重要的基本线性数据结构的特点和作用。栈的特点在于后进先出，即后进栈的元素一定要比之前进的元素先出栈。为实现这一结构，使其复杂度为O(1)，使用Python中List类型的List.append()和List.pop()来实现，这两个方法都是Python实现的高效操作，满足我们的需求。

线性结构的特点是有序数据项的集合，每个项都有前驱和后继。栈结构是后进先出的线性结构。

接下来用三个例子表现了栈结构的用法和优点：1、括号匹配 2、多种进制转换 3、不同风格计算指令的转化与计算

特将笔记整理如下，算法实现的要点在注释中给出，存在多种实现方式：

有序数据项的集合，每个数据项都有唯一的前驱和后继

每个项都有唯一的【前驱】和【后继】

左端右端，顶端底端

有的只允许一端添加，有的双端可添加移除，有的中间位置也可

四种基本结构，共同点是数据项之间只存在先后次序关系

栈Stack-抽象数据类型

只在一端加入和移除，后进先出

离栈底越近保存时间越长-反转次序

例如浏览器的后退，word的undo

"""
Stack()
push(item)
pop()
peek()窥视栈顶数据项
isEmpty()
size()
"""

将Stack实现为Python的一个class，选用list来实现

list[0] list[-1]末端设为栈底

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

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

def push(self,item):
    self.items.append(item)
    # self.items.insert(0,item)-栈顶首端，复杂度o（n）

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

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

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

s=Stack()
s.push('a')
s.push(3)
print(s.peek())#返回 3

栈的应用

1 括号匹配

最新的左括号应该匹配第一个右括号

def parCheck(str1):#str假设只有(()))
s=Stack()
balanced=True
index=0
while index<len(str1) and balanced:
symbol=str1[index]
if symbol in "([{":
s.push(symbol)#左括号放进栈顶
else:
if s.isEmpty():
balanced=False
else:
if (s.peek()=="[" and symbol=="]") or (s.peek()=="{"and symbol=="}") or (s.peek()=="(" and symbol==")"):
s.pop()#根据右括号匹配程度移除左括号
else:
balanced=False
index+=1
if balanced and s.isEmpty():
return True
else:
return False
print(parCheck("({{[]}})"),parCheck("([))"))

2 十进制转换为二进制

从十到二是不停除以2，得到的余数依次是二进制的2 4 8 16

注意到，二进制读取一个数的顺序是从左到右，所以用栈结构，实现先读后得到的数据

def divideBy2(decNumber):
remstack=Stack()#使用字定义的栈类
while decNumber>0:
rem=decNumber%2#pyhton 取余数操作
remstack.push(rem)
decNumber=decNumber//2#python 取整除法操作
binstring=""
while not remstack.isEmpty():#Ensure not empty 校验输出非空
binstring+= str(remstack.pop())
return binstring

print(divideBy2(64)) #输出 1000000 通过

十六进制 0-9 和 ABCDEF

def baseConvrter(decNumber,base):#十进制转十六以下任意进制
digits="0123456789ABCDEF"#定义字母表，需要更多进制扩增此列表即可
remSta=Stack()
while decNumber>0:
rem=decNumber%base#base为希望转成的进制数,rem为递进位数在字母表中的位置
remSta.push(rem)#栈存储位置列表
decNumber=decNumber//base#改变十进制数
returns=""
while remSta.isEmpty()==False:
returns+=str(digits[remSta.pop()])#查表组成输出
return returns

print(baseConvrter(25,16))
print(baseConvrter(25,2)==divideBy2(25))

中缀表达式， a*b，规定优先级，括号强制优先级

全括号表达式

前缀表达式AB，后缀AB

+ABC 前缀 A+BC 后缀 ABC*+，操作符执行最近位置的操作

3 表达式风格转换

首先转化为全括号表达式问题，只需要将某操作符移到右括号处，再删除对应左右括号，

就变成了后缀表达式。移到左括号处就变成了前缀表达式。

【从左往右扫描，每遇到左括号，其后操作符优先级提升，用栈来保存未处理操作符】

新操作符与栈顶操作符比较优先级

约定：中缀表达式由空格隔开的一系列单词token构成

“A,+,B,*,C”

如果token是ABC操作数，直接添加后缀表达式列表末尾

从左到右依次扫描中缀表达式单词列表，如果是左括号则push到opstack栈顶；

在加入之前比较优先级，如果栈顶操作符优先级更高就弹出操作符到输出列表末尾

右括号则【反复弹出opstack栈顶加入到输出列表末尾，直到碰到左括号】

中缀表达式扫描结束后，把栈中所有剩余操作符依次弹出添加到输出列表末尾，join拼接

AB+CD 转化成 ABCD+的后缀表达式

def infixToPostfix(infixstr):
prec={}
prec["*"]=3
prec["/"]=3
prec["+"]=2
prec["-"]=2
prec["("]=1
opStack=Stack()
postfixlist=[]
tokenList=infixstr.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 )"))

4 后缀表达式求值

需要暂存操作数，这依然是栈的特性，因为操作符计算靠的最近的操作数

先出栈右操作数（后入栈）

中间结果一样压入栈顶，继续处理，直到栈中剩下结果值

def postfixEval(postfixExpr):
operandStack=Stack()#操作数栈
tokenList=postfixExpr.split()
for token in tokenList:
if token in "0123456789":
operandStack.push(token)
elif token=="+":
a1=float(operandStack.pop())
a2=float(operandStack.pop())
operandStack.push(a1+a2)
elif token=="":
a1=float(operandStack.pop())
a2=float(operandStack.pop())
operandStack.push(a1a2)
elif token=="-":
a1=float(operandStack.pop())
a2=float(operandStack.pop())
operandStack.push(a2-a1)
elif token=="/":
a1=float(operandStack.pop())
a2=float(operandStack.pop())
operandStack.push(a2/a1)
return operandStack.peek()

print(postfixEval("3 5 / 2 +"))