第3章栈和队列-讲课用详解.ppt

* a1 a2 a3 an ... 队头 队尾 出队列 * 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）。 （A）2 （B）3 （C）4 （D）6 练习 B * 数据对象: 数据关系: 基本操作: (1) InitQueue (Q) //构造空队列 (2) DestroyQueue (Q) //销毁队列 (3) ClearQueue (S) //清空队列 (4) QueueEmpty(S) //判空. 空--TRUE, ADT Queue { 队列的抽象数据类型 * 链栈出栈 ∧ S A e = ‘A’ p S Status Pop (LinkStack S,SElemType e) {if (S==NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; } * 链栈出栈 Status Pop (LinkStack S,SElemType e) {if (S==NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; } ∧ e = ‘A’ S * 取链栈栈顶元素 SElemType GetTop(LinkStack S) { if (S==NULL) exit(1)； else return S–data; } * 3.2 　栈的应用 例1：数制转换（十转N） 用栈暂存低位值 例2：括号匹配的检验 用栈暂存左括号 例3：表达式求值 用栈暂存运算符 简化了程序设计的问题 例1：数制转换（十转N） 十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理： N = (N div d)×d + N mod d (其中：div 为整除运算，mod 为求余运算） 例如：（1348)10 = ( ??? )8 ，其运算过程如下： N ????????? N div 8 ????????? N mod 8 1348???? 168 ??????????????? 4 168??????? 21 ???????????????? 0 21??????? ? 2 ????????????????? 5 2 ????? 0 ??????????? ???? 2 2504 void Conversion( ) { InitStack(S); // 构造空栈 cinN; while(N) { Push(S,Nn%8); //余数进栈 N=N/8; //商成为新的被除数 } while(! StackEmpty(S)) //栈非空的时候 { Pop(S,e); coute; } } //conversion 例2 括号匹配的检验 例如考虑下列括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 括号不匹配出错的情况： 1.当表达式扫描结束时，栈中还有一个左括号没有匹配。如：[([]) 2.栈顶的左括号和最后的右括号不匹配。如：(()] 3.由于前面入栈的左括号均已和后面出现的右括号相匹配，栈已空，最后扫描的右括号不能得到匹配。如：(()[])) Status Matching() { int flag=1;