汇编语言3.ppt

1、第三章第三章栈和队列栈和队列栈和队列是限定插入和删除只能插入和删除只能在表的“端点端点”进行的线性表。线性表线性表 栈栈 队列队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1 Delete(L,i)Delete(S,n)Delete(Q,1)1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型栈和队列概述栈和队列概述栈和队列概述栈和队列概述 栈栈和和队队列列是是在在程程序序设设计计中中被被广广泛泛使使用用的的两两种种线线性性数数据据结结构构，它它们们的的特特点点在在于于基基本本操操作作的的特特殊殊性性，栈栈必必须须按按“后后进进先先

2、出出”的的规规则则进进行行操操作作，而而队队列列必必须须按按“先先进进先先出出”的的规规则进行操作。则进行操作。和和线线性性表表相相比比，它它们们的的插插入入和和删删除除操操作作受受到到更更多多的的约约束束和和限限定定，故故又又称称为为限限定定性性的的线性表结构。线性表结构。3.1 栈的类型定义栈的类型定义3.2 栈的应用举例栈的应用举例3.3 栈类型的实现栈类型的实现3.4 队列的类型定义队列的类型定义3.5 队列类型的实现队列类型的实现主要内容主要内容3.1 3.1 栈的定义栈的定义定义定义:是限定仅在表尾进行插入或删除操是限定仅在表尾进行插入或删除操作的线性表。作的线性表。允许插入和删除

3、的一端允许插入和删除的一端称为栈顶称为栈顶(top)，另一端另一端称为栈底称为栈底(bottom)特点：特点：后进先出后进先出（LastIn First Out的缩写的缩写）(LIFO)a1topbottoman.进栈进栈 出栈出栈栈的类型定义栈的类型定义 ADT Stack 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,aiD,i=2,.,n 约定an 端为栈顶，a1 端为栈底。基本操作：基本操作：ADT StackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)S

4、tackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit()InitStack(&S)操作结果：构造一个空栈 S。DestroyStack(&S)初始条件：栈 S 已存在。操作结果：栈 S 被销毁。StackEmpty(S)初始条件：栈 S 已存在。操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。StackLength(S)初始条件：栈 S 已存在。操作结果：返回 S 的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。a1a2an Cle

5、arStack(&S)初始条件：栈 S 已存在。操作结果：将 S 清为空栈。Push(&S,e)初始条件：栈 S 已存在。操作结果：插入元素 e 为新的栈顶元素。a1a2ane Pop(&S,&e)初始条件：栈 S 已存在且非空。操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1a2anan-1 3.2 栈的应用举例栈的应用举例例一、例一、数制转换数制转换例二、例二、括号匹配的检验括号匹配的检验例三、例三、行编辑程序问题行编辑程序问题例四、例四、迷宫求解迷宫求解例五、例五、表达式求值表达式求值例六、例六、实现递归实现递归 例一、例一、数制转换数制转换 算法基于原理：N=(N div d)

6、d+N mod d 例如：例如：（1348)10=(2504)8，其运算过程如下：N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2计计算算顺顺序序输输出出顺顺序序void conversion()InitStack(S);scanf(%d,N);while(N)Push(S,N%8);N=N/8;while(!StackEmpty(S)Pop(S,e);printf(%d,e);/conversion例二、例二、括号匹配的检验括号匹配的检验假设在表达式中（）或（）等为正确的格式，（）或（）或（）)均为不正确的格式。则 检验括号是否匹配的方法可用

7、“期待的急迫程度”这个概念来描述。分析可能出现的不匹配不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列：()1 2 3 4 5 6 7 8到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧。算法的设计思想：算法的设计思想：1）凡出现左括弧左括弧，则进栈进栈；2）凡出现右括弧右括弧，首先检查栈是否空 若栈空栈空，则表明该“右括弧右括弧”多余多余，否则和栈顶元素和栈顶元素比较，若相匹配相匹配，则“左括弧出栈左括弧出栈”，否则表明不匹配不匹配。3）表达式表达式检验结束时结束时，若栈空栈空，则表明表达式中匹配正确匹配正确，否则表明“左括弧左括弧”有余有余。Status ma

8、tching(string&exp)int state=1;while(i=Length(exp)&state)switch of expi case 左括弧:Push(S,expi);i+;break;case”)”:if(NOT StackEmpty(S)&GetTop(S)=“(“Pop(S,e);ii+;else state=0;break;if(StackEmpty(S)&state)return OK;.例三、行编辑程序问题例三、行编辑程序问题如何实现？如何实现？“每接受一个字符即存入存储器每接受一个字符即存入存储器”?并不恰当！设立一个输入缓冲区，用以接受设立一个输入缓冲区，用以

9、接受用户输入的一行字符，然后逐行存用户输入的一行字符，然后逐行存入用户数据区，并假设入用户数据区，并假设“#”为退格为退格符，符，“”为退行符。为退行符。在用户输入一行的过程中，允许在用户输入一行的过程中，允许用户输入出差错，并在发现有误时用户输入出差错，并在发现有误时可以及时更正。可以及时更正。合理的作法是：假设从终端接受了这样两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);则实际有效的是下列两行：while(*s)putchar(*s+);while(ch!=EOF&ch!=n)switch(ch)case#:Pop(S,c);break;case:Cl

10、earStack(S);break;/重置S为空栈 default:Push(S,ch);break;ch=getchar();/从终端接收下一个字符 ClearStack(S);/重置S为空栈if(ch!=EOF)ch=getchar();while(ch!=EOF)/EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；例四、例四、迷宫求解迷宫求解通常用的是“穷举求解穷举求解”的方法求迷宫路径算法的基本思想基本思想是：若当前位置若当前位置“可通可通”，则纳入路，则纳入路径，继续前进径，继续前进;若当前位置若当前位置“不可通不可通”，则后退，则后退，换方向继续探索换方向继续探索;若四

11、周若四周“均无通路均无通路”，则将当前，则将当前位置从路径中删除出去。位置从路径中删除出去。设定当前位置的初值为入口位置；do 若当前位置可通若当前位置可通，则则将当前位置插入栈顶插入栈顶；若若该位置是出口位置，则则算法结束；否则切换否则切换当前位置的东邻方块为 新的当前位置；否则否则 while(栈不空）栈不空）；求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法：若若栈不空且栈顶位置尚有其他方向未被探索栈不空且栈顶位置尚有其他方向未被探索，则则设定新的当前位置为:沿顺时针方向旋转 找到的栈顶位置的下一相邻块栈顶位置的下一相邻块；若若栈不空但栈顶位置的四周均不可通栈不

12、空但栈顶位置的四周均不可通，则则删去栈顶位置；/从路径中删去该通道块 若若栈不空，则则重新测试新的栈顶位置，直至直至找到一个可通的相邻块或出栈至栈空；若若栈空栈空，则则表明迷宫没有通路。限于二元运算符的表达式定义:表达式表达式:=(操作数操作数)+(运算符运算符)+(操作数操作数)操作数操作数:=简单变量简单变量|表达式表达式 简单变量简单变量:=标识符标识符|无符号整数无符号整数例五、例五、表达式求值表达式求值 表达式的三种标识方法：表达式的三种标识方法：设设 Exp=S1+OP+S2则称则称 OP+S1+S2 为前缀表示法前缀表示法 S1+OP+S2 为中缀表示法中缀表示法 S1+S2+O

13、P 为后缀表示法后缀表示法 例如:Exp=a b+(c d/e)f前缀式:+a b c/d e f中缀式:a b+c d/e f后缀式:a b c d e/f +结论结论:1）操作数之间的相对次序不变）操作数之间的相对次序不变;2）运算符的相对次序不同）运算符的相对次序不同;3）中缀式丢失了括弧信息，致使运算的次序不确定;4)前缀式的运算规则前缀式的运算规则为:连续出现的两个操作数和在它们连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一之前且紧靠它们的运算符构成一个最小表达式个最小表达式;5)后缀式的运算规则后缀式的运算规则为:运算符在式中出现的顺序恰为运算符在式中出现的顺序恰为 表达

14、式的运算顺序表达式的运算顺序;每个运算符和在它之前出现每个运算符和在它之前出现 且且 紧靠它的两个操作数构成一个最小紧靠它的两个操作数构成一个最小 表达式。表达式。如何从后缀式求值？如何从后缀式求值？先找运算符，先找运算符，再找操作数再找操作数例如：例如：a b c d e/f +a bd/ec-d/e(c-d/e)f后缀表达式求值算法的基本思路是：算法的基本思路是：1）读入表达式；）读入表达式；2）若为操作数，则入栈；）若为操作数，则入栈；3）若为运算符，则弹出栈顶元素和下一元）若为运算符，则弹出栈顶元素和下一元素，参加运算，再将结果压入栈；素，参加运算，再将结果压入栈；使用两个工作栈：使用

15、两个工作栈：OPTROPTR：存运算符；：存运算符；OPNDOPND：存操作数或运算结果。：存操作数或运算结果。算法的基本思想是：算法的基本思想是：1 1）置操作数栈为空栈，表达式起始符）置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；为运算符栈的栈底元素；中缀表达式求值 2 2）依次读入表达式中每个字符，若是操作）依次读入表达式中每个字符，若是操作数则进数则进OPNDOPND栈，若是运算符，则和栈，若是运算符，则和OPTROPTR栈的栈顶运算符比较优先权后作相应操作，栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即直至整个表达式求值完毕（即OPTROPTR栈顶元栈顶

16、元素和当前读入的字符均为素和当前读入的字符均为“#”）；）；中缀表达式求值l如何从原表达式求得后缀式？如何从原表达式求得后缀式？每个运算符的运算次序要由它之后它之后的一个运算符的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。分析“原表达式”和“后缀式”中的运算符:原表达式:a+b c d/e f 后缀式:a b c +d e/f 从原表达式求得后缀式的规律为：从原表达式求得后缀式的规律为：1)设立操作数栈；栈；2)设表达式的结束符为“#”，预设运算符栈的栈底为“#”；3)若当前字符是操作数，则直接发送给后缀式。4)若当前运算符的优先数高于栈顶运算符，则进栈；5)否则，退出

17、栈顶运算符发送给后缀式；6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：从原表达式求得后缀式的规律为：void transform(char suffix,char exp )InitStack(S);Push(S,#);p=exp;ch=*p;while(!StackEmpty(S)if(!IN(ch,OP)Pass(Suffix,ch);else if(ch!=#)p+;ch=*p;else Pop(S,ch);Pass(Suffix,ch);/while/CrtExptree switch(ch)case(:Push(S

18、,ch);break;case):Pop(S,c);while(c!=()Pass(Suffix,c);Pop(S,c)break;defult :while(Gettop(S,c)&(precede(c,ch)Pass(Suffix,c);Pop(S,c);if(ch!=#)Push(S,ch);break;/switch递归工作栈递归工作栈n每一次递归调用时，需要为过程中使用每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。的参数、局部变量等另外分配存储空间。n每层递归调用需分配的空间形成递归工每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。作记录，按后进

19、先出的栈组织。局部变量局部变量返回地址返回地址参参 数数活动活动记录记录框架框架递归递归工作记录工作记录例六、实现递归例六、实现递归函数递归时的活动记录函数递归时的活动记录.Function().调用块函数块返回地址(下一条指令)局部变量 参数将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回返回调用函数之前之前，应该完成下列三项任务：多

20、个函数嵌套调用的规则是：此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回！例如：void main()void a()void b()a();b();/main /a /bMain的数据区函数a的数据区函数b的数据区 void hanoi(int n,char x,char y,char z)/将塔座x上按直径由小到大且至上而下编号为1至n/的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 if(n=1)2 move(x,1,z);/将编号为的圆盘从x移到z3 else 4 hanoi(n-1,x,z,y);/将x上编号为至n-1的 /圆盘移到y,z作辅助塔5 move(x,n

21、,z);/将编号为n的圆盘从x移到z6 hanoi(n-1,y,x,z);/将y上编号为至n-1的 /圆盘移到z,x作辅助塔7 8 0 3 a b c返址 n x y z5 2 a c b5 1 a b c7 1 c a bvoid hanoi(int n,char x,char y,char z)1 if(n=1)2 move(x,1,z);3 else 4 hanoi(n-1,x,z,y);5 move(x,n,z);6 hanoi(n-1,y,x,z);7 8 3.3栈类型的实现栈类型的实现顺序栈顺序栈链栈链栈顺序栈的表示和实现顺序栈的表示和实现顺序栈：顺序栈：栈的顺序存储结构，利用一组

22、地址连栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，续的存储单元依次存放自栈底到栈顶的数据元素，指针指针top指向栈顶元素在顺序栈中的下一个位置，指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。为栈底指针，指向栈底的位置。base空栈a 进栈b 进栈aabtopbasetopbasetoptoptopabcdee 进栈abcdef 进栈溢出abde 出出栈cbasebasebasetop/-栈的顺序存储表示栈的顺序存储表示-#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typed

23、ef struct SElemType *base;SElemType *top;int stacksize;SqStack;类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。Status InitStack(SqStack&S)/构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败 S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status Push(SqStack&S,SElemT

24、ype e)if(S.top-S.base=S.stacksize)/栈满，追加存储空间 S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败 S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack&S,SElemType&e)/若栈不空，则删除S的栈顶元素，/用e返回其值，并返回OK；/否则返回E

25、RROR if(S.top=S.base)return ERROR;e=*-S.top;return OK;链式栈无栈满问题，空间可扩充链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行链式栈的栈顶在链头链式栈的栈顶在链头适合于多栈操作适合于多栈操作top链栈链栈栈顶指针链栈链栈a1an注意注意:链栈中链栈中指针的方向指针的方向an-1链式栈链式栈(LinkStack)的定义的定义typedef int StackData;typedef struct node StackData data;/结点结点 struct node*link;/链指针链指针 StackNo

26、de;typedef struct StackNode*top;/栈顶指针栈顶指针 LinkStack;链式栈操作实现链式栈操作实现初始化初始化void InitStack(LinkStack*S)S-top=NULL;入栈入栈int Push(LinkStack*S,StackData x)StackNode*p=(StackNode*)malloc (sizeof(StackNode);p-data=x;p-link=S-top;S-top=p;return OK;判栈空判栈空int StackEmpty(LinkStack*S)return S-top=NULL;出栈出栈int Pop(

27、LinkStack*S,StackData&x)if(StackEmpty(S)return ERROR;StackNode*p=S-top;S-top=p-link;x=p-data;free(p);return OK;取栈顶取栈顶int GetTop(LinkStack*S,StackData&x)if(StackEmpty(S)return 0;x=S-top-data;return 1;置栈空置栈空int MakeEmpty(LinkStack*S)While(S-top!=NULL)StackNode*p=S-top;S-top=S-top-link;free(p);定义定义:只允许

28、在表的一端进行插入，而在另一端只允许在表的一端进行插入，而在另一端删除元素的线性表。删除元素的线性表。在队列中，允许插入的一端叫在队列中，允许插入的一端叫队尾（队尾（rear）。允许删除的一端称为允许删除的一端称为对头对头(front)。特点：特点：先进先出先进先出(FIFO)（First In First Out 的缩的缩写）写）3.4 队列的定义队列的定义出队出队入队入队队头队头队尾队尾a1a2a3an ADT Queue 数据对象：数据对象：Dai|aiElemSet,i=1,2,.,n,n0 数据关系：数据关系：R1|ai-1,ai D,i=2,.,n 约定其中a1 端为队列头队列头，

29、an 端为队列尾队列尾基本操作：基本操作：队列的类型定义队列的类型定义 ADT Queue队列的基本操作：队列的基本操作：InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit()InitQueue(&Q)操作结果：操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：初始条件：队列Q已存在。操作结果：操作结果：队列Q被销毁，不再存在。QueueEmpty(Q)初始条件：初始

30、条件：队列Q已存在。操作结果：操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。QueueLength(Q)初始条件：初始条件：队列Q已存在。操作结果：操作结果：返回Q的元素个数，即队列的长度。GetHead(Q,&e)初始条件：初始条件：Q为非空队列。操作结果：操作结果：用e返回Q的队头元素。a1a2an ClearQueue(&Q)初始条件：初始条件：队列Q已存在。操作结果：操作结果：将Q清为空队列。EnQueue(&Q,e)初始条件：初始条件：队列Q已存在。操作结果：操作结果：插入元素e为Q的新的队尾元素。a1a2ane DeQueue(&Q,&e)初始条件：初始条件：Q为非空

31、队列。操作结果：操作结果：删除Q的队头元素，并用e返回其值。a1a2an 3.5 队列类型的实现队列类型的实现链队列链队列链式映象循环队列循环队列顺序映象 typedef struct QNode/结点类型结点类型 QElemType data;struct QNode *next;QNode,*QueuePtr;链队列链队列链式映象typedef struct /链队列类型链队列类型 QueuePtr front;/队头指针队头指针 QueuePtr rear;/队尾指针队尾指针 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空队列空队列 Status In

32、itQueue(LinkQueue&Q)/构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);/存储分配失败 Q.front-next=NULL;return OK;Status EnQueue(LinkQueue&Q,QElemType e)/插入元素e为Q的新的队尾元素 p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);/存储分配失败 p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;

33、return OK;Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，/用 e 返回其值，并返回OK；否则返回ERROR if(Q.front=Q.rear)return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base;/动态分配存储空间 int front;/头指针，若队列

34、不空，/指向队列头元素 int rear;/尾指针，若队列不空，指向 /队列尾元素 的下一个位置 SqQueue;循环队列循环队列顺序映象顺序队列顺序队列队列的顺序存储表示队列的顺序存储表示 用一组地址连续的存储单元依次存放用一组地址连续的存储单元依次存放从队列头到队列尾的元素，指针从队列头到队列尾的元素，指针front和和rear分别指示队头元素和队尾元素的位置。分别指示队头元素和队尾元素的位置。插入新的队尾元素，尾指针增插入新的队尾元素，尾指针增1，rear=rear+1，删除队头元素，头指针增，删除队头元素，头指针增1，front=front+1，因此，在非空队列中，因此，在非空队列中，

35、头指针始终指向队列头元素，而尾指针始头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。队满时终指向队列尾元素的下一个位置。队满时再进队将溢出。再进队将溢出。队列的进队和出队列的进队和出队队frontrear空队列空队列frontrearA,B,C,D进队进队A B C DfrontrearA,B出队出队C DfrontrearE,F,G进队进队C D E F GC D E F GfrontrearH进队进队,溢出溢出 将顺序队列将顺序队列臆造为一个臆造为一个环状的空间，环状的空间，形成循环形成循环(环环形形)队列。队列。a8a7a6a576543210rearfront循环队列

36、循环队列顺序映象循环队列循环队列(Circular Queue)队头、队尾指针加队头、队尾指针加1，可用取模，可用取模(余数余数)运算实现。运算实现。队头指针加队头指针加1:front=(front+1)%maxsize;队尾指针加队尾指针加1:rear=(rear+1)%maxsize;队列初始化队列初始化：front=rear=0;队空条件队空条件：front=rear;队满条件：队满条件：(rear+1)%maxsize=front;01234567循环队列循环队列frontrearMaxsize-101234567frontBCDrear一般情况一般情况AC01234567队满队满fr

37、ontrearDEFGABCH01234567rear空队列空队列frontC01234567队满队满(正确正确)frontrearDEFGABC Status InitQueue(SqQueue&Q)/构造一个空队列Q Q.base=(ElemType*)malloc (MAXQSIZE*sizeof(ElemType);if(!Q.base)exit(OVERFLOW);/存储分配失败 Q.front=Q.rear=0;return OK;Status EnQueue(SqQueue&Q,ElemType e)/插入元素e为Q的新的队尾元素 if(Q.rear+1)%MAXQSIZE=Q.

38、front)return ERROR;/队列满 Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;Status DeQueue(SqQueue&Q,ElemType&e)/若队列不空，则删除Q的队头元素，/用e返回其值，并返回OK;否则返回ERROR if(Q.front=Q.rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;第 1 行 1 1第 2 行 1 2 1 第 3 行 1 3 3 1第 4 行 1 4 6 4 1二项式系数值（杨辉三角）

39、设第 i-1行的值：(a0=0)a1.ai(ai+1=0)则第 i 行的值：bj=aj-1+aj,j=1,2,i+1利用循环队列计算二项式的过程：假设只计算四行，则队列的最大容量为 5。1 1 00q.frontq.rear1 1 001q.frontq.rear1 1 021q.frontq.rear1 1 021q.frontq.rear1 0 021q.frontq.rear1 0 121q.frontq.rear1 0 121q.frontq.rear1 0 123q.frontq.rear1 0 133q.frontq.rear1 0 131q.frontq.reardo DeQue

40、ue(Q,s);GetHead(Q,e);if(e!=0)printf(“%d”,e);EnQueue(Q,s+e);while(e!=0);1.掌掌握握栈栈和和队队列列类类型型的的特特点点，并并能能在在相相应应的应用问题中正确选用它们。的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，特别应熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。注意栈满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。现算法，特别注意队满和队空的描述方法。4.理解递归算法执行过程中栈

41、的状态变化过理解递归算法执行过程中栈的状态变化过程。程。本章学习要点本章学习要点作作 业业1、链栈中为何不设头指针？、链栈中为何不设头指针？2、循环队列的优点是什么？如何判断它的、循环队列的优点是什么？如何判断它的空和满？空和满？3、设长度为、设长度为n的链队列用单循环链表表示，的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？作；若只设尾指针呢？4、假设循环队列只设、假设循环队列只设rear和和quelen来分别指来分别指示队尾元素的位置和队中元素的个数，试给出示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。队和出队算法，要求出队时需返回队头指针。5、画出对算术表达式、画出对算术表达式A-B*C/D+EF求值时操求值时操作数栈和运算符栈的变化过程作数栈和运算符栈的变化过程。作作 业业