栈（stack），也称为堆栈，是一种特殊的有序列表。它的插入和删除操作都在栈顶进行，按照先进后出和后进先出的规则进行。操作。如下图，以一把枪的弹匣为例，发射时第一颗进弹匣的子弹就是最后一颗，最后一颗进弹匣的子弹就是开火时第一颗发射的子弹。解雇了。的。栈的接口如果你创建了一个栈，那么你应该有如下的接口来对栈进行操作。知道栈需要上面的接口之后，那么在Python中，列表类似于一个栈，接口如下：Python中的Stack接口使用示例：#CreateastackIn[1]:s=[]#向栈中添加一个元素In[2]:s.append(1)In[3]:sOut[3]:[1]#删除栈中的一个元素In[4]:s.pop()Out[4]:1In[5]:sOut[5]:[]#判断栈是否为空In[6]:notsOut[6]:TrueIn[7]:s.append(1)In[8]:notsOut[8]:False#获取栈中元素个数In[9]:len(s)Out[9]:1In[10]:s.append(2)In[11]:s.append(3)#Take栈顶元素In[12]:s[-1]Out[12]:3一大波例子了解了栈的基本概念后，我们再来看几个例子，依次了解堆栈。括号匹配题目如果表达式中允许包含三括号(),[],{}，则嵌套顺序任意，例如：正确格式为{()[()]},[{({})}]格式错误[(]),[()),(()}写一个函数，判断一个表达式字符串是否正确匹配括号思路创建一个空栈，存放没有找到的左括号；String，当遇到一个左括号则入栈，遇到右括号则出栈匹配左括号；第二步，在空栈的情况下遇到右括号，表示缺少左括号，不匹配；两步遍历结束，栈不为空，表示缺少右括号，不匹配；解决代码，推荐在pycharm中打断点更好理解#!/use/bin/envpython#_*_coding:utf-8_*_LEFT={'(','[','{'}#leftbracket注册机GHT={')',']','}'}#右括号defmatch(expr):""":paramexpr:pass传入的字符串:return:返回是否正确"""stack=[]#Createastackforbracketsinexpr:#迭代所有传递的字符串ifbracketsinLEFT:#如果当前字符在左括号中stack.append(brackets)#将当前左括号压入堆栈elifbracketsinRIGHT:#如果是右括号ifnotstackornot1<=ord(brackets)-ord(stack[-1])<=2:#如果当前栈为空，()]#如果右括号减去左括号的值不小于等于2大于或等于1returnFalse#ReturnFalsestack.pop()#删除左括号returnnotstack#如果栈中没有值则返回True，否则返回Falseresult=match('[(){()}]')print(result)迷宫题用二维数组表示一个简单的迷宫，用0表示路径，1表示方块。鼠标可以在每个点移动相邻的南、东、西、北四个点。设计一个算法来模拟老鼠走迷宫并找到一条从入口到出口的路径。如图所示的正确路线如图中红线所示。思路是用一个栈记录鼠标从入口到出口的路径。到达某个点后，将该点压入栈的左侧，并将该点的值设置为1。表示已经通过；从相邻的四个点中选择任意一个可达点，前往该点；如果到达某一点后不去相邻的四个点，则说明进入了死胡同，此时应撤退。堆叠，退一步，尝试其他点；重复步骤2、3、4，直到找到出口；解决代码#!/use/bin/envpython#_*_coding:utf-8_*_definitMaze():""":return:Initializethemaze"""maze=[[0]*7for_inrange(5+2)]#使用列表推导创建一个7*7的二维数组，以保证迷宫四周都是墙。walls=[#记录墙的位置(1,3),(2,1),(2,5),(3,3),(3,4),(4,2),#(4,3),#if(4,3)的点也设置为墙，那么整个迷宫出不去，所以会返回一个空列表(5,4)]foriinrange(7):#设置的周围themazeaswallsmaze[i][0]=maze[i][-1]=1maze[0][i]=maze[-1][i]=1fori,jinwalls:#设置所有墙的点为1maze[i][j]=1returnmaze""[1,1,1,1,1,1,1][1,0,0,1,0,0,1][1,1,0,0,0,1,1][1,0,0,1,1,0,1][1,0,1,0,0,0,1][1,0,0,0,1,0,1][1,1,1,1,1,1,1]"""defpath(maze,start,end):""":parammaze:maze:paramstart:startpoint:paramend:endpoint:return:eachpointofwalking"""i,j=start#Decomposition起点坐标ei,ej=end#分解终点左侧stack=[(i,j)]#创建一个stack，让鼠标站在起点maze[i][j]=1#走过的路径设置为1whilestack:#栈不为空时继续走，否则退出i,j=stack[-1]#获取当前鼠标的位置pointif(i,j)==(ei,ej):break#如果鼠标找到出口fordi,djin[(0,-1),(0,1),(-1,0),(1,0)]:#左右上下ifmaze[i+di][j+dj]==0:#如果当前点可以走maze[i+di][j+dj]=1#设置当前指向1stack.append((i+di,j+dj))#将当前位置加入栈breakelse:#如果所有的点都不让进stack.pop()#返回上一步returnstack#If迷宫走不了，返回空栈Maze=initMaze()#初始化迷宫result=path(maze=Maze,start=(1,1),end=(5,5))#鼠标开始走迷宫打印（结果）#[(1,1),(1,2),(2,2),(3,2),(3,1),(4,1),(5,1),(5,2),(5,3),(4,3),(4,4),(4,5),(5,5)]后缀表达式求值题目在计算表达式时，编译器通常使用后缀表达式,不需要括号：编写程序实现后缀表达式求值函数思路是建立一个栈来存放要计算的操作数；遍历字符串，遇到操作数就将操作数压入栈中，遇到操作符将操作数弹出栈（n次），并进行相应的计算，计算结果为新的操作数压回栈中，等待用于计算按照上述过程遍历整个表达式，最后的结果只留在栈中；解决方法code#!/use/bin/envpython#_*_coding:utf-8_*_operators={#算子操作表'+':lambdaop1,op2:op1+op2,'-':lambdaop1,op2:op1-op2,'*':lambdaop1,op2:op1*op2,'/':lambdaop1,op2:op1/op2,}defevalPostfix(e):""":parame:postfixexpression:return:一般情况下，第一个元素在thestackisthecalculatedvalue"""tokens=e.split()#passover后缀表达式拆分成列表stack=[]fortokenintokens:#迭代列表中的元素iftoken.isdigit():#如果当前元素是一个数字栈。append(int(token))#追加到栈中eliftokeninoperators.keys():#如果当前元素是一个运算符f=operators[token]#在运算符运算表中得到对应的lambda表达式op2=stack.pop()#按照先进后出的原则，先让第二个元素出栈op1=stack.pop()#把第一个元素出栈stack.append(f(op1,op2))#将计算结果入栈returnstack.pop()#返回f栈元素中的第一个元素result=evalPostfix('234*+')print(result)#14KnapsackProblem有一个可以装10kg物品的背包，现在有6件物品：写出所有能装的解装满背包，比如item1+item5。解决方案代码#!/use/bin/envpython#_*_coding:utf-8_*_defknapsack(t,w):""":paramt:背包总容量:paramw:Itemweightlist:return:"""n=len(w)#可选的项数stack=[]#创建一个栈k=0#当前选中的项游标whilestackork
