《第3章-栈和队列-数据结构课件.ppt》由会员分享，可在线阅读，更多相关《第3章-栈和队列-数据结构课件.ppt（115页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第2 2章章 线性表线性表第第3 3章章 栈和队列栈和队列第第4 4章章 串串第第5 5章章 数组和广义表数组和广义表 可表示为可表示为：（：（a a1 1,a,a2 2 ,a,an n）线性结构线性结构3.1 栈栈3.2栈栈的应用举例的应用举例3.3栈与递归的实现栈与递归的实现3.4队列队列教学内容教学内容国际教育学院国际教育学院第第3 3章章栈和队列栈和队列1.1.掌握栈和队列的掌握栈和队列的特点特点，并能在相应的应用问，并能在相应的应用问题中正确选用题中正确选用2.2.熟练掌握栈的熟练掌握栈的两种存储结构两种存储结构的基本操作实现的基本操作实现算法，特别应注意算法，特别应注意栈满和栈空
2、栈满和栈空的条件的条件3.3.熟练掌握熟练掌握循环队列和链队列循环队列和链队列的基本操作实现的基本操作实现算法，特别注意算法，特别注意队满和队空队满和队空的的条件条件4.4.理解理解递归算法递归算法执行过程中栈的状态变化过程执行过程中栈的状态变化过程 教学目标教学目标国际教育学院国际教育学院栈（栈（Stack）1.1.定义定义2.2.逻辑结构逻辑结构3.3.存储结构存储结构4.4.运算规则运算规则5.5.实现方式实现方式队列（队列（Queue）1.1.定义定义2.2.逻辑结构逻辑结构3.3.存储结构存储结构4.4.运算规则运算规则5.5.实现方式实现方式国际教育学院国际教育学院只能在只能在栈顶
3、栈顶运算，且访问结点时依运算，且访问结点时依照照后进先出后进先出（LIFOLIFO）或或先进后出先进后出（FILOFILO）的原则的原则4.4.运算规则运算规则关键是编写关键是编写入栈入栈和和出栈出栈函数，具体函数，具体实现依顺序栈或链栈的不同而不同实现依顺序栈或链栈的不同而不同基本操作有基本操作有入栈、出栈、读栈顶元入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空素值、建栈、判断栈满、栈空等等5.5.实现方式实现方式国际教育学院国际教育学院栈是一种特殊的线性表，它只能在表的一端（栈顶）栈是一种特殊的线性表，它只能在表的一端（栈顶）进行插入和删除运算进行插入和删除运算栈与一般线性表的区别：仅在于
4、栈与一般线性表的区别：仅在于运算规则运算规则不同不同“进进”压入压入=PUSH=PUSH（)“出出”弹出弹出=POP()=POP()一般线性表一般线性表 逻辑结构：一对一逻辑结构：一对一 存储结构：顺序表、链表存储结构：顺序表、链表 运算规则：随机运算规则：随机、顺序存取顺序存取栈栈逻辑结构：一对一逻辑结构：一对一 存储结构：顺序存储结构：顺序栈栈、链、链栈栈运算规则：运算规则：后进先出后进先出栈与一般线性表的区别栈与一般线性表的区别国际教育学院国际教育学院“进进”压入压入=PUSH=PUSH（)“出出”弹出弹出=POP()=POP()国际教育学院国际教育学院顺序栈的表示顺序栈的表示空栈空栈b
5、ase=topbase=top 是是栈空标志栈空标志stacksize=4stacksize=4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top top 指示真正的指示真正的栈顶元素之上栈顶元素之上的下标地址的下标地址栈满时的处理方法：栈满时的处理方法：1 1、报错报错,返回操作系统。返回操作系统。2 2、分配更大的空间分配更大的空间，作为栈的存储空，作为栈的存储空间间,将原栈的内容移入新栈。将原栈的内容移入新栈。国际教育学院国际教育学院#defineSTACK_INIT_SIZE 100typedefstructSElemType*ba
6、se;SElemType*top;intstacksize;SqStack;顺序栈的表示顺序栈的表示存储空间分配增量：存储空间分配增量：STACKINCREMENT存储空间初始分配量存储空间初始分配量国际教育学院国际教育学院StatusInitStack(SqStack&S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stackSize=STACK_INIT_SIZE;returnOK;顺序栈初始化顺序栈初始化国际教育学院国际教育学院求顺
7、序栈的长度求顺序栈的长度intStackLength(SqStackS)returnS.topS.base;basetopAB国际教育学院国际教育学院StatusClearStack(SqStackS)if(S.base)S.top=S.base;returnOK;清空顺序栈清空顺序栈basetop3120国际教育学院国际教育学院(1)(1)判断是否栈满，若满则出错判断是否栈满，若满则出错(2)(2)元素元素e e压入栈顶压入栈顶(3)(3)栈顶指针加栈顶指针加1 1顺序栈进栈顺序栈进栈StatusPush(SqStack&S,SElemTypee)if(S.top-S.base=S.stac
8、ksize)/栈满栈满,报错报错returnERROR;*S.top+=e;returnOK;*S.top=e;top+;ABCtopbase国际教育学院国际教育学院StatusPush(SqStack&S,SElemTypee)if(S.top-S.base=S.stacksize)/栈满栈满,追加存储空间追加存储空间S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stack
9、size+=STACKINCREMENT;*S.top+=e;returnOK;国际教育学院国际教育学院(1)(1)判断是否栈空，若空则出错判断是否栈空，若空则出错(2)(2)获取栈顶元素获取栈顶元素e e(3)(3)栈顶指针减栈顶指针减1 1顺序栈出栈顺序栈出栈StatusPop(SqStack&S,SElemType&e)if(S.top=S.base)/栈空栈空returnERROR;e*-S.top;returnOK;-top;e=*S.top;ABCtopbase国际教育学院国际教育学院(1)(1)判断是否空栈，若空则返回错误判断是否空栈，若空则返回错误(2)(2)否则通过栈顶指针获
10、取栈顶元素否则通过栈顶指针获取栈顶元素取顺序栈栈顶元素取顺序栈栈顶元素StatusGetTop(SqStackS,SElemType&e)if(S.top=S.base)returnERROR;/栈空栈空e=*(S.top1);returnOK;e=*(S.top-);?ABCtopbase国际教育学院国际教育学院435612435612中到了中到了1212顺序不能实现；顺序不能实现；135426135426可以实现。可以实现。1.1.如果一个栈的输入序列为如果一个栈的输入序列为123456123456，能否，能否得到得到435612435612和和135426135426的出栈序列？的出栈序
11、列？练习练习国际教育学院国际教育学院练习练习top不变不变top=0top+top-D3.3.在一个具有在一个具有n n个单元的顺序栈中，假设以地址个单元的顺序栈中，假设以地址高端作为栈底，以高端作为栈底，以toptop作为栈顶指针，则当作进作为栈顶指针，则当作进栈处理时，栈处理时，toptop的变化为的变化为国际教育学院国际教育学院考研试题考研试题b0t0t1b10m-1V双栈共享一个栈空间双栈共享一个栈空间优点：互相调剂，灵活性强，减少溢出机会优点：互相调剂，灵活性强，减少溢出机会国际教育学院国际教育学院将编号为将编号为0 0和和1 1的两个栈存放于一个数组空间的两个栈存放于一个数组空间V
12、mVm中，栈底分别处于数组的两端。当第中，栈底分别处于数组的两端。当第0 0号栈号栈的栈顶指针的栈顶指针top0top0等于等于-1-1时该栈为空，当第时该栈为空，当第1 1号号栈的栈顶指针栈的栈顶指针top1top1等于等于m m时该栈为空。两个栈时该栈为空。两个栈均从两端向中间增长（如下图所示）均从两端向中间增长（如下图所示）。考研试题考研试题b0t0t1b10m-1V国际教育学院国际教育学院voidDblpush(DblStack&s,SElemTypex,inti)；/把把x插入到栈插入到栈i的栈的栈intDblpop(DblStack&s,inti,SElemType&x)；/退掉位
13、于栈退掉位于栈i栈顶的元素栈顶的元素intIsEmpty(DblStacks,inti)；/判栈判栈i空否空否,空返回空返回1,否则返回否则返回0intIsFull(DblStacks)；/判栈满否判栈满否,满返回满返回1,否则返回否则返回0试编写判断栈空、栈满、进栈和出栈试编写判断栈空、栈满、进栈和出栈四个算法的函数四个算法的函数(函数定义方式如下）函数定义方式如下）考研试题考研试题国际教育学院国际教育学院b0t0t1b10m-1V栈空：栈空：topi=boti itopi=boti i表示栈的编号表示栈的编号 栈满：栈满：top0+1=top1 top0+1=top1 或或top1-1=t
14、op0top1-1=top0提示提示国际教育学院国际教育学院链栈的初始化链栈的初始化voidInitStack(LinkStack&S)S=NULL;S国际教育学院国际教育学院判断链栈是否为空判断链栈是否为空StatusStackEmpty(LinkStackS)if(S=NULL)returnTRUE;elsereturnFALSE;国际教育学院国际教育学院链栈进栈链栈进栈StatusPush(LinkStack&S,SElemTypee)p=(LinkStack)malloc(sizeof(Snode);if(!p)exit(OVERFLOW);p-data=e;p-next=S;S=p;
15、returnOK;pS国际教育学院国际教育学院链栈进栈链栈进栈StatusPush(LinkStack&S,SElemTypee)p=(LinkStack)malloc(sizeof(Snode);if(!p)exit(OVERFLOW);p-data=e;p-next=S;S=p;returnOK;pSe国际教育学院国际教育学院链栈进栈链栈进栈StatusPush(LinkStack&S,SElemTypee)p=(LinkStack)malloc(sizeof(Snode);if(!p)exit(OVERFLOW);p-data=e;p-next=S;S=p;returnOK;pSe国际教
16、育学院国际教育学院链栈进栈链栈进栈StatusPush(LinkStack&S,SElemTypee)p=(LinkStack)malloc(sizeof(Snode);if(!p)exit(OVERFLOW);p-data=e;p-next=S;S=p;returnOK;pSeS国际教育学院国际教育学院链栈出栈链栈出栈Status pop(LinkStack&s,SElemType&e)if(StackEmpty(S)exit(Stackisempty);e=s-data;p=s;s=s-next;free(p);return OK;SAe=A国际教育学院国际教育学院链栈出栈链栈出栈Stat
17、us pop(LinkStack&s,SElemType&e)if(StackEmpty(S)exit(Stackisempty);e=s-data;p=s;s=s-next;free(p);return OK;SAe=Ap国际教育学院国际教育学院链栈出栈链栈出栈Status pop(LinkStack&s,SElemType&e)if(StackEmpty(S)exit(Stackisempty);e=s-data;p=s;s=s-next;free(p);return OK;SAe=ApS国际教育学院国际教育学院链栈出栈链栈出栈Status pop(LinkStack&s,SElemTyp
18、e&e)if(StackEmpty(S)exit(Stackisempty);e=s-data;p=s;s=s-next;free(p);return OK;e=AS国际教育学院国际教育学院取链栈栈顶元素取链栈栈顶元素SElemTypeGetTop(LinkStackS)if(StackEmpty(S)exit(Stack is empty);else returnSdata;国际教育学院国际教育学院3.2 3.2 栈的应用举例栈的应用举例例例1 1：数制转换（十转：数制转换（十转N N）用栈暂存低位值用栈暂存低位值例例2 2：括号匹配的检验括号匹配的检验用栈暂存左括号用栈暂存左括号例例3 3
19、：行编辑程序：行编辑程序 用栈暂存字符用栈暂存字符例例4 4：迷宫求解：迷宫求解 用栈实现递归调用用栈实现递归调用例例5 5：表达式求值：表达式求值用栈暂存运算符用栈暂存运算符简化了程序设计的问题简化了程序设计的问题国际教育学院国际教育学院迷迷宫宫求求解解国际教育学院国际教育学院从入口出发，按某一方向向未走过的前方探索从入口出发，按某一方向向未走过的前方探索若能走通，则到达新点，否则试探下一方向若能走通，则到达新点，否则试探下一方向 ;若所有的方向均没有通路，则沿原路返回前一点，若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探换下一个方向再继续试探直到所有可能的通路都探索到，
20、或找到一条通路，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。或无路可走又返回到入口点。求解思想：求解思想：回溯法回溯法迷宫求解迷宫求解国际教育学院国际教育学院需要解决的问题：需要解决的问题：1、表示迷宫的数据结构、表示迷宫的数据结构2、试探方向、试探方向3、栈的设计、栈的设计4、防止重复到达某点，避免发生死循环、防止重复到达某点，避免发生死循环迷宫求解迷宫求解国际教育学院国际教育学院1、表示迷宫的数据结构、表示迷宫的数据结构表示一个表示一个m行行n列迷宫：列迷宫：用用mazemn表示，表示，0im,0jx=xx表表3.13.1算符间的优先关系算符间的优先关系国际教育学
21、院国际教育学院(1)(2)OPND置空置空,#入入OPTR依次读入字符依次读入字符ch，直到表达式求值完毕（，直到表达式求值完毕（OPTR的的栈顶元素和当前读入的字符均为栈顶元素和当前读入的字符均为“#”）if(ch是操作数是操作数)则则ch进进OPND栈栈else比较比较OPTR栈顶元素和栈顶元素和ch的优先级的优先级case:栈顶运算符退栈、计算，结果进栈顶运算符退栈、计算，结果进OPND栈栈算符优先算法算符优先算法设定两栈设定两栈：OPND-操作数或运算结果操作数或运算结果OPTR-运算符运算符国际教育学院国际教育学院OperandTypeEvaluateExpression()Init
22、Stack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar();while(c!=#|GetTop(OPTR)!=ch)if(!In(c,OP)Push(OPND,c);c=getchar();/非运算符非运算符,则进则进栈栈elseswitch(Precede(GetTop(OPTR,c)case:/退栈退栈,并将运算结果入栈并将运算结果入栈Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;/switch/whilereturnGetTop(OPND)
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)国际教育学院国际教育学院3.3 3.3 栈与递归的实现栈与递归的实现n递归的定义递归的定义 若一个对象部分
24、地包含它若一个对象部分地包含它自己自己,或用它自己给自己定义或用它自己给自己定义,则称这个对则称这个对象是递归的；若一个过程象是递归的；若一个过程直接地或间接地调用直接地或间接地调用自己自己,则称这个过程是递归的过程。则称这个过程是递归的过程。国际教育学院国际教育学院当多个函数构成嵌套调用时当多个函数构成嵌套调用时,遵循遵循后调用先返回后调用先返回栈栈国际教育学院国际教育学院n以下三种情况常常用到递归方法以下三种情况常常用到递归方法递归定义的数学函数递归定义的数学函数具有递归特性的数据结构具有递归特性的数据结构可递归求解的问题可递归求解的问题国际教育学院国际教育学院1.递归定义的数学函数递归定
25、义的数学函数:阶乘函数阶乘函数:2阶阶Fibonaci数列数列:国际教育学院国际教育学院树树 2.2.具有递归特性的数据结构具有递归特性的数据结构:RootRootLchildLchildRchildRchild广义表广义表 A=(a,A)A=(a,A)3.3.可递归求解的问题可递归求解的问题:迷宫问题迷宫问题HanoiHanoi塔问题塔问题 国际教育学院国际教育学院分治法：分治法：对于一个较为复杂的问题，能够分解成几对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解个相对简单的且解法相同或类似的子问题来求解1 1、能将、能将一个问题转变成一个新问题，而新问题与一个
26、问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的且这些处理对象是变化有规律的2 2、可以通过上述转化而使问题简化、可以通过上述转化而使问题简化3 3、必须有一个明确的递归出口，或称递归的边界、必须有一个明确的递归出口，或称递归的边界用分治法求解递归问题用分治法求解递归问题必备的三个条件必备的三个条件国际教育学院国际教育学院分治法求解递归问题算法的一般形式：分治法求解递归问题算法的一般形式：voidp(参数表参数表)if（递归结束条件）可直接求解步骤；（递归结束条件）可直接求解步骤；-基本项基
27、本项elsep（较小的参数）；（较小的参数）；-归纳项归纳项long Factorial(long n)if(n=0)return1;/基本项基本项 elsereturn n*Factorial(n-1);/归纳项归纳项国际教育学院国际教育学院返回返回2参数参数2计算计算2*fact(1)返回返回1参数参数1计算计算1*fact(0)返回返回1参数参数0直接定值直接定值=1参参参参数数数数传传传传递递递递递递递递归归归归调调调调用用用用结结结结果果果果返返返返回回回回回回回回归归归归求求求求值值值值if(n=0)return1;elsereturn n*Factorial(n-1);求解阶乘求
28、解阶乘 n!n!的过程的过程主程序主程序主程序主程序main:fact(4)返回返回24参数参数4计算计算4*fact(3)返回返回6参数参数3计算计算3*fact(2)国际教育学院国际教育学院设有一个递归算法如下设有一个递归算法如下:intX(intn)if(n=3)return1;elsereturnX(n-2)+X(n-4)+1则计算则计算X(X(8)时需要计算时需要计算X函数函数次次.D练习练习A.8 B.9C.16D.18国际教育学院国际教育学院规则规则:(1)(1)每次只能移动一个圆盘每次只能移动一个圆盘(2)(2)圆盘可以插在圆盘可以插在A,BA,B和和C C中的任一塔座上中的任
29、一塔座上(3)(3)任何时刻不可将较大任何时刻不可将较大圆盘压在较小圆盘之上圆盘压在较小圆盘之上Hanoi塔问题塔问题ABC国际教育学院国际教育学院Hanoi塔问题塔问题 n=1n=1，则直接从，则直接从 A A 移到移到 C C。否则。否则 (1)用用C柱做过渡，将柱做过渡，将A的的(n-1)个移到个移到B(2)将将A最后一个直接最后一个直接移到移到C(3)用用A做过渡，将做过渡，将B的的(n-1)个移到个移到C国际教育学院国际教育学院#includeintc=0;voidmove(charx,intn,charz)cout+c,n,x,znext=NULL;returnOK;链队列初始化链
30、队列初始化国际教育学院国际教育学院StatusDestroyQueue(LinkQueue&Q)while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;returnOK;销毁链队列销毁链队列国际教育学院国际教育学院StatusQueueEmpty(LinkQueueQ)return(Q.front=Q.rear);判断链队列是否为空判断链队列是否为空国际教育学院国际教育学院StatusGetHead(LinkQueueQ,QElemType&e)if(Q.front=Q.rear)returnERROR;e=Q.front-
31、next-data;returnOK;求链队列的队头元素求链队列的队头元素国际教育学院国际教育学院StatusEnQueue(LinkQueue&Q,QElemTypee)p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;链队列入队链队列入队p国际教育学院国际教育学院StatusDeQueue(LinkQueue&Q,QElemType&e)if(Q.front=Q.rear)returnERROR;p=Q.front-next;e
32、=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);returnOK;链队列出队链队列出队p国际教育学院国际教育学院#defineM100/最大队列长度最大队列长度TypedefstructQElemType*base;/初始化的动态分配存储空间初始化的动态分配存储空间intfront;/头指针头指针intrear;/尾指针尾指针SqQueue;队列的顺序表示用一维数组队列的顺序表示用一维数组baseM国际教育学院国际教育学院队列的顺序表示用一维数组队列的顺序表示用一维数组baseMQ.frontQ.front0 01
33、12 23 34 45 5Q.rearQ.rearQ.frontQ.frontQ.rearQ.rearJ J1 1J J2 2J J3 3Q.frontQ.frontQ.rearQ.rearJ J3 3Q.frontQ.frontQ.rearQ.rearJ J5 5J J6 6front=rear=0空队标志：空队标志：front=rear入队：入队：baserear+=x;出队：出队：x=basefront+;国际教育学院国际教育学院Q.frontQ.frontQ.rearQ.rearJ5J5J6J6Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rearJ5
34、J5J6J6J1J1J2J2J3J3J4J4存在的问题存在的问题设数组大小为设数组大小为Mfront=0rear=M-1时时再入队再入队真溢出真溢出front 0rear=M-1时时再入队再入队假溢出假溢出国际教育学院国际教育学院解决的方法循环队列解决的方法循环队列1 10 0Q.rearQ.rearQ.frontQ.front.base0接在接在baseM-1之后之后若若rear+1=M则令则令rear=0;实现：利用实现：利用“模模”运算运算入队：入队：baserear=x;rear=(rear+1)%M;出队：出队：x=basefront;front=(front+1)%M;国际教育学院
35、国际教育学院J4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfrontJ9J9J8J8J7J7J7,J8,J9J7,J8,J9入队入队队空：队空：front=rearfront=rear队满：队满：front=rearfront=rear解决方案：解决方案：1.1.另外另外设一个标志设一个标志以区别队空、队满以区别队空、队满2 2.少用一个元素空间少用一个元素空间：队空：队空：front=rearfront=rear 队满：队满：(rear+1)%M=front(rear+1)%M=frontJ4J4J5J5J6J60 01 12 23 34 45 5re
36、arrearfrontfront0 01 12 23 34 45 5frontfrontJ4,J5,J6J4,J5,J6出队出队rearrear国际教育学院国际教育学院循环队列循环队列#defineMAXQSIZE100/最大队列长度最大队列长度TypedefstructQElemType*base;/初始化的动态分配存储空间初始化的动态分配存储空间intfront;/头指针头指针intrear;/尾指针尾指针SqQueue;国际教育学院国际教育学院StatusInitQueue(SqQueue&Q)Q.base=(ElemType*)malloc(MAXQSIZE*sizeof(ElemTy
37、pe);if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;returnOK;循环队列初始化循环队列初始化国际教育学院国际教育学院StatusQueueEmpty(SqQueueQ)return(Q.front=Q.rear);判断循环队列是否为空判断循环队列是否为空国际教育学院国际教育学院求循环队列的长度求循环队列的长度intQueueLength(SqQueueQ)return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;国际教育学院国际教育学院StatusGetHead(SqQueueQ,QElemType&e)if(Q.fron
38、t=Q.rear)returnERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;returnOK;取循环队列的队头元素取循环队列的队头元素国际教育学院国际教育学院StatusEnQueue(SqQueue&Q,QElemTypee)if(Q.rear+1)%MAXQSIZE=Q.front)returnERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;循环队列入队循环队列入队国际教育学院国际教育学院StatusDeQueue(LinkQueue&Q,QElemType&e)if(
39、Q.front=Q.rear)returnERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;returnOK;循环队列出队循环队列出队国际教育学院国际教育学院队列应用举例队列应用举例【例【例1 1】汽车加油站】汽车加油站随着城市里汽车数量的急速增长，汽车加油站也随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入。每辆车加油都要经过三段路程，第一
40、段是在入口处排队等候进入加油车道；第二段是在加油车口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加模拟这个过程，就需要设置加油车道数加2 2个队个队列。列。国际教育学院国际教育学院【例【例2 2】模拟打印机缓冲区】模拟打印机缓冲区在主机将数据输出到打印机时，会出现主机速度与在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停打印机的打印速度不匹配的问题。这时主机就
41、要停下来等待打印机。显然，这样会降低主机的使用效下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打正确性，又提高了主机的使
42、用效率。由此可见，打印机缓冲区实际上就是一个队列结构。印机缓冲区实际上就是一个队列结构。队列应用举例队列应用举例国际教育学院国际教育学院【例【例3 3】CPUCPU分时系统分时系统在一个带有多个终端的计算机系统中，同时有多个在一个带有多个终端的计算机系统中，同时有多个用户需要使用用户需要使用CPUCPU运行各自的应用程序，它们分别通运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用过各自的终端向操作系统提出使用CPUCPU的请求，操作的请求，操作系统通常按照每个请求在时间上的先后顺序，将它系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把们排成一个队列，每次把CPUC
43、PU分配给当前队首的请求分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将运行完毕或用完规定的时间片后，操作系统再将CPUCPU分配给新的队首请求用户，这样即可以满足每个用分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使户的请求，又可以使CPUCPU正常工作。正常工作。队列应用举例队列应用举例国际教育学院国际教育学院1.掌握栈和队列的掌握栈和队列的特点特点，并能在相应的应用问，并能在相应的应用问题中正确选用题中正确选用2.熟练掌握栈的熟练掌握栈的顺序栈顺序栈和链栈的进栈出栈算法，和
44、链栈的进栈出栈算法，特别应注意特别应注意栈满和栈空栈满和栈空的条件的条件3.熟练掌握熟练掌握循环队列循环队列和链队列的进队出队算法，和链队列的进队出队算法，特别注意特别注意队满和队空队满和队空的条件的条件4.理解理解递归算法递归算法执行过程中栈的状态变化过程执行过程中栈的状态变化过程小结小结国际教育学院国际教育学院1.1.将编号为将编号为0 0和和1 1的两个栈存放于一个数组空的两个栈存放于一个数组空间间VmVm中，栈底分别处于数组的两端。当第中，栈底分别处于数组的两端。当第0 0号栈的栈顶指针号栈的栈顶指针top0top0等于等于-1-1时该栈为空，当时该栈为空，当第第1 1号栈的栈顶指针号
45、栈的栈顶指针top1top1等于等于m m时该栈为空。时该栈为空。两个栈均从两端向中间增长（如下图所示）。两个栈均从两端向中间增长（如下图所示）。b0t0t1b10m-1V练习练习国际教育学院国际教育学院数据结构定义如下数据结构定义如下typedefstructinttop2,bot2;/栈顶和栈底指针栈顶和栈底指针SElemType*V;SElemType*V;/栈数组栈数组 int m;int m;/栈最大可容纳元素个数栈最大可容纳元素个数DblStack;DblStack;试编写判断栈空、栈满、进栈和出栈四个算法试编写判断栈空、栈满、进栈和出栈四个算法的函数（函数定义方式如下）的函数（函
46、数定义方式如下）练习练习国际教育学院国际教育学院voidDblpush(DblStack&s,SElemTypex,inti)；/把把x插入到栈插入到栈i的栈的栈intDblpop(DblStack&s,inti,SElemType&x)；/退掉位于栈退掉位于栈i栈顶的元素栈顶的元素intIsEmpty(DblStacks,inti)；/判栈判栈i空否空否,空返回空返回1,否则返回否则返回0intIsFull(DblStacks)；/判栈满否判栈满否,满返回满返回1,否则返回否则返回0试编写判断栈空、栈满、进栈和出栈试编写判断栈空、栈满、进栈和出栈四个算法的函数四个算法的函数(函数定义方式如下
47、）函数定义方式如下）练习练习国际教育学院国际教育学院栈空：栈空：topi=boti itopi=boti i表示栈的编号表示栈的编号 栈满：栈满：top0+1=top1 top0+1=top1 或或top1-1=top0top1-1=top0提示提示练习练习国际教育学院国际教育学院练习练习2.2.假设以带头结点的循环链表表示队列，并假设以带头结点的循环链表表示队列，并且且只设一个指针只设一个指针指向队尾元素结点（注意不设指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队和头指针），试编写相应的队列初始化、入队和出队的算法。出队的算法。国际教育学院国际教育学院typedefstru
48、ctCiQNode/定义定义QElemTypedata;structQnode*next;CiQnode,*CiQueuePtr;提示（循环链表的特例）提示（循环链表的特例）StatusInitCiQueue(CiQueuePtr&Q)/初始化初始化Q=(CiQueuePtr)malloc(sizeof(CiQnode);if(!Q)exit(OVERFLOW);Q-next=Q;returnOK;练习练习国际教育学院国际教育学院StatusEnQueue(CiQueuePtr&Q,QElemTypee)/入队入队提示（循环链表的特例）提示（循环链表的特例）StatusDeQueue(CiQueuePtr&Q,QElemType&e)/出队出队.练习练习国际教育学院国际教育学院