1、第第3章章 栈和队列栈和队列3.1 栈栈3.2 队列队列3.3 栈与队列的应用栈与队列的应用23.1 栈栈ADT栈栈n栈（栈（Stack）u只允许在表的一端进行插只允许在表的一端进行插入和删除的线性表入和删除的线性表u允许插入和删除的一端称允许插入和删除的一端称为栈顶（为栈顶（top），另一端称），另一端称为栈底（为栈底（bottom）u不含元素的栈称为空栈不含元素的栈称为空栈 u插入：进栈，入栈插入：进栈，入栈 删除：出栈，退栈删除：出栈，退栈u特点特点后进先出（后进先出（LIFO）先进后出（先进后出（FILO）33.1 栈栈ADT栈栈n问题问题u有三个元素按有三个元素按 a1, a2, a
2、3 的次序依次进栈，其出栈的次序依次进栈，其出栈次序有几种可能？次序有几种可能？出栈次序：出栈次序： a1，a2，a3 a1，a3，a2 a2，a1，a3 a2，a3，a1 a3，a2，a1注意：注意：栈只是对表插入和删除操作的位置进行了限栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。制，并没有限定插入和删除操作进行的时间。43.1 栈栈ADT栈栈n栈的抽象数据类型栈的抽象数据类型ADT Stack Data 数据项列表数据项列表 top：栈顶位置：栈顶位置 Operations Constructor Process：创建一个空栈：创建一个空栈 IsEmpty
3、 Process：判断栈是否为空：判断栈是否为空 Output：如果栈为空，则返回：如果栈为空，则返回true，否则返回，否则返回false GetTop Process：取栈顶元素：取栈顶元素 Output：返回栈顶元素：返回栈顶元素53.1 栈栈ADT栈栈 Length Process：求栈中元素个数：求栈中元素个数 Output：返回栈中元素的个数：返回栈中元素的个数 Push Input：要添加的数据元素：要添加的数据元素 Process：向栈中添加元素：向栈中添加元素x，即进栈，即进栈 Pop Process：删除栈顶元素，即出栈：删除栈顶元素，即出栈 Output：返回栈顶元素：返
4、回栈顶元素 Clear Process：删除栈中所有元素并置新的栈顶：删除栈中所有元素并置新的栈顶 /Stack63.1 栈栈栈的实现栈的实现顺序栈顺序栈n顺序栈的定义顺序栈的定义如何改造数组实现栈的顺序存储？如何改造数组实现栈的顺序存储？ 0 1 2 3 4 5 6附设指针附设指针top指示栈顶元指示栈顶元素在数组中的位置。素在数组中的位置。 top确定用数组的哪确定用数组的哪一端表示栈底。一端表示栈底。a1a2a373.1 栈栈栈的实现栈的实现顺序栈的基本操作顺序栈的基本操作出栈：先出栈出栈：先出栈 top再减再减1进栈：进栈：top先加先加1 再进栈再进栈栈空：栈空：top= -1 0
5、1 2 3 4 5 6 7 8a1topa2topa3top栈满：栈满：top=MaxStackSize-1top top83.1 栈栈栈的实现栈的实现const int MaxStackSize=50; /栈中能容纳最大元素个数栈中能容纳最大元素个数class SeqStack DataType StackListMaxStackSize; int top; public: Stack (); /构造函数，初始化构造函数，初始化top bool IsEmpty (); /判断栈的状态是否为空判断栈的状态是否为空 bool IsFull (); DataType GetTop (); /取栈顶
6、元素取栈顶元素 void Push (const DataType x); /入栈入栈 DataType Pop (); /出栈出栈 void Clear (); /栈清空栈清空;/ SeqStack93.1 栈栈栈的实现栈的实现n顺序栈的操作的实现顺序栈的操作的实现u构造函数，初始化一个空栈构造函数，初始化一个空栈 Stack ( ) StackList = new DataTypeMaxStackSize; top=-1; / Stack103.1 栈栈栈的实现栈的实现u判断栈是否为空判断栈是否为空 bool IsEmpty ( ) if (top=-1) return true; els
7、e return false; / IsEmpty113.1 栈栈栈的实现栈的实现u判断栈是否已满判断栈是否已满 bool IsFull( ) if (top=MaxStackSize-1) return true; else return false; / IsFull123.1 栈栈栈的实现栈的实现u取栈顶元素取栈顶元素 DataType GetTop( ) if (IsEmpty( ) cout”栈空！栈空！”endl; return nulldata; return StackListtop; 133.1 栈栈栈的实现栈的实现u向栈顶压入元素向栈顶压入元素 void Push (Dat
8、aType x) if (IsFull( ) cout”栈满！栈满！”endl; else StackList+top = x; / Push143.1 栈栈栈的实现栈的实现u删除栈顶元素删除栈顶元素 DataType Pop( ) if (IsEmpty( ) cout”栈空！栈空！”next=NULL; /创建头结点创建头结点 void Push (DataType data);183.1 栈栈栈的实现栈的实现 DataType Pop ( ); DataType GetTop ( ); void Clear ( ) top-next=NULL; bool IsEmpty ( ) retu
9、rn top -next= = NULL; ;/ LinkStack193.1 栈栈栈的实现栈的实现n类中操作算法的描述类中操作算法的描述u入栈操作入栈操作 void Push (DataType item ) p=new StackNode ( item); p-next=top-next; top-next=p; /Push203.1 栈栈栈的实现栈的实现u出栈操作出栈操作 DataType pop ( ) if ( top-next!=NULL ) p=top-next; retvalue=p-data; /暂存栈顶数据暂存栈顶数据 top -next=p-next; /修改栈顶指针修改
10、栈顶指针 delete p; /释放，返回数据释放，返回数据 return retvalue; else /栈空的情况栈空的情况 cout”the stack is empty!”next!=NULL) return top-next-data; else /栈空的情况栈空的情况 cout”the stack is empty!”1时，先把塔时，先把塔 A 上的上的 n-1 个圆盘移到塔个圆盘移到塔 B，然后将，然后将 n 号盘从塔号盘从塔 A 移到塔移到塔 C，再将，再将 n-1 个圆盘从塔个圆盘从塔 B移到塔移到塔C。即把求解即把求解 n 个圆盘的个圆盘的Hanoi问题转化为求解问题转化为
11、求解 n-1 个圆盘个圆盘的的 Hanoi 问题，依次类推，直至转化成只有一个圆盘问题，依次类推，直至转化成只有一个圆盘的的 Hanoi 问题。问题。313.1 栈栈栈与递归栈与递归323.1 栈栈栈与递归栈与递归u解决汉诺塔问题的算法解决汉诺塔问题的算法 main( ) int n; coutn; hanoi( n ,A,B,C ); void hanoi (int n,char x,char y,char z) if (n=1) move (1,x,z); else hanoi (n-1,x,z,y); move (n,x,z); hanoi (n-1,y,x,z); 333.1 栈栈栈与
12、递归栈与递归递归过程和运行时栈递归过程和运行时栈n递归函数的运行轨迹递归函数的运行轨迹u描述方法描述方法1）写出函数当前调用层执行的各语句，并用箭头表示语）写出函数当前调用层执行的各语句，并用箭头表示语句的执行次序；句的执行次序；2）对函数的每个递归调用，写出相应的函数调用，从调）对函数的每个递归调用，写出相应的函数调用，从调用处画一条箭头指向被调用函数入口，表示调用路线，用处画一条箭头指向被调用函数入口，表示调用路线，从被调用函数末尾处画一条箭头指向调用语句的下面，从被调用函数末尾处画一条箭头指向调用语句的下面，表示返回路线；表示返回路线；3）在返回路线上标出本层调用所得的函数值。）在返回路
13、线上标出本层调用所得的函数值。 343.1 栈栈栈与递归栈与递归un=3 时汉诺塔递归算法的运行轨迹时汉诺塔递归算法的运行轨迹Hanoi ( 3, A, B, C）Move ( A, 3, C )Hanoi ( 2, A, C, B）Hanoi ( 2, A, C, B）Hanoi ( 3, A, B, C）Hanoi ( 1, A, B, C）递归第三层递归第三层递归第二层递归第二层递归第一层递归第一层Move ( A, 1, C )Hanoi ( 1, C, A, B）Move ( C, 1, B )Hanoi ( 1, B, C, A）Move ( B, 1, A )Hanoi ( 1,
14、 A, B, C）Move ( A, 1, C )Hanoi ( 1, A, B, C）Move ( A, 2, B )Hanoi ( 1, C, A, B）Hanoi ( 2, B, A, C）Hanoi ( 1, B, C, A）Move ( B, 2, C )Hanoi ( 1, A, B, C）Hanoi ( 2, B, A, C）(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)353.1 栈栈栈与递归栈与递归n递归函数的内部执行过程递归函数的内部执行过程u当一个函数在运行期间调用另一个函数时，在运当一个函数在运行期间调用另一个函数时，在运
15、行被调用函数之前，系统需要将实参和返回值地行被调用函数之前，系统需要将实参和返回值地址等数据传递给被调函数，当函数调用时，这些址等数据传递给被调函数，当函数调用时，这些数据与局部变量一起构成一条数据与局部变量一起构成一条“工作记录工作记录”，被，被压入系统提供的栈（运行时栈）。压入系统提供的栈（运行时栈）。u当被调函数返回时，按照返回地址执行调用函数当被调函数返回时，按照返回地址执行调用函数中下一条指令，同时释放栈中相应的工作记录。中下一条指令，同时释放栈中相应的工作记录。363.1 栈栈栈与递归栈与递归主程序主程序Call proc1rproc1proc2proc3sCall proc2tC
16、all proc3系统运行时栈系统运行时栈局部变量局部变量返回地址返回地址实际参数实际参数工作记录工作记录373.1 栈栈栈与递归栈与递归u递归调用的内部执行过程递归调用的内部执行过程运行开始时，首先为递归调用建立一个系统运行时栈；运行开始时，首先为递归调用建立一个系统运行时栈；每次执行递归调用之前，把递归函数的值参和局部变每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址等组成的工作记录量的当前值以及调用后的返回地址等组成的工作记录压入栈中；压入栈中；每次递归调用结束后，将栈顶元素出栈，使相应的值每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前
17、的值，然后转向返回地址参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。指定的位置继续执行。383.1 栈栈栈与递归栈与递归un=3 时汉诺塔递归算法的部分执行过程时汉诺塔递归算法的部分执行过程 main() hanoi ( 3,A,B,C ); void hanoi(int n,char x,char y,char z) if (n=1) move (1,x,z); else hanoi (n-1,x,z,y); move (n,x,z); hanoi (n-1,y,x,z); 0123456789ABC321返回返回地址地址zyxn 3ABC 01CAB82ACB61ABC
18、612393.1 栈栈栈与递归栈与递归n递归总结递归总结u递归是重要的设计和编程工具，使许多算法变得递归是重要的设计和编程工具，使许多算法变得简单，易于设计和实现。简单，易于设计和实现。 优点优点u递归使算法的时间复杂度和空间复杂度同时增大，递归使算法的时间复杂度和空间复杂度同时增大，有时会导致效率急剧恶化，或者溢出系统栈。有时会导致效率急剧恶化，或者溢出系统栈。 缺点缺点u使用递归时应该权衡效率和设计的关系。在有足使用递归时应该权衡效率和设计的关系。在有足够的空间并且时间要求不高的情况下可以使用递够的空间并且时间要求不高的情况下可以使用递归。归。403.2 队列队列ADT定义定义n定义定义u
19、队列（队列（Queue）是只允许在表的一端进行删除，而）是只允许在表的一端进行删除，而在另一端进行插入的线性表。在另一端进行插入的线性表。允许删除的一端叫做队头（允许删除的一端叫做队头（front）允许插入的一端叫做队尾（允许插入的一端叫做队尾（rear）u特点特点先进先出（先进先出（FIFO，First In First Out）a1 a2 a3. an 入队入队出队出队frontrear413.2 队列队列ADT定义定义nADT队列的定义队列的定义ADT Queue Data 数据项列表数据项列表 front：队列中第一个元素的位置：队列中第一个元素的位置 rear：队列中最后一个元素的位
20、置：队列中最后一个元素的位置 Operations Constructor Process：初始化队首和队尾：初始化队首和队尾 IsEmpty Process：判断是否为空队列：判断是否为空队列 Output：若队列空，返回：若队列空，返回true，否则返回，否则返回false423.2 队列队列ADT定义定义 Length Process：求队列中元素个数：求队列中元素个数 Output：返回队列的元素个数：返回队列的元素个数 Front Process：取出队头元素：取出队头元素 Output：返回队头元素：返回队头元素 Enter Input：要进入队列的元素：要进入队列的元素 Proc
21、ess：在队尾插入新的元素：在队尾插入新的元素 Leave Process：删除队头元素：删除队头元素 Output：返回队头元素：返回队头元素 ClearQueue Process：删除队列中所有元素并设置初始状态：删除队列中所有元素并设置初始状态/Queue433.2 队列队列队列的实现队列的实现顺序队列顺序队列n顺序队列的定义顺序队列的定义const int MaxQSize=50;class SeqQueue int front, rear; DataType QueueListMaxQSize; public: SeqQueue();/构造函数构造函数,初始化数据成员初始化数据成员
22、void Enter(DataType item); DataType Leave(); void Clear(); DataType Front(); int Length(); bool IsEmpty(); bool IsFull(); ;/ SeqQueue443.2 队列队列队列的实现队列的实现n顺序队列的进队和出队顺序队列的进队和出队 u设两个指针设两个指针 front 和和 rear（初始（初始 frontrear0）ufront 指向队头元素，出队时先取出，再指向队头元素，出队时先取出，再 front+1urear 指向队尾元素的下一个位置，进队时先将新元素加入，指向队尾元素的
23、下一个位置，进队时先将新元素加入，再再 rear+1u队空条件：队空条件：front=rear，此时不能出队，此时不能出队u队满条件：队满条件：rear=MaxQSize，此时不能进队，此时不能进队图3.10 头尾指针和队列中元素的变化rear543210543210d1d2d3543210d1d2d3d4d5d6frontfrontrearrear543210d5d6rearfront(a) 空队列(b) d1,d2,d3入队(c) d4,d5,d6入队(d) d1,d2,d3,d4出队453.2 队列队列队列的实现队列的实现u存在问题存在问题 rear=MaxQSize时，再有元素进队时，
24、再有元素进队发生溢出发生溢出l当当front= 0真溢出真溢出l当当front 0假溢出假溢出解决假溢出的方案解决假溢出的方案固定队头，出队时，剩余元素均向前固定队头，出队时，剩余元素均向前移动移动固定队尾，入队时，剩余元素均向前固定队尾，入队时，剩余元素均向前移动移动循环队列：把队列设想成环形，让循环队列：把队列设想成环形，让 0 接在接在 MaxQSize-1 后后更好更好图3.10 头尾指针和队列中元素的变化rear543210543210d1d2d3543210d1d2d3d4d5d6frontfrontrearrear543210d5d6rearfront(a) 空队列(b) d1,
25、d2,d3入队(c) d4,d5,d6入队(d) d1,d2,d3,d4出队图3.10 头尾指针和队列中元素的变化rear543210543210d1d2d3543210d1d2d3d4d5d6frontfrontrearrear543210d5d6rearfront(a) 空队列(b) d1,d2,d3入队(c) d4,d5,d6入队(d) d1,d2,d3,d4出队463.2 队列队列队列的实现队列的实现n循环队列循环队列u也是队列的顺序存储结构也是队列的顺序存储结构u实现实现利用利用“模模”运算运算入队入队lQueueListrear=item; rear=(rear+1)%MaxQSi
26、ze; 出队出队litem=QueueListfront; front=(front+1)% MaxQSize; 01frontrear.MaxQSize-1473.2 队列队列队列的实现队列的实现u仍然存在问题仍然存在问题如何判断队列是如何判断队列是“空空”还是还是“满满”？3.11循环队列示意图(a)一般情况 (b)队满时 4 5 32 1 0 front rear (c)队空时 45 3 21 0 d1 d2 d3 d4 d5 d6 frontrear 453 2 1 0front rear d1 d2 d3 队空：队空：front=rear队满：队满：front=rear483.2 队
27、列队列队列的实现队列的实现u三种处理方法三种处理方法给队列设一个标志位以区别队列是空还是满给队列设一个标志位以区别队列是空还是满给队列增加一个统计元素个数的变量给队列增加一个统计元素个数的变量 count，当，当count=MaxQSize 时队满；时队满；count=0 时队空时队空少用一个变量，约定少用一个变量，约定 rear+1 等于等于 front（从后面赶上队（从后面赶上队头指针）为队满的情况头指针）为队满的情况l队满条件：队满条件：( rear+1 ) % MaxQSize=frontl队空条件：队空条件： frontrear493.2 队列队列队列的实现队列的实现u循环队列类的操
28、作算法描述循环队列类的操作算法描述构造函数，初始化一个空队列构造函数，初始化一个空队列 SeqQueue () front=rear=0; / SeqQueue入队操作入队操作 void Enter (DataType item) if ( (rear+1)%MaxQSize=front ) /判断是否队满判断是否队满 cout”队列已满，不能入队！队列已满，不能入队！”endl; else QueueListrear=item; rear=(rear+1)%MaxQSize; / Enter503.2 队列队列队列的实现队列的实现出队操作出队操作 DataType Leave() if (
29、front=rear ) /判断是否队空判断是否队空 cout”队列已空，不能出队队列已空，不能出队”next = NULLfront图图 3.13 链队列链队列a1a2a3a4 rear533.2 队列队列队列的实现队列的实现u链队列描述链队列描述 class QNode /链队结点的类链队结点的类 DataType data; QNode *next; public: QNode(DataType item=nulldata) data= item; next=NULL; friend class LinkQueue; ; / QNode543.2 队列队列队列的实现队列的实现class
30、LinkQueue QNnode *front, *rear; public: LinkQueue() rear =front=new QNode(); void Enter (DataType item ); DataType Leave(); DataType Front(); void Clear () front-next = rear-next = NULL; bool IsEmpty () return front next= NULL; ; / LinkQueue 553.2 队列队列队列的实现队列的实现u链队列基本操作的算法描述链队列基本操作的算法描述入队操作入队操作 void
31、 Enter ( DataType item ) rear-next = new QNode ( item); rear=rear-next; /Enter563.2 队列队列队列的实现队列的实现出队操作出队操作 DataType Leave( ) if (!IsEmpty ( ) ) /判队不空判队不空 p = front-next; DataType retvalue = p-data;/保存队头的值保存队头的值 front-next = p-next; delete p; if ( front-next=NULL ) /删除队列中唯一结点后，重新设置删除队列中唯一结点后，重新设置rear
32、 rear=front; return retvalue; else cout” 队列空队列空!”next-data; else cout”队列空，无队头元素！队列空，无队头元素！”0 时重复（时重复（1），（），（2） （1）若）若N0，则将，则将 N % r 压入栈压入栈 s 中，执行（中，执行（2）；）； 若若N0，将栈，将栈 s 的内容依次出栈，算法结束。的内容依次出栈，算法结束。（2）用）用 N/r 代替代替 N613.3 栈与队列的应用栈与队列的应用u算法描述算法描述 void conversion ( int N，int r ) SeqStack s; int x; while
33、( N ) s.Push (N % r ); N=N / r ; while (! s.IsEmpty ( ) x=s.Pop ( ) ; coutx ; /while /conversion623.3 栈与队列的应用栈与队列的应用n应用应用2：表达式求值：表达式求值u表达式表达式表达式由操作数（表达式由操作数（operand）、运算符（）、运算符（operator）和）和分界符（分界符（delimiter）组成）组成l操作数：变量或常数操作数：变量或常数l运算符：算术运算符、关系运算符、逻辑运算符运算符：算术运算符、关系运算符、逻辑运算符l分界符：括号分界符：括号表达式的表示方法表达式的表示
34、方法l前缀表达式前缀表达式l中缀表达式中缀表达式l后缀表达式后缀表达式633.3 栈与队列的应用栈与队列的应用u后缀表达式（逆波兰式）求值后缀表达式（逆波兰式）求值后缀表达式不含括号后缀表达式不含括号运算符放在两个操作数后面运算符放在两个操作数后面例例l中缀表达式中缀表达式 2 + ( 3 * 8 4 ) / 5l后缀表达式后缀表达式 2 3 8 * 4 - 5 / +所有的求值计算皆按运算符出现的顺序，严格从左向所有的求值计算皆按运算符出现的顺序，严格从左向右进行右进行比中缀表达式的计算简单比中缀表达式的计算简单643.3 栈与队列的应用栈与队列的应用算法思想算法思想l设一个栈；设一个栈；l
35、顺序扫描后缀表达式的每一项，根据其类型做如下顺序扫描后缀表达式的每一项，根据其类型做如下处理：处理：p如果该项是操作数，则将其压入栈顶；如果该项是操作数，则将其压入栈顶；p如果该项是运算符如果该项是运算符 ，则连续从栈顶退出两个操，则连续从栈顶退出两个操作数作数 x 和和 y，形成运算指令，形成运算指令 x y，并将结果重新，并将结果重新压入栈顶。压入栈顶。l表达式所有项扫描并处理完后（以符号表达式所有项扫描并处理完后（以符号“=”为结为结束），栈顶存放的就是计算结果。束），栈顶存放的就是计算结果。653.3 栈与队列的应用栈与队列的应用栈栈输入输入操作序列操作序列 A B C D + E F
36、 / PushABCDC DPushPushPop, Pop, PushPushPop, Pop, PushB (C D)Pop, Pop, PushA+ B (C D)EFE/FPushPushPop, Pop, PushPop, Pop, PushA+B (C-D) E/F663.3 栈与队列的应用栈与队列的应用u中缀表达式的计算中缀表达式的计算中缀表达式的计算次序中缀表达式的计算次序l根据运算符优先级由高到低的顺序进行运算根据运算符优先级由高到低的顺序进行运算l有括号出现时先算括号内的，后算括号外的，多层有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行括号，由内向外进行l乘
37、方连续出现时先算最右面的乘方连续出现时先算最右面的计算方法计算方法1l按中缀表达式的顺序计算（本书）按中缀表达式的顺序计算（本书）计算方法计算方法2l先将中缀表达式转换为后缀表达式先将中缀表达式转换为后缀表达式l再进行后缀表达式求值再进行后缀表达式求值673.3 栈与队列的应用栈与队列的应用计算方法计算方法1l根据上述三条运算规则，在运算的每一步中，对任根据上述三条运算规则，在运算的每一步中，对任意相继出现的运算符意相继出现的运算符 1和和 2，都要比较优先关系，都要比较优先关系l运算符间的优先关系见下表运算符间的优先关系见下表 2 1 * * / + / + ( )( ) # # * * /
38、 / + + （ ） # # = = =683.3 栈与队列的应用栈与队列的应用l算法思想算法思想p设定两栈：操作数栈设定两栈：操作数栈 OPND，运算符栈，运算符栈 OPTRp栈初始化：设操作数栈栈初始化：设操作数栈 OPND 为空；运算符栈为空；运算符栈 OPTR 的栈底元素为表达式起始符的栈底元素为表达式起始符 #；p依次读入字符：是操作数则入依次读入字符：是操作数则入OPND栈，是运算符则栈，是运算符则要判断（设要判断（设OPTR 的栈顶元素为的栈顶元素为 1 ，当前读入的运，当前读入的运算符为算符为 2 ）： 1）if 1 2，则退栈、计算，结果压入，则退栈、计算，结果压入 OPND
39、栈；栈；p重复，直至读入字符和重复，直至读入字符和OPTR的栈顶元素均为的栈顶元素均为 #，此时此时OPND 的栈顶即为计算结果的栈顶即为计算结果693.3 栈与队列的应用栈与队列的应用OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*, (37-2)#Push(opnd,7)#,*, (3,7-2)#Push(optr,-)#,*, (, -3,72)#Push(opnd,2)#,*, (, -3,7,2)#Operate(7-2)#,*, (3,5)#Pop(opt
40、r)#,*3,5#Operate(3*5)#15#GetTop(opnd)703.3 栈与队列的应用栈与队列的应用l算法描述算法描述void EvaluateExpression( OperandType &result) /s1为操作对象栈，为操作对象栈，s2为运算符栈，为运算符栈，OP为运算符集合为运算符集合 SeqStack s1,s2; s2.Push(#); c=getchar(); while (c!=#) & (s2.GetTop()!=#) if (!In(c,OP) s1.Push(c); c=getchar(); 713.3 栈与队列的应用栈与队列的应用 else swit
41、ch (compare (s2.GetTop(), c) case : temat=s2.Pop(); b=s1.Pop(); a=s1.Pop(); result= Operate(a,temat,b); s1.Push(result); c=getchar();break; /switch /while result=s1.GetTop(); /EvaluateExpression723.3 栈与队列的应用栈与队列的应用计算方法计算方法2将中缀表达式转换成后缀表达式将中缀表达式转换成后缀表达式l设置一个栈，栈底元素为表达式起始符设置一个栈，栈底元素为表达式起始符 #；l依次读入中缀表达式的
42、每一字符，是操作数则直接依次读入中缀表达式的每一字符，是操作数则直接输出，是运算符则要判断（设栈顶元素为输出，是运算符则要判断（设栈顶元素为 1 ，当前，当前读入的运算符为读入的运算符为 2 ）：1）if 1 2， 则退栈，并输出；则退栈，并输出；3）if 1= 2 且不为且不为#， 则退栈，但不输出，若退则退栈，但不输出，若退出的是出的是 ( 则读入下一字符则读入下一字符 ；l重复，直至读入字符和栈顶元素均为重复，直至读入字符和栈顶元素均为 #，算法结，算法结束，此时输出序列即为后缀表达式束，此时输出序列即为后缀表达式733.3 栈与队列的应用栈与队列的应用n应用应用3：迷宫求解问题：迷宫求
43、解问题 入口入口出口出口743.3 栈与队列的应用栈与队列的应用u基本思想基本思想从入口出发，沿某一方向向前探索从入口出发，沿某一方向向前探索l若当前位置若当前位置“可通可通”，则纳入路径，继续前进；，则纳入路径，继续前进；l若当前位置若当前位置“不可通不可通”，则换方向继续探索，则换方向继续探索;若四周若四周“均无通路均无通路”，则沿原路退回到前一位置，换，则沿原路退回到前一位置，换方向继续探索方向继续探索753.3 栈与队列的应用栈与队列的应用u迷宫求解问题的迷宫求解问题的递归递归算法算法算法中用到的数据结构算法中用到的数据结构lint Mazem+2p+2：表示迷宫：表示迷宫pm表示行数
44、，表示行数，p表示列数表示列数p第第0、m+1行，第行，第0、p+1 列是迷宫的围墙列是迷宫的围墙pMazeij=1时，表示该位置是墙壁，不能通行时，表示该位置是墙壁，不能通行Mazeij=0时，表示该位置是通路时，表示该位置是通路lint markm+2p+2：标志矩阵：标志矩阵p初始为初始为0，当某一位置，当某一位置ij走过时，置走过时，置 markij=1763.3 栈与队列的应用栈与队列的应用loffsets move4：表示方向：表示方向Struct offsets int a, b; char *d; moveq.dmoveq.amoveq.bE(东东)01S(南南)10W(西西)
45、0-1N(北北)-10N(北北)i-1, jW(西西)i, j-1当前位置当前位置i, jE(东东)i, j+1S(南南) i+1, j773.3 栈与队列的应用栈与队列的应用递归函数递归函数int SeekPath (int x, int y) int i,g,h; char *d; if ( x=m & y=p ) return 1; for (i=0; i4; i+) g=x+movei.a; h=y+movei.b; d=movei.dir; if ( !Mazegh & !markgh ) markgh=1; if ( SeekPath(g,h) ) cout“(“g“,”h“),”
46、“Direction”dir“,”; return 1; if ( x=1&y=1 ) cout“no pathvin Maze”endl; return 0;783.3 栈与队列的应用栈与队列的应用递归函数的主程序递归函数的主程序const int m=12, p=15;void main( ) int Mazem+2p+2, markm+2p+2; int move4= 0,1,”E”, 1,0,”S”,0,-1,”W”, -1,0,”N” ; for (int i=0;im+2;i+) for(int j=0;jMazeij; for(int i=0;im+2;i+) for(int j
47、=0;jp+2;j+) markij=0; mark11=1; if ( SeekPath (1,1) ) cout“(”1“,”1“),”“Direction”“E”endl;793.3 栈与队列的应用栈与队列的应用u迷宫求解的迷宫求解的非递归非递归算法算法struct Block int ord; /通道块的序号通道块的序号 PosType seat; /通道块在迷宫中的坐标位置通道块在迷宫中的坐标位置 int direction; /从此通道块走向下一通道块的方向从此通道块走向下一通道块的方向 ;class Maze struct Block e; public: bool MazePa
48、th(PosType start, PosType end); ;803.3 栈与队列的应用栈与队列的应用bool Maze:MazePath(PosType start, PosType end) SeqStack s; curpos=start; /当前位置为入口位置当前位置为入口位置 curstep=1; /探索第一步探索第一步 do if ( Pass(curpos) /当前位置可以通过且未走过当前位置可以通过且未走过 footprint(curpos); /留下足印留下足印 e=new Block(curstep,curpos,1); s.Push(e); /加入路径加入路径 if
49、(curpos=end) return(true); /到达终点到达终点 curpos=NextPos(curpos,1); /下一个位置是当前位置的东邻下一个位置是当前位置的东邻 curstep+; 813.3 栈与队列的应用栈与队列的应用 else /当前位置不通当前位置不通 if ( !s.IsEmpty() e=s.Pop(); while(e.direction=4 & !s.IsEmpty() MarkPrint(e.seat); e=s.Pop(); /留下不能通过的标记并后退留下不能通过的标记并后退 /end while if (e.direction4) e.directio
50、n+; s.Push(e); /换下一个方向探索换下一个方向探索 curpos=NextPos(e.seat, e.direction); /新位置是旧的相邻块新位置是旧的相邻块 /end if /end if /end else while(!s.IsEmpty(); return(false);/ Mazth 823.3 栈与队列的应用栈与队列的应用队列的应用队列的应用n逐行打印二项展开式逐行打印二项展开式 (a+b)n 的系数的系数杨辉三角形杨辉三角形833.3 栈与队列的应用栈与队列的应用u分析第分析第 i 行元素与第行元素与第 i+1行元素的关系行元素的关系目的是从前一行的数据可以计
