[工学]chap003 栈与队列.ppt

栈和队列的特点 ’后进先出’，栈又称作后进先出表（LIFO，即Last In First Out）。 ’先进先出’，队列又称作先进先出表（FIFO，即First In First Out）。 如何从后缀式求值？ 先找运算符， 再找操作数 空队列 队列中有一个元素 队列满 stack 举例：10进制向k进制转换 #include stack void baseChange(int n, int k){ stackint S; while(n0){ S.push(n%k); n = n/k; } while(S.empty()==false){ coutS.top(); S.pop(); } } queue举例：舞伴 #include queue struct Partner{ string male, female; }; queuestring ManQ, WomanQ; queuePartner DancerQ; void Prepare(int ManNum, int WomanNum) { string name; for(int i=0; iManNum; i++){ // 输入男子名字,并入队 cinname; ManQ.push(name); } for(int i=0; iWomanNum; i++) { //输入女子名字,并入队 cinname; WomanQ.push(name); } } queue举例：求迷宫最短路径的长度 课后建议： Stack： Hdoj 2163, 1022, 2031,1702,1990,1237 HLoj 1013,1207, 8806 queue Hdoj 1253 Hdoj 1372 Hdoj 1702，1908，1972（较难） HLoj 8805,8807,8808 void DancePartner (int count){ // count 为舞曲的播放轮次 string sMale, sFemale; Partner partner; for(int i=1; i=count; i++){ // music begin cout“当前轮次：“iendl; while(!ManQ.Empty() !WomanQ.Empty()) { ManQ.DeQueue(sMale); WomanQ.DeQueue(sFemale); partner.male=sMale; partner.female=sFemale; DancerQ.EnQueue(partner); coutsMale “ and “sFemaleendl; } //男子或者女子队列中有空就结束配对 // music end while(!DancerQ.Empty ()) { DancerQ.DeQueue (partner); ManQ.EnQueue(partner.male); WomanQ.EnQueue(partner.female); }//舞曲结束，配对拆开进各自队列 } } 要求设计一个算法, 计算从迷宫入口（1,1）到出口(M,N)的最短路径的长度。 算法的基本思想为：从迷宫入口点出发，向四周有哪些信誉好的足球投注网站，记下所有一步能到达的坐标点；然后依次再从这些点出发，再记下所有一步能到达的坐标点，…，依此类推，直到迷宫的出口点为止。这样就找到了一条迷宫的最短路径(因为距离近的先试探)。 在有哪些信誉好的足球投注网站过程中必须记下每一个可到达的坐标点，以便从这些点出发继续向四周有哪些信誉好的足球投注网站。由于先到达的点会得到优先处理，故使用“先进先出”数据结构——队列来保存已到达的坐标点。 队列举例2 求迷宫的最短步数 1）表示迷宫的数据结构： 设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1; 其中：0表示通路，1表示不通。 当从某点出发试探时，中间点有4个方向可以试探（见后图），而四个角点有2个方向，其它边缘点有3个方向。 迷宫的定义如下： const int M=6; // 迷宫的实际行 const int N=8; // 迷宫的实际列 int maze [M][N] ; 实现该算法需要解决的四个问题 如图表示的迷宫是一个6×8的迷宫。 入口坐标为（0，0），出口坐标为（5，7）。 T 1 1 0 0 1 1 0 5 0 0 0 1 1 0 0 1 4 1 1 0 0 1 1