数据结构栈与队列.pptVIP

例——坦克大战地图空地石墙、河流砖墙——可以被打坏初始位置、目标位置每一回合向4个方向走1步向4个方向发射子弹，子弹会按此方向直线前进，知道撞击到墙（2种）问题最少经过多少回合到达目标位置？例——坦克大战思路有必要发射子弹吗？想要打掉某个砖墙，并且想从该砖墙处走过花2个回合可通过砖墙带权值的迷宫问题空地——1回合砖墙——2回合河流、石墙——障碍例——坦克大战原始迷宫问题BFS选择队列头节点该节点距离可保证最短带权值的迷宫问题用优先队列代替队列每次选取的节点也可保证距离最短例——坦克大战初始：que.EnPQue(x0,y0,0)，inQ(x0,y0)=true，其余inQ=falsewhile(!que.Empty()) (x,y,d)=que.DePQue()//d是队列所有节点中最小的 if(x,y)为目标位置returnd for(xi,yi)in(x,y)的4个方向 ifinQ(xi,yi)==false且非障碍 if(xi,yi)是空地que.EnPQue(xi,yi,d+1) elseque.EnPQue(xi,yi,d+2) //砖墙 inQ(xi,yi)=true return-1 例——Zipper有三个串A,B,CStringA:cat

StringB:tree

StringC:tcraete如果前两个串在第三个中，并且两个串本身的顺序在第三个串中不变，则认为前两个串可以组成第三个串。例——Zipper如上例：StringA:cat

StringB:tree

StringC:tcraete而下面的方案就不行：StringA:cat

StringB:tree

StringC:catrtee例——ZipperC串的最后一个字母一定是A串或者B的最后一个字母可通过判断，知道C串的最后一个字母属于A还是B若同时将这个字母从A或者B，C中删去，则会得到一组新的串A’，B’，C’StringA:cat

StringB:tree

StringC:tcraeteStringA’:cat

StringB’:tre

StringC’:tcraet例——ZipperStringA’:cat

StringB’:tre

StringC’:tcraet可以看出新的串A’，B’，C’同样也符合题意例——Zipper以下函数判断长度为i的串A和长度为j的串B可否组成串C长度为i的串A和长度为j的串B组成的C的长度为i+jboolCalc(inti,intj) if(i==0j==0)returntrue if(c[i+j-1]==a[i-1]c[i+j-1]!=b[j-1]) returnCalc(i-1,j) if(c[i+j-1]!=a[i-1]c[i+j-1]==b[j-1]) returnCalc(i,j-1) if(c[i+j-1]==a[i-1]c[i+j-1]==b[j-1]) returnCalc(i-1,j)||Cal(i,j-1) returnfalse栈与队列栈特点后进先出（LIFO）底部元素透明交卷子、堆盘子作用：保护现场实现：顺序表stack、栈顶指针top链式栈基本操作入栈、出栈队列特点先进先出（FIFO）公平原则食堂排队、吸管里的饮料作用：维持顺序实现：顺序表queue、队首指针front、队尾指针rear环形队列：减少空间浪费链式队列基本操作入队、出队例——铁轨问题一条铁轨，A进，B出可能的出站序列？例1：1,2,3,4,5yes；例2：5,4,3,2,1yes例3：3,2,4,5,1yes；例4：3,1,4,5,2no例——铁轨问题后进先出——栈x—A站最前方火车编号若A站已无火车，则x=0y—按照出站序列，下一个需进入B站的火车编号若火车已全部驶入B站，则y=0数组d模拟栈—当前停留在站中的火车xy1243512435例——小球钟含有小球的四个部件分钟轨道：ball[1..4]第5个小球滚入时，轨道过重倾斜，原先的4个小球反向落入底部轨道末端，第5个小球滚入5分钟轨道5分钟轨道：ball[1..11]小时轨道：ball[1..11]