严蔚敏版数据结构第三章课件.ppt

1、1数据结构课程的内容数据结构课程的内容23.1 栈（栈（Stack）第三章第三章 栈和队列栈和队列3.2 队列队列（Queue）1.定义定义2.逻辑结构逻辑结构3.存储结构存储结构4.运算规则运算规则5.实现方式实现方式1.定义定义2.逻辑结构逻辑结构3.存储结构存储结构4.运算规则运算规则5.实现方式实现方式31.定义定义3.1 栈栈与同线性表相同，仍为一对一关系。与同线性表相同，仍为一对一关系。用顺序栈或链栈存储均可，但以顺序栈更常见用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时依照后进先出只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（）或先进后出（

2、FILO）的原则。）的原则。关键是编写入栈和出栈函数，具体实现依顺关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。序栈或链栈的不同而不同。基本操作有入栈、出栈、读栈顶元素值、建基本操作有入栈、出栈、读栈顶元素值、建栈、或判断栈满、栈空等。栈、或判断栈满、栈空等。3.存储结构存储结构4.运算规则运算规则5.实现方式实现方式 2.逻辑结构逻辑结构限定只能在表的一端进行插入和删除运算的限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）线性表（只能在栈顶操作）4问：堆栈是什么？它与一般线性表有什么不同？问：堆栈是什么？它与一般线性表有什么不同？3.1 栈栈答：答：堆栈是一种特

3、殊的线性表，它只能在表的一端堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。与一般线性表的区别：仅在于运算规则不同。一般线性表一般线性表 堆栈堆栈逻辑结构：一对一逻辑结构：一对一 逻辑结构：一对一逻辑结构：一对一存储结构：顺序表、链表存储结构：顺序表、链表 存储结构：顺序栈、链栈存储结构：顺序栈、链栈运算规则：随机存取运算规则：随机存取 运算规则：后进先出运算规则：后进先出(LIFO)“进进”压入压入=PUSH（x)“出出”弹出弹出=POP(y)5栈栈 是仅在是仅在表尾表尾进行插入、删除操作的线性表。进

4、行插入、删除操作的线性表。表尾表尾(即即 an 端端)称为称为栈顶栈顶 top;表头表头(即即 a1 端端)称为称为栈底栈底base例如：例如：栈栈 s=(a1 ,a2 ,a3 ,.,an-1 ,an)a1 称为称为 栈底元素栈底元素 an 称为称为 栈顶元素栈顶元素插入元素到插入元素到栈顶栈顶（即表尾）的操作，称为（即表尾）的操作，称为入栈入栈。从从栈顶栈顶（即表尾）删除最后一个元素的操作，称为（即表尾）删除最后一个元素的操作，称为出栈出栈。教材教材P44P44对对栈栈有更详细定义：有更详细定义：强调：强调：插入和删除都只能在表的一端（栈顶）进行！插入和删除都只能在表的一端（栈顶）进行！6栈

5、的表示和实现栈的表示和实现 顺序栈：栈的顺序存储结构，利用一组地顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶址连续的存储单元依次存放自栈底到栈顶的数据元素，指针的数据元素，指针top指向栈顶元素在顺指向栈顶元素在顺序栈中的下一个位置，序栈中的下一个位置，base为栈底指针，指向栈底的位置。为栈底指针，指向栈底的位置。base空栈a 进栈b 进栈aabtopbasetopbasetop顺序栈示意图顺序栈示意图s a1 a2 a3data(栈底栈底)(栈顶栈顶)99.3210top8顺序栈的类型表示顺序栈的类型表示:#define STACK_INIT_SIZE 100

6、#define STACK_INIT_SIZE 100；#define STACKINCREMENT 10#define STACKINCREMENT 10；typedef char StackData;typedef char StackData;typedef struct typedef struct/顺序栈定义顺序栈定义 StackData StackData*base;base;/栈底指针栈底指针 StackData StackData*top;top;/栈顶指针栈顶指针int stacksizeint stacksize；/当前已分配的存储空间当前已分配的存储空间 SeqStack

7、 SeqStack；9 判栈空判栈空 int StackEmpty(SeqStack int StackEmpty(SeqStack*S)S)if(S-top=S-base)return 1/if(S-top=S-base)return 1/空则返回空则返回1 1 else return 0;/else return 0;/否则返回否则返回0 0 判栈满判栈满 int StackFull(SeqStack int StackFull(SeqStack*S)S)if(S-top-S-base=S-StackSize)if(S-top-S-base=S-StackSize)return 1 ret

8、urn 1/判栈满判栈满,满则返回满则返回1 1else return 0;else return 0;/否则返回否则返回0 0 顺序栈的基本运算顺序栈的基本运算:10初始化初始化void InitStack(SeqStack*S)/置空栈置空栈S-base-base=(StackData*)malloc(STACK_INIT_SIZE*sizeof(StackData);if(!S-base)exit(OVERFLOW);S-top=S-base-base;S-stacksize=S-stacksize=STACK_INIT_SIZE;Return ok;11 a1 a2 an顺序栈顺序栈S

9、 ai表和栈的操作区别表和栈的操作区别对线性表对线性表 s=(a1 ,a2 ,.,an-1,an)表头表头表尾表尾栈底栈底base栈顶栈顶top低地址低地址高地址高地址写入：写入：vi=ai读出：读出：x=vi压入：压入：PUSH(an+1)弹出：弹出：POP (x)前提：一定要预设栈顶指针前提：一定要预设栈顶指针top！低地址低地址高地址高地址vi a1 a2 ai an 顺序表顺序表Vn an+112入栈操作入栈操作例如用堆栈存放（例如用堆栈存放（A A，B B，C C，D D）（注意要遵循（注意要遵循“后进先出后进先出”原则）原则）AACBABAtop核心语句：核心语句：top=L;顺序

10、栈中的顺序栈中的PUSHPUSH函数函数status Push(ElemType x)if(topM)上溢 else vtop+top+=x;Push(B);Push(C);Push(D);toptoptoptop低地址低地址LPush(A);高地址高地址MBCD13 入栈入栈 int Push(SeqStack*S,StackData x)/插入元素插入元素x为新的栈顶元素为新的栈顶元素 if(StackFull(S)S-base=(StackData*)malloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(StackData);if(!S-ba

11、se)exit(overflow);S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;/追加存储空间追加存储空间 *(S-top)=x;（S-top）+;Return ok 14 出栈操作出栈操作例如从栈中取出例如从栈中取出B B （注意要遵循（注意要遵循“后进先出后进先出”原则）原则）DCBAtoptopDCABDCBAtopDCBAtoptop低地址低地址L高地址高地址MD核心语句：核心语句：Pop();Pop();Printf(Pop();顺序栈中的顺序栈中的POPPOP函数函数status Pop()status Pop()if(

12、top=L)if(top=L)下溢下溢 else y=velse y=v-top-top;return(y);return(y);15 出栈出栈 int pop(SeqStack*S,StackData&x)/若栈空返回若栈空返回0,否则栈顶元素退出到否则栈顶元素退出到x并并返回返回1 if(StackEmpty(S)return 0;-(S-top);x=*(S-top);return 1;16例例1：一个栈的输入序列是一个栈的输入序列是12345，若在入栈的过，若在入栈的过程中允许出栈程中允许出栈，则栈的输出序列则栈的输出序列43512可能实现可能实现吗？吗？12345的输出呢？的输出呢？

13、43512不可能实现，主要是其中的不可能实现，主要是其中的12顺序不能顺序不能实现；实现；12345的输出可以实现，只需压入一个立即弹的输出可以实现，只需压入一个立即弹出一个即可。出一个即可。435612中到了中到了12顺序不能实现；顺序不能实现；135426可以实现。可以实现。例例2：如果一个栈的输入序列为如果一个栈的输入序列为123456，能否得，能否得到到435612和和135426的出栈序列？的出栈序列？答：答：答：答：17例例3（严题集（严题集3.1）一个栈的输入序列为一个栈的输入序列为123，若在，若在入栈的过程中允许出栈，则可能得到的出栈序列是入栈的过程中允许出栈，则可能得到的出

14、栈序列是什么？什么？答：答：可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解：1 1入入1 1出，出，2 2入入2 2出，出，3 3入入3 3出，出，即即123123；1 1入入1 1出，出，2 2、3 3入入3 3、2 2出，出，即即132132；1 1、2 2入，入，2 2出，出，3 3入入3 3出，出，即即231231；1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出，即即213213；1 1、2 2、3 3入，入，3 3、2 2、1 1出，出，即即321321；合计有合计有5 5种可能性。种可能性。18例例4：计算机系计算机系2001年考研题（程序设计基础）

15、年考研题（程序设计基础）设依次进入一个栈的元素序列为设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：则可得到出栈的元素序列是：A、D可以可以（B、C不行）。不行）。讨论：有无通用的判别原则？讨论：有无通用的判别原则？有。在可能的输出序列中，不存在这样的输入序列有。在可能的输出序列中，不存在这样的输入序列i i，j j，k k，能同时满足，能同时满足 ijk ijk 和和 PjPkPiPjPkdata=x;p-link=st;st=p;S Status pop()pop()if(st=NULL)if(st=NULL)下溢下溢 elsey=st-data;p=st;st=st

16、-link;elsey=st-data;p=st;st=st-link;free(p);return(y);free(p);return(y);链栈链栈入栈入栈函数函数链栈链栈出栈出栈函数函数插入插入表头表头从表头从表头删除删除23说说 明明链式栈无栈满问题，空间可扩充链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行链式栈的栈顶在链头链式栈的栈顶在链头适合于多栈操作适合于多栈操作24 数制转换（十转数制转换（十转N）P48 设计思路：用栈暂存低位值设计思路：用栈暂存低位值例例2：括号匹配的检验括号匹配的检验P49 设计思路：用栈暂存左括号设计思路：用栈暂存左括号例例

17、3：表达式求值表达式求值 -P52 设计思路：用栈暂存运算符设计思路：用栈暂存运算符例例1：栈的应用举例栈的应用举例251.数制转换数制转换N=(N div d)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输出顺序输出顺序计算顺序计算顺序26void conversion()InitStack(S);scanf(%d,N);while(N)Push(S,N%8);N=N/8;while(!StackEmpty(S)Pop(S,e);prin

18、tf(%d,e);/conversion272.行编辑程序行编辑程序在用户输入一行的过程中，允许用户输入出差在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。错，并在发现有误时可以及时更正。设立一个输入缓冲区，用以接受用户输入的一设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区行字符，然后逐行存入用户数据区;并假设并假设“#”为退为退格符，格符，“”为退行符。为退行符。假设从终端接受两行字符：假设从终端接受两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);实际有效行为：实际有效行为：while(*s)putchar(

19、*s+);28Void LineEdit()InitStack(s);ch=getchar();while(ch!=EOF)/EOF为全文结束符为全文结束符while(ch!=EOF&ch!=n)switch(ch)case#:Pop(S,c);break;case:ClearStack(S);break;/重置重置S为空栈为空栈 default:Push(S,ch);break;ch=getchar();/从终端接收下一个字符从终端接收下一个字符 29将从栈底到栈顶的字符传送至调用过程的数据区将从栈底到栈顶的字符传送至调用过程的数据区；ClearStack(S);/重置重置S为空栈为空栈if

20、(ch!=EOF)ch=getchar();DestroyStack(s);30例例3 3 表达式求值表达式求值(这是栈应用的典型例子这是栈应用的典型例子 )这里，这里，表达式求值的算法是表达式求值的算法是“算符优先法算符优先法”。例如：例如：3*（7 2）（1）要正确求值，首先了解算术四则运算的规则：）要正确求值，首先了解算术四则运算的规则：a.从左算到右从左算到右 b.先乘除，后加减先乘除，后加减 c.先括号内，后括号外先括号内，后括号外例：例：4+2*3-10/5=4+6-10/5=10-10/5=10-2=8 由此，此表达式的计算顺序为：由此，此表达式的计算顺序为：3*（7 2）=3*

21、5=1531（2）根据上述三条运算规则，在运算的每一步中，对任意）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符相继出现的算符 1和和 2，都要比较优先权关系。，都要比较优先权关系。算符优先法所依据的算符间的优先关系算符优先法所依据的算符间的优先关系见教材见教材P53表表3.1 （是提供给计算机用的表！）（是提供给计算机用的表！）由表可看出，右括号由表可看出，右括号)和井号和井号#作为作为 2时时级别最低；级别最低；由由c 规则规则得出：得出：*，/，+，-为为 1时的优先权低于时的优先权低于（，高于高于）由由a规则规则得出：得出：（=）表明括号内运算，已算完。表明括号内运算，已

22、算完。#=#表明表达式求值完毕。表明表达式求值完毕。栈的应用（表达式求值）栈的应用（表达式求值）32（3）算法思想：）算法思想：设定两栈：设定两栈：操作符栈操作符栈 OPTR，操作数栈，操作数栈 OPND 栈初始化栈初始化：设操作数栈：设操作数栈 OPND 为空；操作符栈为空；操作符栈 OPTR 的栈的栈底元素为表达式起始符底元素为表达式起始符#；依次读入字符依次读入字符：是操作数则入：是操作数则入OPND栈，是操作符则要判断：栈，是操作符则要判断：if 操作符操作符 栈顶元素栈顶元素，压入，压入OPTR栈。栈。栈的应用（表达式求值）栈的应用（表达式求值）33栈的应用（表达式求值）栈的应用（表

23、达式求值）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(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)34Status EvaluateExpression(OperandType&result)InitStack(OPND

24、);InitStack(OPTR);Push(OPTR,#);c=getchar();while(c!=#)/(GetTop(OPTR)!=#)if(!In(c,OP)Push(OPND,c);c=getchar();else switch(compare(c,GetTop(OPTR)case :Push(OPTR,c);c=getchar();break;case=:Pop(OPTR);c=getchar();break;case next=S;rear=S;出队（头部删除）：出队（头部删除）：front-next=p-next;队列会满吗？队列会满吗？front=rear一般不会，因为删除

25、时有一般不会，因为删除时有free动作。除非内存不足！动作。除非内存不足！38frontrearx元素元素x入队入队frontrearxy元素元素y入队入队frontrearxy元素元素x出队出队frontrear空队列空队列39 链式队列的定义链式队列的定义 typedef int QueueData;typedef struct node QueueData data;/队列结点数据队列结点数据 struct node*link;/结点链指针结点链指针 QueueNode;typedef struct QueueNode*rear,*front;LinkQueue;40基本操作基本操作 S

26、tatus InitQueue(LinkQueue&Q)Status InitQueue(LinkQueue&Q)/构造一个空队列构造一个空队列Q Q if(!(Q.front=Q.rear=(QueuePtr)mallocif(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)(sizeof(QNode)exit(OVERFLOW);exit(OVERFLOW);Q.front-next=NULL;Q.front-next=NULL;return OK;return OK;41 Status QueueEmpty(LinkQueue Q)/若若Q为

27、空队列为空队列,则返回则返回TRUE,否则返回否则返回FALSE if(Q.front=Q.rear)return TRUE;else return FALSE;42 int QueueLength(LinkQueue Q)/求队列的长度求队列的长度 int i=0;QueuePtr p;p=Q.front;while(Q.rear!=p)i+;p=p-next;return i;43 Status EnQueue(LinkQueue&Q,QElemType e)/插入元素插入元素e为为Q的新的队尾元素的新的队尾元素 QueuePtr p;if(!(p=(QueuePtr)malloc(siz

28、eof(QNode)/存存储分配失败储分配失败 exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;44 Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空若队列不空,删除删除Q的队头元素的队头元素,用用e返回其值返回其值,并返回并返回OK,否则返回否则返回ERROR QueuePtr p;if(Q.front=Q.rear)return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.re

29、ar=Q.front;free(p);return OK;45顺序队示意图顺序队示意图Q(队尾队尾)(队首队首)front a1 a2 a3data a40.99rear 队列会满吗？队列会满吗？很可能会，因为数组前很可能会，因为数组前端空间无法释放。因此端空间无法释放。因此数组应当有长度限制。数组应当有长度限制。空队列的特征？空队列的特征？约定：约定：front=rear队尾后地址队尾后地址入队入队(尾部插入尾部插入)：vrear=e;rear+;出队出队(头部删除头部删除)：x=vfront;front+;讨论：讨论：有有缺缺陷陷 怎样实现入队和怎样实现入队和出队操作？出队操作？3.2 队

30、列队列46问：什么叫问：什么叫“假溢出假溢出”？如何解决？如何解决？答：答：在顺序队中，当尾指针已经到了数组在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫中还有空位置，这就叫“假溢出假溢出”。3.2 队列队列解决假溢出的途径解决假溢出的途径采用循环队列采用循环队列47a3a2a10123N-1rearfronta3a2a1frontrear 0 1 2 3 .N-1新问题：新问题：在循环队列中，空队特征是在循环队列中，空队特征是front=rear；队满时也会有队满时也会有front=rear；判决条件将出现二义性！

31、判决条件将出现二义性！解决方案有三：解决方案有三：加设标志位，让删除动作使其为加设标志位，让删除动作使其为1,插入动作使其为插入动作使其为0,则可识别当前则可识别当前 front=rear 使用一个计数器记录队列中元素个数（即队列长度）；使用一个计数器记录队列中元素个数（即队列长度）；人为浪费一个单元，令人为浪费一个单元，令队满特征为队满特征为front=(rear+1)%N；48队空条件队空条件:front=rear (初始化时：初始化时：front=rear)队满条件队满条件：front=(rear+1)%N (N=maxsize)队列长度：队列长度：L=（Nrearfront）%N J2

32、 J3J1 J4 J5frontrear 选用选用空闲单元法：空闲单元法：即即front和和rear之一指向实元素，另一指向空闲元素。之一指向实元素，另一指向空闲元素。问问2：在具有在具有n个单元的循个单元的循环队列中，队满时共有多少环队列中，队满时共有多少个元素？个元素？n-1个个5 问问1：左图中队列长度左图中队列长度L=？49J6 J5J7J8 J9例例1：一循环队列如下图所示，若先删除一循环队列如下图所示，若先删除4个元素，接着再个元素，接着再插入插入4个元素，请问队头和队尾指针分别指向哪个位置个元素，请问队头和队尾指针分别指向哪个位置?J2 J3J1 J4 J5frontrear解：

33、解：由图可知，队头和队尾指针的初态分别为由图可知，队头和队尾指针的初态分别为front=1和和rear=6。frontrear删除删除4个元素后个元素后front=5；再插入；再插入4个元素后，个元素后，r=(6+4)%6=4 frontfrontfrontfrontfront50例例2：数组数组n用来表示一个循环队列，用来表示一个循环队列，f 为当前队列头元为当前队列头元素的素的前一前一位置，位置，r 为队尾元素的位置。假定队列中元素的个为队尾元素的位置。假定队列中元素的个数小于数小于n，计算队列中元素的公式为，计算队列中元素的公式为:（）（）rf （）（）（nfr）%n （）（）nrf （

34、）（）（nrf）%n4种公式哪种合理？种公式哪种合理？当当 r f 时（时（A）合理；）合理；当当 r f 时（时（C）合理；）合理；分析分析：综合综合2种情况，以（种情况，以（D）的表达最为合理的表达最为合理例例3：在一个循环队列中，若约定队首指针指向队首元素在一个循环队列中，若约定队首指针指向队首元素的的前一个前一个位置。那么，从循环队列中删除一个元素时，其位置。那么，从循环队列中删除一个元素时，其操作是操作是 先先 ，后，后 。移动队首指针移动队首指针取出元素取出元素51问：为什么要设计队列？它有什么独特用途？问：为什么要设计队列？它有什么独特用途？1.离散事件的模拟（模拟事件发生的先后

35、顺序）；离散事件的模拟（模拟事件发生的先后顺序）；2.操作系统中多道作业的处理（一个操作系统中多道作业的处理（一个CPU执行多个作执行多个作业）；业）；3.简化程序设计。简化程序设计。答：答：循环队列的操作实现循环队列的操作实现见教材见教材P64P6452循环队列的操作实现循环队列的操作实现1）初始化一空队列初始化一空队列算法要求：生成一空队列算法要求：生成一空队列算法操作：为队列分配基本容量空间算法操作：为队列分配基本容量空间 设置队列为设置队列为空队列空队列，即即 front=rear=0（也可为任意单元，如（也可为任意单元，如 2，或，或 4）;53算法：算法：Status InitQu

36、eue(SqQueue&q)/初始化空循环队列初始化空循环队列 q q.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAXSIZE);/分配空间分配空间 if(!q.base)exit(OVERFLOW);/失败，退出程序失败，退出程序 q.front=q.rear=0;/置空队列置空队列 return OK;/InitQueue;新开单元的地址为新开单元的地址为0则表示内存不足则表示内存不足54算法说明：向循环队列的队尾插入一个元素算法说明：向循环队列的队尾插入一个元素分分 析析：(1)插入前应当先判断队列是否满插入前应当先判断队列是否满

37、if(q.rear+1)%QUEUE_MAXSIZE)=q.front)return ERROR;(2）插入动作）插入动作 q.base q.rear=e;q.rear=(q.rear+1)%QUEUE_MAXSIZE;2）入队操作入队操作55Status EnQueue(SqQueue&q,QElemType e)/向循环队列向循环队列 q 的队尾加入一个元素的队尾加入一个元素 e if(q.rear+1)%QUEUE_MAXSIZE=q.front )return ERROR;q.base q.rear =e;/存储存储 q.rear=(q.rear+1)%QUEUE_MAXSIZE;/指

38、针后移指针后移 return OK;/EnQueue;2）入队操作（完整函数）入队操作（完整函数）563）出队操作）出队操作算法说明：删除队头元素，返回其值算法说明：删除队头元素，返回其值 e 分分 析：析：（1）在删除前应当判断队列是否空；在删除前应当判断队列是否空；if(q.front=q.rear)return ERROR;（2）插入动作分析；插入动作分析；因为队头指针因为队头指针front指向队头元素的位置，所以：指向队头元素的位置，所以：e=q.base q.front ;q.front=(q.front+1)%QUEUE_MAXSIZE;57Status DeQueue(SqQue

39、ue&q,QElemType&e)/若队列不空，删除循环队列若队列不空，删除循环队列 q 的队头元素，的队头元素，/由由 e 返回其值，并返回返回其值，并返回OK if(q.front=q.rear)return ERROR;/队列空队列空 e=q.base q.front ;q.front=(q.front+1)%QUEUE_MAXSIZE;return OK;/DeQueue算法：算法：58讨论（代本章小结）讨论（代本章小结）线性表、栈与队的异同点线性表、栈与队的异同点相同点：相同点：逻辑结构相同，都是线性的；都可以用顺序存储或逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列

40、是两种特殊的线性表，即链表存储；栈和队列是两种特殊的线性表，即受限的线受限的线性表性表（只是对插入、删除运算加以限制）。（只是对插入、删除运算加以限制）。不同点：不同点：运算规则不同，线性表为随机存取，而栈是只允许在一运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表端进行插入和删除运算，因而是后进先出表LIFOLIFO；队列；队列是只允许在一端进行插入、另一端进行删除运算，因而是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表是先进先出表FIFOFIFO。用途不同，线性表比较通用；堆栈用于函数调用、递归用途不同，线性表比较通用；堆栈用于函数调用、

41、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。和简化设计等。59一一 选择题选择题1.1.对于栈操作数据的原则是（对于栈操作数据的原则是（）。）。A.A.先进先出先进先出 B.B.后进先出后进先出 C.C.后进后出后进后出 D.D.不分顺序不分顺序 2.2.一个栈的输入序列为一个栈的输入序列为123n123n，若输出序列的第一个元，若输出序列的第一个元素是素是n n，输出第，输出第i i（1=i=n1=i=n）个元素是（）个元素是（）。）。A.A.不确定不确定 B.n-i+1 C.i D.n-iB.n-i+1 C.i D.n-

42、i3.3.若一个栈的输入序列为若一个栈的输入序列为1,2,3,n1,2,3,n，输出序列的第一个，输出序列的第一个元素是元素是i i，则第，则第j j个输出元素是（个输出元素是（）。）。A.i-j-1 B.i-j C.j-i+1 D.A.i-j-1 B.i-j C.j-i+1 D.不确定的不确定的4.4.栈在（栈在（）中应用。）中应用。【中山大学中山大学 1998 1998 二、二、3 3（2 2分）分）】A.A.递归调用递归调用 B.B.子程序调用子程序调用 C.C.表达式求值表达式求值 D.AD.A，5.5.有六个元素有六个元素6 6，5 5，4 4，3 3，2 2，1 1 的顺序进栈，问

43、下列哪的顺序进栈，问下列哪一个不是合法的出栈序列？（一个不是合法的出栈序列？（）A.A.5 4 3 6 1 2 B.4 5 3 1 2 6 5 4 3 6 1 2 B.4 5 3 1 2 6 C.3 4 6 5 2 1 D.2 3 4 1 5 6 C.3 4 6 5 2 1 D.2 3 4 1 5 6 60 6.在作进栈运算时,应先判别栈是否(),在作退栈运算时应先判别栈是否()。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为()。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的()分别设在这片内存空间的两端,这样,当()时，才产生上溢。

44、,:A.空 B.满 C.上溢 D.下溢 :A.n-1 B.n C.n+1 D.n/2 :A.长度 B.深度 C.栈顶 D.栈底 :A.两个栈的栈顶同时到达栈空间的中心点.B.其中一个栈的栈顶到达栈空间的中心点.C.两个栈的栈顶在栈空间的某一位置相遇.D.两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.61 7.输入序列为ABC，可以变为CBA时，经过的栈操作为（）【中山大学 1999 一、8(1分)】A.push,pop,push,pop,push,pop B.push,push,push,pop,pop,pop C.push,push,pop,pop,push,pop D.push,pop,

45、push,push,pop,pop 8.若一个栈以向量V1.n存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是()。Atop:=top+1;V top:=x B.V top:=x;top:=top+1 C.top:=top-1;V top:=x D.V top:=x;top:=top-1 9.设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A线性表的顺序存储结构 B.队列 C.线性表的链式存储结构 D.栈62 10.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时()。【北京理工大学 2001 六、3（2分）】A仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都要修改 D.队头,队尾指针都可能要修改 11.假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m 12 栈和队都是（）A顺序存储的线性结构 B.链式存储的非线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构