CH3栈和队列.ppt

《CH3栈和队列.ppt》由会员分享，可在线阅读，更多相关《CH3栈和队列.ppt（97页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、通常称，栈和队列是限定插入和删除插入和删除只能只能在表的“端点端点”进行的线性表。线性表线性表 栈栈 队列队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1 Delete(L,i,&e)Delete(S,n,&e)Delete(Q,1,&e)1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型3.1 栈的类型定义栈的类型定义3.2 栈的应用举例栈的应用举例3.3 栈类型的实现栈类型的实现3.4 队列的类型定义队列的类型定义3.5 队列类型的实现队列类型的实现一、栈的概念 栈栈（stackstack）是是插入插入和和删除删除操作限定在操

2、作限定在表尾表尾进进行的行的线性表线性表。栈的逻辑表示为：栈的逻辑表示为：S=S=（a a1 1,a,a2 2,a,an n）表尾元素表尾元素a an n称为称为栈顶栈顶(top)(top)表头元素表头元素a a1 1称为称为栈底栈底(bottom)(bottom)不含元素的空表称为不含元素的空表称为空栈空栈栈的概念栈的概念栈是限定在表的同一端进行插入或删除操作的线性表。进行插入或删除操作的一端称为栈顶，另一端称为栈底。栈的运算特性是栈的运算特性是后进先出后进先出(Last In Last In First Out-First Out-LIFOLIFO)或或先先进进后后出出(First Fir

3、st In Last Out-In Last Out-FILOFILO)k0k1.Kn-1栈顶栈底进栈出栈栈3.1 栈的类型定义栈的类型定义 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)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(

4、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 ClearStack(&S)初始条件：栈 S 已存在。操作结果：将 S 清为空栈。Push(&S,e)初始条件：栈 S 已

5、存在。操作结果：插入元素 e 为新的栈顶元素。a1a2ane Pop(&S,&e)初始条件：栈 S 已存在且非空。操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1a2anan-1 3.2栈的表示和实现栈的表示和实现顺序栈顺序栈链栈链栈/-栈的顺序存储表示栈的顺序存储表示-#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef struct SElemType *base;SElemType *top;int stacksize;SqStack;类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。顺序栈示意图顺序

6、栈示意图*base*topstacksize.a1.aian*base*topstacksize初始初始空空栈栈*top=*base;stacksize=STACK_INIT_SIZE顺序栈顺序栈 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;顺顺 序序 栈栈 的的 操操 作作 实实 现

7、现(GetTop)栈 S非 空,则 用 e返 回 栈 S中 栈 顶 元 素 的 值，并返回OK,则返回ERROR。Status GetTop(SqStack s,SElemType&e)ifif(s.top=s.base)returnreturn ERROR;e=*(s.top-1);return OK;/*GetTop */*base*topstacksize.a1.aianse*e=*(s.top-1);Status Pop(SqStack&S,SElemType&e)/若栈不空，则删除S的栈顶元素，/用e返回其值，并返回OK；/否则返回ERROR if(S.top=S.base)retu

8、rn ERROR;e=*-S.top;/-S.top;e=*S.top;return OK;*base*topstacksize.a1.aiansee=*(-s-top);e=*(-s-top);Status Push(SqStack&S,SElemType 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.s

9、tacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;/*S.top=e;S.top+;return OK;插入新的栈顶元素时，堆栈变化示意e*base*topstacksize.a1.aians*base*topstacksize.a1.aians栈满时，追加存储空间栈满时，追加存储空间*(s-top+)=e;*(s-top+)=e;e思考题：思考题：一个栈的入栈序列为：一个栈的入栈序列为：1 2 3，那么可能得到的出栈序，那么可能得到的出栈序列是什么？列是什么？2.设将整数设将整数1，2，3，4依次进栈，但只要出栈时栈非空，依次进栈，但只要出栈时栈非

10、空，则可将出栈操作按任何次序夹入其中，请回答下述问则可将出栈操作按任何次序夹入其中，请回答下述问题：题：(1)若入、出栈次序为若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为何？则出栈的数字序列为何？(2)能否得到出栈序列能否得到出栈序列1423和和1432?并说明为什么不能得到或并说明为什么不能得到或者如何得到。者如何得到。(3)请分析请分析 1，2，3，4 的的24种排列中，哪些序列是可以通种排列中，哪些序列是可以通过相应的入出栈操作得到的。过相应的入出栈操作得到的。答：答：3 2 1，2 3

11、 1，2 1 3，1 3 2，1 2 3。不能不能 有有 312 仅当两个栈顶相遇时，才产生上溢，即所有可用空间仅当两个栈顶相遇时，才产生上溢，即所有可用空间已用完。对每个栈可用的最大空间就可能大于整个可用已用完。对每个栈可用的最大空间就可能大于整个可用空间的一半空间的一半m/2。栈1栈2空闲栈bot1top1bot2top21m2.栈的系统存储空间共享。（两栈共享）栈的系统存储空间共享。（两栈共享）3.1.4 链栈的表示和实现1.栈的链式存储表示栈的链式存储表示typedef struct SNode ElemType data;struct SNode*next;SNode,*LinkSt

12、ack;问：问：链栈中为何不设置头结点链栈中为何不设置头结点?答：链栈不需要在头部附加头结点，因答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要行操作，反而使算法更复杂，所以只要有链表的首指针就可以了。有链表的首指针就可以了。anan-1ai+1aia1栈顶栈顶栈底栈底3.链栈基本操作的实现链栈基本操作的实现初始化初始化S=NULL；入栈入栈申请结点申请结点p；p-data=e;p-next=S;S=p;判空：判空：S=NULL出栈：出栈：

13、if(S=NULL)return ERROR;else p=S;S=p-next;e=p-data;free(p);anan-1ai+1aia1栈顶栈顶栈底栈底练习(1)栈是限定在_处进行插入或删除操作的线性表。A.端点 B.栈底 C.栈顶 D.中间(2)4个元素按A、B、C、D顺序连续进S栈，进行Pop(S,x)运算后，x的值是_。A.A B.B C.C D.D(3)栈的特点是_。A.先进先出 B.后进先出 C.后进后出 D.不进不出(4)栈与一般线性表的区别主要在_方面。A.元素个数 B.元素类型C.逻辑结构 D.插入、删除元素的位置(5)一个栈的输入序列为1，2，3，4，5，则下列序列中

14、不可能是栈的输出序列的是_。A.2，3，4，1，5，B.5，4，1，3，2，C.2，3，1，4，5，D.1，5，4，3，2B3.3 栈的应用举例栈的应用举例例一、例一、数制转换数制转换例二、例二、括号匹配问题括号匹配问题例三例三 表达式求值表达式求值 例一、例一、数制转换数制转换 算法基于原理：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计计算算顺顺序序输输出出顺顺序序*base*topstacksize4052先进后出：先进后出：数据生

15、成的顺序：数据生成的顺序：4,0,5,24,0,5,2 读出的顺序：读出的顺序：2,5,0,42,5,0,4void 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例2：括号匹配的检查例如：例如：（）（）（）（）（）（）（）算法的设计思想：算法的设计思想：1）凡出现左括弧，则进栈；）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空）凡出现右括弧，首先检查栈是否空若栈空，则表明该若栈空，则表明该“右括弧右

16、括弧”多余多余否则和栈顶元素比较，否则和栈顶元素比较，若相匹配，则若相匹配，则“左括弧出栈左括弧出栈”否则表明不匹配否则表明不匹配3）表达式检验结束时，）表达式检验结束时，若栈空，则表明表达式中匹配正确若栈空，则表明表达式中匹配正确否则表明否则表明“左括弧左括弧”有余有余Status Compare()InitStack(S);flag=TURE;while（ch=getchar()）！）！=#）&flag）switch(ch)case(:case :caxe :Push(S,ch);break;case):if(Pop(S,e)=ERROR|e!=()flag=FALSE;break;cas

17、e :if(Pop(S,e)=ERROR|e!=)flag=FALSE;break;case :if(Pop(S,e)=ERROR|e!=)flag=FALSE;break;/switch if(flag&ch=#&StackEmpty(S)return TRUE;else return FALSE;例例3 3：栈的应用栈的应用-表达式求值表达式求值一一.表达式表达式 表达式表达式由操作数、运算符和界限符组成。由操作数、运算符和界限符组成。操作数操作数（operand)：常数或变量常数或变量运算符运算符（operator)算术运算符：算术运算符：+、-、*、/、*等等关系运算符：、关系运算符：

18、、逻辑运算符：逻辑运算符：AND、OR、NOT界界限限符符（delimiter):左左右右括括号号、表表达达式式结结束束符符等等例例3 3：栈的应用：栈的应用-表达式求值表达式求值二二.算符优先关系表算符优先关系表 先乘除，后加减：先乘除，后加减：*、/+、先括号内，后括号外：先括号内，后括号外：同级按左结合律：同级按左结合律：以下为不允许的：以下为不允许的：）与（、（与、与）与（、（与、与）+-*/（）#+-*/（）#=12三.算术表达式求值的算符优先算法使用使用DS算符栈算符栈OPTR：有效算符；有效算符；操作数栈操作数栈OPND：有效操作数，运算结果。有效操作数，运算结果。算法思想算法思

19、想（1）初始化：）初始化：OPND置为空栈，将放入置为空栈，将放入OPTR栈底栈底（2）依次读入表达式中的每个字符，）依次读入表达式中的每个字符，若是操作数，则入若是操作数，则入OPND栈；栈；若是算符，则和若是算符，则和OPTR栈顶算符进行优先级比较：栈顶算符进行优先级比较：若栈顶算符优先，则执行相应运算，结果存入若栈顶算符优先，则执行相应运算，结果存入OPND栈栈 若与栈顶算符相等，则作（）或处理。若与栈顶算符相等，则作（）或处理。若栈顶算符低于，该算符入若栈顶算符低于，该算符入OPTR栈。栈。（3）重复（重复（2），直到表达式求值完毕），直到表达式求值完毕 （读入的是（读入的是#，且，且

20、OPTR栈顶元素也为栈顶元素也为#）3算法描述算法描述OperandType Evaluateexpress()InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar();while(c!=#|GetTop(OPTR)!=#)if（c为操作数）为操作数）Push(OPND,c);c=getchar();/不是运算符不是运算符进栈进栈 else switch Precede(GetTop(OPTR),c)case:/退栈并将运算结果入栈退栈并将运算结果入栈 Pop(OPTR,thrta);Pop(OPND,b);Pop(OPND,a);Pus

21、h(OPND,Operate(a,theta,b);break;/switch/Evaluateexpress输入：3*（7+3*6/2-5#)运算对象栈运算符栈3#*(7+3*618/2916-51133有关思考与提示有关思考与提示算符优先表的存储和表示算符优先表的存储和表示;栈的选择（静态顺序栈栈的选择（静态顺序栈-用数组表示）用数组表示）判断判断c是否为算符。是否为算符。Operate(a,theta,b)的实现的实现3.3 栈与递归的实现一、函数调用与返回通常，当一个函数调用另一个函数时，在执行被调用函数前系统要预先做三件事情：将所有的实参和函数返回地址等信息传递给被调用函数；为被调用

22、函数的局部变量分配存储空间将控制转移到被调用函数的入口处。而而在在从从被被调调用用函函数数返返回回调调用用函函数数之之前前，系系统统也需要做如下三件事情：也需要做如下三件事情：保存被调用函数的计算结果；保存被调用函数的计算结果；释释放放为为被被调调用用函函数数局局部部变变量量分分配配的的数数据据空空间；间；按返回地址将控制转移给调用函数。按返回地址将控制转移给调用函数。二、函数的嵌套调用当多个函数构成嵌套调用时，系统按照先调用后返回的原则进行工作。这种信息的传递和控制转移符合后进先出的原则，使用栈来实现是非常自然的。例：设有一个主程序，它调用函数a，函数a又调用函数b，函数b又调用函数c，（见

23、下页），其中r，s，t分别表示中断地址，我们可以用一个栈来描述调用情况（见下页）r主主程程序序srrrs函函数数1rst函函数数2rst函函数数3多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回！例如：void main()void a()void b()a();b();/main /a /bMain的数据区函数a的数据区函数b的数据区 注：系统将整个程序运行期间所需要的存储空间都利用一个工作栈来管理，每当调用（或执行）一个函数时，就为它在栈顶分配一个存储区；每当退出（或执行完）一个函数时，就释放为它所分配的存储区；当前工作的函数的数据区总在工作栈的当前

24、栈顶位置。三、递归函数的执行过程递归函数的执行过程类似于嵌套调用时的情况，只不过是在直接递归时的调用函数和被调用函数是同一个函数罢了递归是程序设计中一个强有力的工具，可以解决许多实际应用问题：递归定义的数学函数递归的数据结构问题的定义是递归的 递归问题递归问题例：例：Hanoi塔问题塔问题分析：分析：n n个个 X Y Z (1)(1)将将X X轴上的轴上的n-1n-1个盘子借助个盘子借助Z Z轴移到轴移到Y Y轴上；轴上；(2)(2)将将X X轴上的余下的轴上的余下的1 1个盘子移到个盘子移到Z Z轴上；轴上；(3)(3)将将Y Y轴上的轴上的n-1n-1个盘子借助个盘子借助X X轴移到轴移

25、到Z Z轴上轴上求解算法及调用示意图求解算法及调用示意图void void hanoi(inthanoi(int n,char n,char x,char y,char z)x,char y,char z)if(n=1)move(x,1,z);if(n=1)move(x,1,z);else hanoi(n-else hanoi(n-1,x,z,y);1,x,z,y);move(x,n,z);move(x,n,z);hanoi(n-hanoi(n-1,y,x,z);1,y,x,z);Hanoi(3,a,b,c)Hanoi(3,a,b,c)Hanoi(1,a,b,c)Hanoi(1,b,c,a)H

26、anoi(1,c,a,b)Hanoi(1,a,b,c)Hanoi(2,a,c,b)Hanoi(2,b,a,c)move(a,c)move(a,c)move(b,c)move(b,a)move(c,b)move(a,b)move(a,c)n=3的调用示意图的调用示意图二、递归过程与递归工作栈二、递归过程与递归工作栈1.递归过程递归过程调用过程调用过程回推过程回推过程2.递归工作栈递归工作栈 目的目的：保证递归函数正确执行，系统设立工作栈作：保证递归函数正确执行，系统设立工作栈作为递归函数运行期间使用的数据存储区。为递归函数运行期间使用的数据存储区。内容：内容：函数返回地址函数返回地址 本次调用时

27、与形参结合的实参本次调用时与形参结合的实参 本层的局部变量值本层的局部变量值3.4 队列队列3.4.1 队列的抽象数据类型的定队列的抽象数据类型的定义义3.4.2 链队列的表示和实现链队列的表示和实现3.4.3 循环队列的表示和实现循环队列的表示和实现一、队列的概念一、队列的概念队列队列（queuequeue）是限定仅在一端插入是限定仅在一端插入,另一端删除的线性表。另一端删除的线性表。允许插入的一端叫允许插入的一端叫队尾队尾(rear),(rear),允许删除的一端叫允许删除的一端叫队头队头(front),(front),不含元素的空表称为不含元素的空表称为空队列空队列队列的运算特性是先进先

28、出队列的运算特性是先进先出(First In First Out-First In First Out-FIFOFIFO)3.4 3.4 队列的表示和实现队列的表示和实现出队列入队列a1 a2 .an队头队尾例如：例如：到到医医院院看看病病，首首先先需需要要到到挂挂号号处处挂挂号号，然然后后，按按号码顺序救诊。号码顺序救诊。乘乘坐坐公公共共汽汽车车，应应该该在在车车站站排排队队，车车来来后后，按按顺顺序上车。序上车。在在WindowsWindows这这类类多多任任务务的的操操作作系系统统环环境境中中，每每个个应应用用程程序序响响应应一一系系列列的的“消消息息”，像像用用户户点点击击鼠鼠标标；拖

29、拖动动窗窗口口这这些些操操作作都都会会导导致致向向应应用用程程序序发发送送消消息息。为为此此，系系统统将将为为每每个个应应用用程程序序创创建建一一个个队队列列，用用来来存存放放发发送送给给该该应应用用程程序序的的所所有有消消息息，应应用用程程序序的的处处理理过过程程就就是是不不断断地地从从队队列列中中读读取取消消息息，并依次给予响应。并依次给予响应。ADT Queue 数据对象：数据对象：Dai|aiElemSet,i=1,2,.,n,n0 数据关系：数据关系：R1|ai-1,ai D,i=2,.,n 约定其中a1 端为队列头队列头，an 端为队列尾队列尾基本操作基本操作：ADT Queue队

30、列的基本操作：队列的基本操作：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)初始条件：初始条件：队列Q已存在。操作结果：操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。Q

31、ueueLength(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为非空队列。操作结果：操作结果：删除Q的队头元素，并用e返回其值。a1a2an 3.4.2 队列类

32、型的实现队列类型的实现链队列链队列链式映象循环队列循环队列顺序映象 typedef struct QNode/结点类型结点类型 QElemType data;struct QNode *next;QNode,*QueuePtr;链队列链队列链式映象typedef struct /链队列类型链队列类型 QueuePtr front;/队头指针队头指针 QueuePtr rear;/队尾指针队尾指针 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空队列空队列如：LinkQueue Q;Status InitQueue(LinkQueue&Q)/构造一个空队列Q Q

33、.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);/存储分配失败 Q.front-next=NULL;return OK;链队列链队列示意图示意图frontrearBfrontrearAfrontrearBA(a)空队列空队列(b)元素元素“A”入队列入队列(c)元素元素“B”入队列入队列(d)元素元素“A”出队列出队列 Status EnQueue(LinkQueue&Q,QElemType e)/插入元素e为Q的新的队尾元素 p=(QueuePtr)malloc(sizeof(QNode);if(

34、!p)exit(OVERFLOW);/存储分配失败 p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;frontrearBA(d)元素元素“A”出队列出队列思考：思考：元素元素“B”再出队列，出现什么情况，该如何处理？再出队列，出现什么情况，该如何处理？思考：思考：再执行删除操作，还能成功吗？再执行删除操作，还能成功吗？frontrearB Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，/用 e 返回其值，并返回OK；否则返回ERROR if(Q.front=Q.rear

35、)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;删除时的三种情形：删除时的三种情形：a.删除前已空；删除前已空；b.删删除除前前只只有有一一个个结结点点，删删除除后后为为空空队列；队列；c.其他情形（删除前结点数其他情形（删除前结点数1）思考：思考：在什么情况下出队要修改在什么情况下出队要修改q.rear(队尾队尾)指针？为指针？为什么？什么？frontrearB思考：思考：基本操作基本操作GetHead 如何实现？如何实现？Status

36、 DestroyQueue(LinkQueue&Q)/销毁队列Q while(Q.front)P=Q.front-next;free(Q.front);Q.front=P;Q.rear=Q.front;return OK;#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base;/动态分配存储空间 int front;/头指针，若队列不空，/指示队列头元素的位置 int rear;/尾指针，若队列不空，指示 /队列尾元素 的下一个位置 SqQueue;循环队列循环队列顺序映象采用顺序存储结构采用顺序存储结构,如果定义：如果定义：Sq

37、Queue Q；约定约定:1)初始空队列：初始空队列：Q.front=Q.rear=0;2)插入新的元素时插入新的元素时,Q.rear+;3)删除队头元素时删除队头元素时,Q.front+;J1J2J3Q.frontQ.rearJ3Q.frontQ.rearJ5J6Q.frontQ.rearQ.rearQ.front102354初始时初始时：Q.front=Q.rear=0;Q.front=Q.rear=0;空队列条件空队列条件：Q.front=Q.rear;Q.front=Q.rear;出队时出队时：if Q.rear=Q.front return ERROR /if Q.rear=Q.fr

38、ont return ERROR /队空队空 else e=else e=Q.baseQ.frontQ.baseQ.front;Q.frontQ.front=Q.front+1;=Q.front+1;入队时入队时：if Q.rear=if Q.rear=MAXQSIZE ERROR /ERROR /队满队满 else else Q.baseQ.rearQ.baseQ.rear=e;=e;Q.rearQ.rear=Q.rear+1=Q.rear+1；队列长度：队列长度：Q.rear-Q.frontQ.rear-Q.front 3.4 3.4 队列的表示和实现队列的表示和实现 3.4 3.4 队列

39、的表示和实现队列的表示和实现考虑队满条件，即当考虑队满条件，即当Q.rear=Q.rear=MAXQSIZE时，是否整个存储空间都已占时，是否整个存储空间都已占用用？MAXQSIZE-10Q.rearQ.front此时，Q.rear=MAXQSIZE 且队满。MAXQSIZE-10Q.rearQ.front此时，尽管此时，尽管Q.rear=MAXQSIZE,Q.rear=MAXQSIZE,但但队列中实际元素并不足队列中实际元素并不足MAXQSIZEMAXQSIZE个，个，仍有仍有Q.frontQ.front个空闲单元，称这种情个空闲单元，称这种情形为形为“假溢出假溢出”。循环列表循环列表-解决

40、数组越界但未占满空间的办法10MAXQSIZE-1.Q.frontQ.rear.队列当当Q.rear Q.front时时:Q.rear Q.front =队列中元素个数队列中元素个数当当Q.rear Q.front时时:Q.rear Q.front =队列中元素个数队列中元素个数当当Q.rear Q.front时时:Q.rear Q.front+MAXQSIZE=队列中元素个数队列中元素个数当当Q.rear=Q.front时时:队列是队列是空空或或满满return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;Status EnQueue(SqQueue&Q,ElemTy

41、pe e)/插入元素e为Q的新的队尾元素 if(Q.rear+1)%MAXQSIZE=Q.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;3.5 队列应用队列是一种简单而

42、基本的数据结构队列是一种简单而基本的数据结构,在各在各种软件系统中应用十分广泛，例如：种软件系统中应用十分广泛，例如：CPUCPU资源的竞争问题资源的竞争问题（类似地：利用队列来管理各种计算机的资源。）类似地：利用队列来管理各种计算机的资源。）主机与外部设备之间速度不匹配的问题主机与外部设备之间速度不匹配的问题在主机、磁盘文件和终端机之间提供一个读写缓在主机、磁盘文件和终端机之间提供一个读写缓冲；冲；用于实时应用程序（如解决运行程序与键盘处理用于实时应用程序（如解决运行程序与键盘处理程序的异步操作问题。）程序的异步操作问题。）各种应用系统中的事件规划、事件模拟以及各种应用系统中的事件规划、事件

43、模拟以及图中的一些非递归的搜索算法等。图中的一些非递归的搜索算法等。汽车加油站。汽车加油站。随着城市里汽车数量的急速增长，汽车加油随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，三段是进入出口

44、处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加程，就需要设置加油车道数加2 2个队列。个队列。模拟打印机缓冲区。模拟打印机缓冲区。在主机将数据输出到打印机时，会出现主机在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，种办法：为打印机设置一个打印数据缓冲区，当主机

45、需要打印数据时，先将数据依次写入当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队由此可见，打印机缓冲区实际上就是一个队列结构。列结构。CPUCPU分时系统分时系统在一个带有多个终端的计算机系统中，同时在一个带有多个终端的计算机系统中，同时有多个用户需要使用有多个用

46、户需要使用CPUCPU运行各自的应用程运行各自的应用程序，它们分别通过各自的终端向操作系统提序，它们分别通过各自的终端向操作系统提出使用出使用CPUCPU的请求，操作系统通常按照每个的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个请求在时间上的先后顺序，将它们排成一个队列，每次把队列，每次把CPUCPU分配给当前队首的请求用分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作程序运行完毕或用完规定的时间片后，操作系统再将系统再将CPUCPU分配给新的队首请求用户，这分配给新的队首请求用户，这样

47、即可以满足每个用户的请求，又可以使样即可以满足每个用户的请求，又可以使CPUCPU正常工作。正常工作。1.掌掌握握栈栈和和队队列列类类型型的的特特点点，并并能能在在相相应应的应用问题中正确选用它们。的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，特别应熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。注意栈满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。现算法，特别注意队满和队空的描述方法。4.理解递归算法执行过程中栈的状态变化过理解递归算法执行过程中栈的状

48、态变化过程。程。本章学习要点本章学习要点本章习题1.填空题填空题（1）设栈设栈S和队列和队列Q的初始状态皆为空，元的初始状态皆为空，元素素a1，a2，a3，a4，a5和和a6依次通过一个栈，依次通过一个栈，一个元素出栈后即进入队列一个元素出栈后即进入队列Q，若，若6个元素个元素出队列的顺序是出队列的顺序是a3，a5，a4，a6，a2，a1，则则栈栈S至少应该容纳至少应该容纳_个元素。个元素。42.比较栈和队列的相同点和不同点，举例说明。比较栈和队列的相同点和不同点，举例说明。3.对于算术表达式对于算术表达式3(52)7，用栈存储式，用栈存储式子中的运算对象和运算符，试说明该算术表达子中的运算对

49、象和运算符，试说明该算术表达式的运算过程。式的运算过程。4.循环队列的优点是什么？如何判断它的空和循环队列的优点是什么？如何判断它的空和满？满？5.试述队列的链式存储结构和顺序存储结构的试述队列的链式存储结构和顺序存储结构的优缺点。优缺点。题目题目2：利用深度为：利用深度为n的两个栈的两个栈S1，S2模拟一个队列，模拟一个队列，实现队列的入队列、出队列和判空运算。实现队列的入队列、出队列和判空运算。SqStack ST；定义一个顺序栈；已知栈的三个运算定义如下：PUSH(&ST,x)：元素x入ST栈；POP(&ST,&x)：ST栈顶元素出栈，赋给变量x；StackEmpty(ST)：判ST栈是

50、否为空。题目说明：栈的特点是后进先出，队列的特点是先进先出。用两个栈S1和S2模拟一个队列时，S1作输入栈，逐个元素压栈，以此模拟队列元素的入队列。当需要出队列时，S2作输出栈，相当于队列的出队列，若S2为空，将栈S1退栈并逐个压入栈S2中，S1中最先入栈的元素，在S2中处于栈顶。S2退栈，实现了队列的先进先出。队列为空：只有栈S2为空且S1也为空，才算是队列空。这里给出入队列这里给出入队列EnQueue算法描述如下：算法描述如下：Status EnQueue(SqStack&S1,SqStack&S2,SElemType x)/将x入队列，若入队列成功返回1。否则返回0。if(S1.top=