数据结构第四讲栈应用及运用队列.pptVIP

case 3: //左边 if(a[x][y-1]!=1) { Push(ss,x,y-1); flag=true; if(c[x][y-1]==1) c[x][y]=0; } b[x][y]++; break; case 4://四周已经全部检查过 a[x][y]=1;//(x,y)在死路上 b[x][y]++; flag=true; c[x][y]=0; break; } } } printf(迷宫图为\n); for(int i=1;i6;i++) { for(int j=1;j6;j++) { printf( %d ,a[i][j]); } printf(\n); } printf(解为\n); for( i=1;i6;i++) { for( int j=1;j6;j++) { printf( %d ,c[i][j]); } printf(\n); } return 0; } 输出结果 栈的应用举例－－表达式计算 ＋ － × ／ ( ) # ＋ － × ／ ( = ) # = 当前运算符 栈顶运算符 表达式的处理算法 读入一个字符 1、如为操作数，直接压入操作数栈； 2、如当前运算符高于栈顶运算符，入栈； 3、如当前运算符低于栈顶运算符，栈顶运算符退栈， 同时操作数弹出两个数做相应运算，运算结果压回 操作数栈。当前运算符再与栈顶运算符比较； 4、如当前运算符等于栈顶运算符，且栈顶运算符为 “（”，当前运算符为“）”，则栈顶运算符退栈， 继续读下一符号； 5、如当前运算符等于栈顶运算符，且栈顶运算符为 “#”，当前运算符也为“#”，则栈顶运算符退栈， 结束； 步骤 表达式 STACK 输出 1 A＋(B－C／D)×E# # 2 ＋(B－C／D)×E# # A 3 (B－C／D)×E# # ＋ A 4 B－C／D)×E# # ＋( A 5 －C／D)×E# # ＋( AB 6 C／D)×E# # +(－ AB 7 ／D)×E# # ＋(－ ABC 8 D)×E# # ＋(－/ ABC 9 )×E# # ＋(－/ ABCD 步骤 表达式 STACK 输出 10 ×E# # ＋(－ ABCD/ 11 ×E# # ＋( ABCD/ － 12 ×E# # ＋ ABCD/ － 13 E# # ＋ × ABCD/ － 14 # # ＋ × ABCD/ －E 15 # # + ABCD/ －E × 16 # # ABCD/ －E × ＋ 队列 队列的定义 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 　　例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 　　当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的。 下图是队列的示意图： 　　　　　 　　　　　　 　　 　　　　　 非循环队列和循环队列 　　队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值在队列初始化时均应置为０。入队时将新元素插入所指的位置，然后加１。出队时，删去所指的元素，然后加１并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。 　０　１　２　３ 0 1 2 3 　 Front rear a b c Front rear (a)队列初始为空　　　　　　（b）A,B,C入队 　０　１　２　３　　　０　１　２　３ b c front