教学课件第三章栈和队列.ppt

第三章 栈和队列n n学习要点n n理解栈和队列的基本概念和各种存储结构；理解栈和队列的基本概念和各种存储结构；n n掌握栈和队列的各种运算方法掌握栈和队列的各种运算方法n n了解堆栈在递归运算中的应用了解堆栈在递归运算中的应用3.1 栈 栈的概念栈的概念 使用数组创建使用数组创建栈栈　　使用链表创建使用链表创建栈栈3.1.1 栈的概念栈的示意图出栈入栈栈顶ana2a1栈底n定义：定义：栈栈(Stack)是限制在一端进行插入是限制在一端进行插入和删除运算的线性表通常称插和删除运算的线性表通常称插入、删除的这一端为入、删除的这一端为栈顶栈顶(Top)，，另一端为另一端为栈底栈底(Bottom)当表中当表中没有元素时称为没有元素时称为空栈空栈a1, a2, ... , an ））插入删除栈的特点栈的特点后进先出后进先出(LIFO)(LIFO)栈的示意图出栈入栈TOPana2a1n栈顶：栈顶：对栈进行操作的一端对栈进行操作的一端n栈顶指针：栈顶指针：指示栈顶位置的指针指示栈顶位置的指针n栈的长度：栈的长度：栈中元素的个数栈中元素的个数n假设栈假设栈S=(a1，，a2，，a3，，…,an)，则，则a1称为称为栈底元素栈底元素，，an为为栈顶栈顶元素元素。

插入的过程称为入栈，删插入的过程称为入栈，删除的过程称为出栈栈中元素的除的过程称为出栈栈中元素的出栈入栈是按照后进先出的原则出栈入栈是按照后进先出的原则进行的因此，栈称为后进先出进行的因此，栈称为后进先出表（表（LIFO）r rs sr rt ts sr rs sr rr r(a) 调用调用a函数函数, r进栈　进栈　(c) 调用调用c函数函数,t进栈　进栈　(e) 返回返回a函数函数,s退栈退栈(b) 调用调用b函数函数,s进栈进栈　　(d) 返回返回b函数函数,t退栈退栈　　(f) 返回主程序返回主程序,r退栈退栈 n栈在函数嵌套调用中的应用：栈在函数嵌套调用中的应用：n n栈的基本操作栈的基本操作InitStackInitStack( (s) s)构造一个空栈构造一个空栈S SClearStack(s)ClearStack(s) 将栈将栈S S清为空栈清为空栈EmptyStack(s)EmptyStack(s)若栈若栈S S为空栈，返回为空栈，返回TRUETRUE，否则，否则FALSEFALSELenStack(s)LenStack(s)返回栈返回栈S S中元素的个数，即栈的长度中元素的个数，即栈的长度GetTop(s)GetTop(s)取出取出S S的栈顶元素的值的栈顶元素的值Push(s,x)Push(s,x)插入元素插入元素x x为新的栈顶元素为新的栈顶元素Pop(s,x)Pop(s,x)删除删除S S的栈顶元素，并返回其值的栈顶元素，并返回其值如何存储栈?进栈、出栈等操作如何实现？3.1.2 栈的顺序存储结构 n顺序栈顺序栈：：是利用一块地址连续的存储单元来存放栈中的元是利用一块地址连续的存储单元来存放栈中的元素，同时要利用一个指示器素，同时要利用一个指示器top top 来指示栈顶元素的位置。

来指示栈顶元素的位置 typedef struct{Elemtype sk[Maxsize]；int top; }seqstack;seqstack *s;s->sk[s->top]//当前栈顶元素栈的几种状态示意图栈的几种状态示意图 top1234空栈 有5个元素的栈　 栈顶元素出栈 元素进栈 toptoptop12345123423栈顶指针top,指向实际栈顶位置，初值为-1top=-1,栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（overflow)当栈用顺序结构存储时，栈的基本操作如建空栈、进栈、出栈等操作如何实现？顺序栈的图示topMAX-1n-1n-210a an na an-1n-1a a2 2a a1 11 ) 进栈操作进栈操作 进栈函数分为两个步骤：进栈函数分为两个步骤：n 将栈顶的指针加将栈顶的指针加1n 将要存放的数据存放在指针所指向的数组中将要存放的数据存放在指针所指向的数组中x 进栈前 x 进栈后topMAX-1n-1n-210a an na an-1n-1a a2 2a a1 1topMAX-1n-1n-210a an na an-1n-1a a2 2a a1 1x1 ) 进栈操作进栈操作 int Push(seqstack *s,Elemtype x){if (s->top==Maxsize-1){ printf("out of space!\n"); return (0); }s->top++;s->sk[s->top]=x;return(1);} 2）出栈操作）出栈操作出栈操作也分为两个步骤：出栈操作也分为两个步骤：n 取出目前栈指针所指数组元素的内容。

取出目前栈指针所指数组元素的内容n 将栈指针的内容减将栈指针的内容减1，即指向下一个栈元素即指向下一个栈元素出栈操作前出栈操作后topMAX-1n-1n-210a an na an-1n-1a a2 2a a1 1topMAX-1n-1n-210a an na an-1n-1a a2 2a a1 12）出栈操作）出栈操作int Pop(seqstack *s,Elemtype *e){ if (s->top==-1){ printf("no element!\n"); return(0);}*e=s->sk[s->top];s->top--;return(1);}3）其它几种操作）其它几种操作seqstack *InitStack( )//创建空栈创建空栈 {seqstack *s;s=(seqstack* ) malloc(sizeof(seqstack));if( !s) { printf(“未完成空未完成空间间分配分配!\n"); return(null); }s->top=-1;return(s); }int EmptyStack(seqstack *s) //栈的判空操作栈的判空操作 { if（（ s->top==-1）） s->top==Maxsize-1return(1);elsereturn(0);}Elemtype GetTop(seqstack *s) //取栈顶元素取栈顶元素 {if (EmptyStack(s))return(0);elsereturn(s->sk[s->top]);}注意：n n对对对对于于于于顺顺顺顺序序序序栈栈栈栈，，，，入入入入栈栈栈栈时时时时，，，，首首首首先先先先判判判判栈栈栈栈是是是是否否否否满满满满了了了了，，，，栈栈栈栈满满满满的的的的条条条条件件件件为为为为：：：：s->top==MAXSIZE-1s->top==MAXSIZE-1，，，，栈栈栈栈满满满满时时时时，，，，不不不不能能能能入入入入栈栈栈栈；；；； 否则出现空间溢出。

否则出现空间溢出否则出现空间溢出否则出现空间溢出n n出出出出栈栈栈栈和和和和读读读读栈栈栈栈顶顶顶顶元元元元素素素素操操操操作作作作，，，，先先先先判判判判栈栈栈栈是是是是否否否否为为为为空空空空，，，，为为为为空空空空时时时时不能操作不能操作不能操作不能操作n n合合合合理理理理初初初初始始始始化化化化栈栈栈栈的的的的方方方方法法法法：：：：先先先先为为为为栈栈栈栈分分分分配配配配一一一一个个个个基基基基本本本本容容容容量量量量，，，，然后在应用过程中，当栈的空间不够时再逐步扩大然后在应用过程中，当栈的空间不够时再逐步扩大然后在应用过程中，当栈的空间不够时再逐步扩大然后在应用过程中，当栈的空间不够时再逐步扩大栈的链式存储结构，也称链栈，如图所示：栈的链式存储结构，也称链栈，如图所示：data nextS栈顶栈底an-1ana13.1.2 栈的链式存储结构 typedef struct node{Elemtype data;struct node *next;}stacknode,*LinkStack;链栈的存储结构链栈的存储结构链栈的存储结构链栈的存储结构: :top1 ) 进栈算法进栈算法int PushLinkStack (LinkStack S,Elemtype x){ LinkStack p;p=(LinkStack)malloc(sizeof(StackNode));if (!p){ printf("分配不成功分配不成功\n"); return(0); }p->data=x;p->next=S->next;S->next=p;return(p);}Sana1Px2 ) 出栈算法出栈算法int PopLinkStack(LinkStack S,Elemtype *e){ LinkStack p;if (S->next==null){printf(" Not Exist\n");return(0);}p=S->next;S->next=S->next->next;e=p->data;free(p);return(1);}San-1ana1p1m栈1底栈1顶栈2底栈2顶3.1.3 共享栈　　常采用将两个栈底设在可用空间的两端。

　　 仅当两个栈顶相遇时，才产生上溢，即所有可用空间已用完对每个栈可用的最大空间就可能大于整个可用空间的一半m/2　　有时，一个程序设计中，需要使用多个同一类型的栈，这时候可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，实现多个栈存储空间的动态分配小结小结　　1 栈是限定仅能在栈是限定仅能在栈顶栈顶一端进行插入、删除操一端进行插入、删除操 　作的线性表；　作的线性表；　　2 栈的元素具有栈的元素具有后进先出后进先出的特点；的特点；　　3 栈顶元素的位置由一个称为栈顶指针的变量栈顶元素的位置由一个称为栈顶指针的变量 　指示，进栈、出栈操作要修改栈顶指针；　指示，进栈、出栈操作要修改栈顶指针；3.2 3.2 栈的应用举例栈的应用举例r主主程程序序srrrs子子过过程程1rst子子过过程程2rst子子过过程程3结果：结果： 2 5 0 4 2 5 0 4例1 数制转换n n十进制十进制十进制十进制N N和其它进制数的转换是计算机实现计算的基和其它进制数的转换是计算机实现计算的基和其它进制数的转换是计算机实现计算的基和其它进制数的转换是计算机实现计算的基本问题本问题本问题本问题, , 其中一个简单算法基于下列原理其中一个简单算法基于下列原理其中一个简单算法基于下列原理其中一个简单算法基于下列原理: :n nN = (N div N = (N div d d) )1010   d d+N mod +N mod d dn n例如例如例如例如: (1348): (1348)1010 = 2 = 2   8 83 3+5+5   8 82 2+0+0   8+4 = (2504)8+4 = (2504)8 8 N N 　　　　N div 8N div 8　　　　 N mod 8 N mod 81348 1348 　　　　168 168 4 4 　　　　168168 　　　　 21 210 02121 2 2　　　　　　　　　　　　5 52 02 0　　　　2 2计算时从低位到高位顺序计算时从低位到高位顺序产生八进制数的各个数位产生八进制数的各个数位显示时按从高位到显示时按从高位到低位的顺序输出低位的顺序输出void Transform(){S=InitStack();scanf("%d",&n);while(n){Push(S,n%8);n=n/8;}while(!EmptyStack(S)){Pop(S,p);printf("%d",*p);}}利用栈利用栈“先进后出先进后出”的性质，的性质，把先产生的数位压入栈中，把先产生的数位压入栈中，然后再从栈顶依次弹出即可然后再从栈顶依次弹出即可3.3 3.3 栈与递归栈与递归什么是递归什么是递归什么是递归什么是递归一一一一个个个个对对对对象象象象（（（（事事事事物物物物））））的的的的组组组组成成成成包包包包含含含含了了了了自自自自身身身身或或或或者者者者说说说说对对对对于于于于一一一一个个个个对象的描述又用到了该对象本身的现象称为对象的描述又用到了该对象本身的现象称为对象的描述又用到了该对象本身的现象称为对象的描述又用到了该对象本身的现象称为递归递归递归递归 。

递递递递归归归归是是是是程程程程序序序序设设设设计计计计中中中中一一一一个个个个很很很很有有有有用用用用的的的的工工工工具具具具，，，，许许许许多多多多数数数数学学学学函函函函数数数数的定义和程序设计等许多领域中都用到了递归的定义和程序设计等许多领域中都用到了递归的定义和程序设计等许多领域中都用到了递归的定义和程序设计等许多领域中都用到了递归A( ){　…　A( ) ;　…}A 直接调用自己直接调用自己B间接调用自己间接调用自己B( ) { C( ) {　… 　　　　… 　C( );　 B( );　… 　… } } 递归算法的编写递归算法的编写递归算法的编写递归算法的编写1 1）将问题用递归的方式描述（定义））将问题用递归的方式描述（定义））将问题用递归的方式描述（定义））将问题用递归的方式描述（定义）2 2）根据问题的递归描述（定义）编写递归算法）根据问题的递归描述（定义）编写递归算法）根据问题的递归描述（定义）编写递归算法）根据问题的递归描述（定义）编写递归算法问题的递归描述（定义）问题的递归描述（定义）问题的递归描述（定义）问题的递归描述（定义） 递归定义包括两项递归定义包括两项递归定义包括两项递归定义包括两项 基本项（终止项）：描述递归终止时问题的求解；基本项（终止项）：描述递归终止时问题的求解；基本项（终止项）：描述递归终止时问题的求解；基本项（终止项）：描述递归终止时问题的求解； 递递递递归归归归项项项项：：：：将将将将问问问问题题题题分分分分解解解解为为为为与与与与原原原原问问问问题题题题性性性性质质质质相相相相同同同同，，，，但但但但规规规规模模模模较较较较小小小小的的的的问题；问题；问题；问题；例例 阶乘函数阶乘函数　　　　n!= 1* 2* 3* 4 * (n-1)* n n!= 1* 2* 3* 4 * (n-1)* n 　　　　n!n!递归定义递归定义递归定义递归定义　　　　n!= 1 n!= 1 当当当当 n=1 n=1 时时时时　　　　　　　　　　　　　　　　　　　　　　　　　　　　n!= n (n-1)! n!= n (n-1)! 当当当当n> 1 n> 1 时时时时用用(n-1)!(n-1)!定义定义n!n!计算计算计算计算5 5 5 5的阶乘（的阶乘（的阶乘（的阶乘（5 5 5 5！！！！=5X4X3X2X1=5X4X3X2X1=5X4X3X2X1=5X4X3X2X1））））int f(int n) int f(int n) int f(int n) int f(int n) { { { { if ( n = = 1) return (1); if ( n = = 1) return (1); if ( n = = 1) return (1); if ( n = = 1) return (1); else return ( n * f(n-1)); else return ( n * f(n-1)); else return ( n * f(n-1)); else return ( n * f(n-1)); } } } }f(1)f(2)f(3)f(4)f(5)top1 f(1)=1 2*f(1) f(2)=2*f(1)3*f(2) f(3)=3*f(2)4*f(3) f(4)=4*f(3)5*f(4) f(5)=5*f(4)例1 阶乘函数void print(int w){ int i; if ( w!=0) { print(w-1); for(i=1;i<=w;++i) printf(“%3d,”,w); printf(“/n”); }}运行结果：1，2，2，3，3，3，例2 递归的执行情况分析 递归调用执行情况如下：递归调用执行情况如下：主程序主程序(1)print(w) w=3; 3print(2);（（1））w=3 top(2) 输出：输出：3, 3, 3w2print(1);（（2））w=2 （（1））w=3 top(3) 输出：输出：2, 2w1print(0);（（3））w=1 （（2））w=2 （（1））w=3 top(4)输出：输出：1w0（（4））w=0 （（3））w=1 （（2））w=2 （（1））w=3 topw(3) 输出：输出：2, 2(2) 2(1) 3top(4)输出：输出：1(3) 1(2) 2(1) 3top(2) 输出：输出：3, 3, 3 (1 ) 3top返回返回(3) 1(2) 2(1) 3top(4) 0结束结束(1) { print(w-1); for(i=1;i<=w;++i) printf(“%3d,”,w); printf(“/n”); }3.4 队列 队列的概念队列的概念 循环队列循环队列——队列的顺序存储和实现队列的顺序存储和实现3.4.3 队列的链式存储和实现队列的链式存储和实现3.4.1 队列的概念n n什么是队列什么是队列什么是队列什么是队列? ?n n队列队列队列队列是限定仅能在一端进行删除，是限定仅能在一端进行删除，是限定仅能在一端进行删除，是限定仅能在一端进行删除，另一端进行插入的线性表。

另一端进行插入的线性表另一端进行插入的线性表另一端进行插入的线性表 a a0 0 a a1 1 a a2 2 a a3 3 a a4 4入队队头队尾出队 队列的示意图队列的示意图允许删除的一端称为允许删除的一端称为队队头头，允许插入的一端称，允许插入的一端称为为队尾队尾队列的长度队列的长度：队列中元：队列中元素的个数素的个数队列的特点队列的特点先进先出先进先出(FIFO)(FIFO)n n队列的基本操作队列的基本操作InitInitQueue(Queue(Q)Q)将将Q Q置为一个空队列置为一个空队列QueueQueueEmpty(Q)Empty(Q)若若Q Q为空队列返回为空队列返回TRUETRUE，否则，否则FALSEFALSEQueueQueueLen(Q)Len(Q)返回队列返回队列Q Q中元素个数，即队的长度中元素个数，即队的长度GetHead(Q)GetHead(Q)返回返回Q Q的队头元素的队头元素EnQueueEnQueue(Q,e)(Q,e)插入元素插入元素e e为队为队Q Q的新队尾元素的新队尾元素DeDeQueueQueue(Q,e)(Q,e)删除删除Q Q的队头元素，并用的队头元素，并用e e返回其值返回其值3.4.2 队列的顺序存储和循环队列 n用一个数组来实现队列的顺序存储用一个数组来实现队列的顺序存储n队头指针队头指针front指向队头元素实际位置的指向队头元素实际位置的前一个前一个位置位置n队尾指针队尾指针rear指向队尾元素在队列中的实际位置指向队尾元素在队列中的实际位置队列顺序结构的队列顺序结构的队列顺序结构的队列顺序结构的C C C C语言描述：语言描述：语言描述：语言描述：typedef struct{typedef struct{Elemtype elem[maxsize];Elemtype elem[maxsize];int front;int front;int rear;int rear;}SqQueue;}SqQueue;SqQueue *Q;SqQueue *Q;n n实现：用一维数组实现实现：用一维数组实现elemelem[M][M]front=-1rear=-1123450队空123450frontJ1,J2,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1空队列条件：front==rear入队列： elem[++rear]=x;出队列：x= elem[++front];rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront2456（a) 假溢出(b)真溢出rearfront32rearfront154261n n存在问题存在问题设数组维数为设数组维数为MM，，则：则：n n当当front=-1,rear=M-1front=-1,rear=M-1时，再有元素入队发生溢出时，再有元素入队发生溢出————真溢出真溢出n n当当frontfront -1,rear=M-1-1,rear=M-1时，再有元素入队发生溢出时，再有元素入队发生溢出————假溢出假溢出n n当当rearrear指向数组的最后一个分量的时候，队列再也无法插入新元素，而这指向数组的最后一个分量的时候，队列再也无法插入新元素，而这时常常还有大量的内存空间被闲置。

时常常还有大量的内存空间被闲置n n解决方案解决方案n n队首固定，每次出队剩余元素向下移动队首固定，每次出队剩余元素向下移动————浪费时间浪费时间n n循环队列循环队列n n基本思想：把队列设想成环形，让基本思想：把队列设想成环形，让elemelem[0][0]接在接在elemelem[M-1][M-1]之后，若之后，若rear+1==M,rear+1==M,则令则令rear=0;rear=0;n n实现：利用实现：利用“ “模模” ”运算运算n n入队：入队： rear=(rear+1)%M; elem[rear]=x; rear=(rear+1)%M; elem[rear]=x;n n出队：出队： front=(front+1)%M; x= elem[front]; front=(front+1)%M; x= elem[front];n n队满、队空判定条件队满、队空判定条件0M-11frontrear…...…...n n队满、队空判定条件队满、队空判定条件frontrear(c)队空(b)队满frontrearfrontrear(a)一般情况J6J7J8J9J4J54 03 152J6J7J4J54 03 1524 03 152队空：front==rear队满：front==rear解决方案：解决方案：解决方案：解决方案：1. 1.另外另外另外另外设一个标志设一个标志设一个标志设一个标志以区别队空、队满以区别队空、队满以区别队空、队满以区别队空、队满2 2. .少用一个元素空间少用一个元素空间少用一个元素空间少用一个元素空间，约定队头指示的位置不存放元素：，约定队头指示的位置不存放元素：，约定队头指示的位置不存放元素：，约定队头指示的位置不存放元素： 队空：队空：队空：队空：front==rearfront==rear 队满：队满：队满：队满：(rear+1)%M==front(rear+1)%M==frontfrontJ6J7J8J4J54 03 152rearn n循环队列的基本操作算法frontrear（（1 1）） 队头指针队头指针 front = (front+ 1)% M front = (front+ 1)% M；； 等价于：等价于： if if（（ front +1 = M front +1 = M ）） front = 0; front = 0; else else front = front +1; front = front +1;（（2 2）队尾指针）队尾指针rear = (rear +1)% M rear = (rear +1)% M ；；等价于：等价于： if if （（ rear +1 = M rear +1 = M ）） rear = 0; rear = 0; else else rear = rear + 1; rear = rear + 1;循环队列在指针移动处理时与一般队列不同：循环队列在指针移动处理时与一般队列不同：循环队列在指针移动处理时与一般队列不同：循环队列在指针移动处理时与一般队列不同：J6J4J54 03 1521）初始化队列）初始化队列 功能：功能：对循环队列对循环队列Q进行初始化，即　　　进行初始化，即　　　将将Q置为一个空队列；置为一个空队列；算法：算法：建一个空队列Qfrontrear4 03 152int InitQueue(SqQueue *Q){Q->font=0;Q->rear=0;return OK;}2）入队操作）入队操作 功能：功能：将元素将元素 x 插入队尾插入队尾 元素元素 x x 入队前入队前元素元素 x x 入队后入队后frontrearJ1J2J34 03 152frontrearJ1J2J3 x4 03 152Q->rear=(Q->rear+1)%Maxsize;Q->elem[Q->rear]=e;入队算法：入队算法：int EnQueue(SqQueue *Q,ElemType e){if ((Q->rear+1)%Maxsize==Q->front) return ERROR;Q->rear=(Q->rear+1)%Maxsize;Q->elem[Q->rear]=e;return OK;}2）出队操作）出队操作 功能：功能：删除队头元素删除队头元素出队操作前出队操作前出队操作后出队操作后frontrearJ1J2J34 03 152frontJ1J2J34 03 152rearQ->front=(Q->front+1)%Maxsize; *e=Q->elem[Q->front];int DeQueue(SqQueue *Q,ElemType *e){if (Q->front==Q->rear) return ERROR;Q->front=(Q->front+1)%Maxsize; *e=Q->elem[Q->front];return OK;}出队算法：出队算法：打印队列算法打印队列算法：（数组打印）：（数组打印）void print1(SqQueue *Q){for (i=0;ielem[i]);}printf("\n");printf(“Q->front=",Q->front);printf(“Q->rear=",Q->rear);}打印队列算法打印队列算法：（循环队列打印）：（循环队列打印）void print2(SqQueue *Q){i=(Q->front+1) % Maxsize;while (i!=Q->rear){printf("%d", Q->elem[i]);i=i+1;i=i % maxsize;}printf(“Q->rear=",Q->rear);}空链队列空链队列链队列图示链队列图示n n链队列Q.frontQ.reara1 1a2 2Q.frontQ.rear3.4.3 链队列--队列的链式表示与实现n n链队列存储结构的C语言描述:typedef struct QsNode{elemtype data;struct QsNode *next;}Qsnode;typedef struct { Qsnode * front; Qsnode * rear;}LinkQueue;1）队列初始化运算）队列初始化运算int InitQueue (LinkQueue *Q){Q->front=(Qsnode *)malloc(sizeof(Qsnode));if(!Q->front) return 0;Q->rear = Q->front;Q->front->next = NULL;return 1;}Q.frontQ.rear2）队列入队运算）队列入队运算将结点加入到队列将结点加入到队列将结点加入到队列将结点加入到队列的尾端的尾端的尾端的尾端int InQuene(LinkQueue *Q,elemtype e){ Qsnode *p;p=(Qsnode *p)malloc (sizeof(Qsnode));if(p= =NULL) return 0;p->data = e;Q->rear->next = p;Q->rear = p; Q->rear->next = NULL;return 1;}pea1 1Q.frontQ.rear3）队列出队运算）队列出队运算将队头元素删除将队头元素删除将队头元素删除将队头元素删除int DeQuene (LinkQueue *Q){ Qsnode *P;if(Q->front = =Q->rear) return 0; p=Q->front->next; Q->front->next = p->next;if(Q->rear= =p) Q->rear=Q->front;free(p);return 1;}a1 1a2 2Q.frontQ.rearp当只有一个元素时，当只有一个元素时，要修改尾指针要修改尾指针void print(LinkQueue *q){LinkQueue *p;p=q->front->next;while (p!=NULL){printf("%4d",p->data);p=p->next;}}4）队列打印运算）队列打印运算1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；3）离散事件的模拟----模拟实际应用中的各种排队现象；4）用于处理程序中具有先进先出特征的过程； 在操作系统课程中会讲到n n队列的应用返回目录返回目录 小结小结　　1 队列是限定仅能在表尾一端进行插入，表队列是限定仅能在表尾一端进行插入，表 头一端删除操作的线性表；头一端删除操作的线性表；　　2 队列中的元素具有先进先出的特点；队列中的元素具有先进先出的特点；　　3 队头、队尾元素的位置分别由称为队头指队头、队尾元素的位置分别由称为队头指 针和队尾指针的变量指示；针和队尾指针的变量指示； 4 入队操作要修改队尾指针，出队操作要修入队操作要修改队尾指针，出队操作要修 改队头指针；改队头指针；  习题习题1 1、设将整数、设将整数1 1、、2 2、、3 3、、4 4依次进栈，但只要出栈时栈非空，依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问则可将出栈操作按任何次序夹入其中，请回答下有问题：题：（（1 1）若入栈次序为）若入栈次序为push(1)push(1)，，pop()pop()，，push(2)push(2)，，push(3)push(3)，，pop()pop()，，pop( )pop( )，，push(4)push(4)，，pop( )pop( )，则出栈的数字，则出栈的数字序列为什么？序列为什么？（（2 2）能否得到出栈序列）能否得到出栈序列423423和和432432？并说明为什么不能得？并说明为什么不能得到或如何得到。

到或如何得到3 3）请分析）请分析1 1、、2 2、、3 3、、4 4的的2424种排列中，哪些序列可以通种排列中，哪些序列可以通过相应的入出栈得到过相应的入出栈得到3 3、循环队列的优点是什么？如何判断它的空和满？、循环队列的优点是什么？如何判断它的空和满？4 4、设长度为、设长度为n n的链队列用单循环链表表示，若只设头指的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？针，则怎样进行入队和出队操作；若只设尾指针呢？7 7、用第二种方法，即少用一个元素空间的方法来区别循、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作满、出队、入队及取队头元素等六个基本操作9 9、指出下列程序段的功能是什么？、指出下列程序段的功能是什么？ (1) void demo1(seqstack *s){(1) void demo1(seqstack *s){ int I;arr[64];n=0; int I;arr[64];n=0; while (!stackempty(s)) arr[n++]=pos(s); while (!stackempty(s)) arr[n++]=pos(s); for(I=0;