第三章栈与队列

1、第第 3 章章 栈与队列栈与队列下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片本章的主要内容本章的主要内容1.栈的基本概念和栈的基本运算。栈的基本概念和栈的基本运算。2.栈在计算机中的应用。栈在计算机中的应用。3.队列的基本概念和队列的基本运算。队列的基本概念和队列的基本运算。4.队列在计算机中的应用。队列在计算机中的应用。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈3.1.1 栈的定义栈的定义栈（栈（Stack）又称又称堆栈堆栈，是一种特殊的，是一种特殊的线性表线性表，它，它限定限定对线对线性表的性表的插入和删除插入和删除操作只能在线性表的操作只能在线性表的一端进行一端进行

2、。允许允许插入和删除插入和删除的一端是的一端是变化变化的的一端，称为一端，称为栈顶（栈顶（top），），栈的栈的另一端称为另一端称为栈底栈底（bottom）。）。栈栈顶顶实际上就是实际上就是线性表线性表的的表尾表尾，栈栈底底实际上就是实际上就是线性表线性表的的表头表头，通，通常我们称表尾元素为常我们称表尾元素为栈顶元素栈顶元素。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈1.向一个栈向一个栈插入插入新元素又称为新元素又称为进栈或入栈进栈或入栈，它是把该元素放到，它是把该元素放到栈顶元栈顶元素的上面素的上面，使之成为，使之成为新的栈顶元素新的栈顶元素。2.从一个栈从一个栈删除删除

3、一个元素又称为一个元素又称为出栈或退栈出栈或退栈，它是把，它是把栈顶元素删除掉栈顶元素删除掉，使其下面的相邻元素成为使其下面的相邻元素成为新的栈顶元素新的栈顶元素。3.由于对栈的由于对栈的插入和删除插入和删除操作只能在操作只能在栈顶栈顶进行，所以栈是具有进行，所以栈是具有后进先后进先出出特性（特性（Last In First Out）的线性表，简称为）的线性表，简称为LIFO表。表。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈栈常用的基本操作栈常用的基本操作:1. InitStack（）（）初始化操作，建立一个空栈初始化操作，建立一个空栈S。2. GetTop（&S，& x ）

4、取取栈顶元素栈顶元素操作，若栈操作，若栈S不空，则不空，则用用 x 返回栈顶元素。返回栈顶元素。3. Push（&S， x ）进栈进栈操作，在操作，在S栈的栈顶压入一个元素栈的栈顶压入一个元素 x 。4. Pop（&S，& x ）出栈出栈操作，删除已存在且非空的栈操作，删除已存在且非空的栈S的的栈顶元素栈顶元素，用，用 x 返回返回栈顶元素栈顶元素。5. Empty（&S）判断一个栈判断一个栈是否为空是否为空，若，若S为空栈，返回一为空栈，返回一个个真值真值。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈3.1.2 栈的顺序存储结构及其运算栈的顺序存储结构及其运算栈栈的顺序存储结

5、构，简称的顺序存储结构，简称顺序栈顺序栈，它是利用一，它是利用一组地址连续的组地址连续的存储单元存储单元依次依次存放自存放自栈底到栈顶的数据元素栈底到栈顶的数据元素。栈栈的顺序存储结构可用的顺序存储结构可用C语言语言定义如下定义如下：#define MAXLEN 100typedef int elementtype;typedef struct/*栈的顺序存储结构定义栈的顺序存储结构定义*/ elementtype elementMAXLEN;/*存放栈元素的数组存放栈元素的数组*/ int top; /*栈指针栈指针*/SqStack;下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1

6、栈栈1.当有新元素当有新元素进栈进栈时，栈顶指针时，栈顶指针向上移动向上移动，top加加1。栈指针栈指针top实际上就实际上就是数组的下标是数组的下标 。当有元素。当有元素出栈出栈时，栈顶指针时，栈顶指针向下移动向下移动，top减减1。2.用数组用数组elementMAXLEN作为栈的存储空间，作为栈的存储空间，elementtop为为栈顶元素，当栈顶元素，当top= -1时栈为时栈为空空;当当top=0时，栈中有时，栈中有一个元素一个元素;当当top=MAXLEN-1时，表示时，表示栈满栈满。3.当当top=-1，栈为空，对空栈不能执行，栈为空，对空栈不能执行删除操作删除操作。当。当top

7、=MAXLEN-1，栈满，栈满时不能再栈满，栈满时不能再执行插入操作执行插入操作。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈1.初始化顺序栈初始化顺序栈SqStack InitStack_sq()/*建立一个空栈建立一个空栈s*/ SqStack s; s.top=-1; return(s);下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈2.取栈顶元素取栈顶元素int GetTop_sq(SqStack *s,elementtype *x) if(s-top=-1) /*栈空栈空*/ return(0);/*栈空返回栈空返回0*/ else *x=s-eleme

8、nts-top; return(1); 下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈3.进栈操作进栈操作int Push_sq(SqStack *s,elementtype x) if(s-top=MAXLEN-1) return(0); /*栈满返回栈满返回0*/ s-top+; s-elements-top=x; return(1);下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈4.出栈操作出栈操作int Pop_sq(SqStack *s,elementtype *x) if(s-top=-1) return(0); /*栈空返回栈空返回0*/ *x=s-e

9、lements-top; s-top-; return(1);下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈5.判空栈操作判空栈操作int Empty_sq(SqStack *s) return(s-top=-1);栈栈是是动态变化动态变化的的数据结构数据结构，顺序栈在，顺序栈在某种程度某种程度上可以满足这上可以满足这种种动态结构动态结构所对应所对应动态操作动态操作，但是一般数组，但是一般数组长度的定义长度的定义有一有一定定局限性局限性。主要是不能应付。主要是不能应付栈满栈满这种情况。如果不能这种情况。如果不能预估预估栈栈中中元素个数的最大值元素个数的最大值，这种用数组来存放栈中

10、数据元素的，这种用数组来存放栈中数据元素的顺顺序栈序栈，就，就不能在程序中使用不能在程序中使用。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈3.1.3 栈的链式存储结构及其运算栈的链式存储结构及其运算栈栈的链式存储结构简称为的链式存储结构简称为链栈链栈，它是一种特殊的，它是一种特殊的单链表单链表，也，也是一种动态存储结构，不用预先分配存储空间。是一种动态存储结构，不用预先分配存储空间。typedef struct node /*定义链栈结点定义链栈结点*/ int data; /*这里以整型数据为例这里以整型数据为例*/ struct node *next; /*指针类型指针类

11、型,存放下一存放下一 个结点地址个结点地址*/NODE;单链表单链表的头结点称为的头结点称为栈顶栈顶，单链表的，单链表的尾结点尾结点称为称为栈底栈底，单链，单链表的表的头指针头指针top作为作为栈顶指针栈顶指针，如下图所示。，如下图所示。注意！注意！这里的这里的单链表没有单链表没有头结点头结点，为，为统一统一对空链表和非空链表的对空链表和非空链表的操作操作，在，在单链表中应单链表中应增加头结点增加头结点。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈链栈的主要操作有进栈、出栈和读栈等。链栈的主要操作有进栈、出栈和读栈等。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈

12、1. 进栈进栈当向链栈插入一个当向链栈插入一个新元素新元素时，首先要向系统申请一个时，首先要向系统申请一个结点的结点的存储空间存储空间，将新元素的值写入新结点的，将新元素的值写入新结点的数据域中数据域中，然后修改，然后修改栈顶指针栈顶指针。NODE *pushstack(NODE *top,int x) /*进栈操作进栈操作*/ NODE *p; p=(NODE*)malloc(sizeof(NODE); p-data=x;/*将要插入的数据将要插入的数据x存储到结点存储到结点p的数据域中的数据域中*/ p-next=top; /*将将p插入链表头部插入链表头部,即链栈顶部即链栈顶部*/ to

13、p=p; return(top);下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈2. 出栈出栈出栈出栈时，先时，先取出栈顶取出栈顶元素的元素的值值，再，再修改修改栈顶指针栈顶指针，释放释放原栈顶结点。原栈顶结点。NODE *popstack(NODE *top,int *p) NODE *q; /*定义定义q结点结点*/ if(top!=NULL) /*如果栈不空如果栈不空*/ q=top; *p=top-data; /*将栈顶元素放入将栈顶元素放入*p中中*/ top=top-next; /*修改修改top指针指针*/ free(q); /*释放原栈顶空间释放原栈顶空间*/ r

14、eturn(top); /*返回栈顶指针返回栈顶指针*/下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈. 链栈的初始化（创建一个空链栈）链栈的初始化（创建一个空链栈）创建创建一个没有头结点的一个没有头结点的空链栈空链栈，就是声名一个指向栈中结点，就是声名一个指向栈中结点的的指针指针，并且令其，并且令其取空值取空值。NODE *InitLinkStack() NODE *top; top=NULL; return top;调用InitLinkStack函数的效果，完全函数的效果，完全等价于等价于在在主调函数主调函数中写中写上如下语句：上如下语句： NODE *top; top=NU

15、LL;下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈3.1.4 栈的应用举例栈的应用举例栈栈是计算机是计算机系统软件系统软件中应用最广泛的中应用最广泛的数据结构数据结构之一。之一。1. 表达式的求值表达式的求值表达式表达式求值求值是是编译系统编译系统中的一个基本问题。中的一个基本问题。所谓表达式求值所谓表达式求值，就是把我们平时，就是把我们平时书写的表达式，书写的表达式，翻译成翻译成计算机能理解的并能正确求值的一个计算机能理解的并能正确求值的一个指令序列指令序列。这里介。这里介绍一种简单直观、广为使用的算法，通常称为绍一种简单直观、广为使用的算法，通常称为“算符优先法算符优先法”

16、。要对一个表达式正确地求值，首先要要对一个表达式正确地求值，首先要了解运算规则了解运算规则。即：。即： 先乘除，后加减；先乘除，后加减； 从左算到右；从左算到右； 先括号内，后括号外先括号内，后括号外。任何一个表达式都是由任何一个表达式都是由操作数操作数(operand)、运算符运算符(operator)和和界限符界限符(delimiter)组成的。一般地，操作数可以是组成的。一般地，操作数可以是常数常数或或变量变量；运算符可以分为算数运算符、；运算符可以分为算数运算符、关关系运算符系运算符和和逻辑运算符逻辑运算符三类；界限符有左右三类；界限符有左右括号括号和表达式和表达式结束符结束符。为了叙

17、述的简洁，我们仅讨论算数表达式求值问题。在算数表达式中只有加、为了叙述的简洁，我们仅讨论算数表达式求值问题。在算数表达式中只有加、减、乘、除四种运算符。减、乘、除四种运算符。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈我们把我们把运算符运算符和和界限符界限符统称为统称为算符算符，它们构成的集合称为，它们构成的集合称为OP。根据上述。根据上述三条算数运算规则，在运算的每一步中，任意两个相继出现的算符三条算数运算规则，在运算的每一步中，任意两个相继出现的算符1和和2之间的优先关系至多是下面之间的优先关系至多是下面三种关系之一三种关系之一：1 2 1优先级高于优先级高于2 ；表表3-

18、2定义了这种运算符之间的优先级。定义了这种运算符之间的优先级。 下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈2+-*/()1+-*/(0其算法用其算法用C语言描述如下语言描述如下：int suml(int n) if(n=0)return 1; else return (n*suml(n-1);这是一个递归函数。这是一个递归函数。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈递归函数的执行过程如下递归函数的执行过程如下:1.系统首先为系统首先为递归调用递归调用建立一个建立一个工作栈工作栈，在该工作栈中，在该工作栈中存放存放参数、局参数、局部变量和调用后的返回地址部

19、变量和调用后的返回地址等信息等信息; 2.在每次在每次递归调用之前递归调用之前，把本次算法中所使用的，把本次算法中所使用的参数、局部变量的当参数、局部变量的当前值和调用后的返回地址前值和调用后的返回地址等等压入栈顶压入栈顶;3.在每次执行在每次执行递归调用结束之后递归调用结束之后，又把，又把栈顶元素弹出栈顶元素弹出，分别赋给相应，分别赋给相应的参数和局部变量，以便使它们恢复到的参数和局部变量，以便使它们恢复到调用前的状态调用前的状态，然后返回由，然后返回由返回地址返回地址所指定的位置所指定的位置;4.继续执行后续指令继续执行后续指令。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈

20、例例3.4 设设 n=4， 计算计算4!。用一个用一个栈栈来描述其来描述其递归递归的求解过程的求解过程。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈例例3.5 Hanoi塔问题塔问题假设有假设有3个分别命名为个分别命名为A、B和和C的的塔座塔座，在塔座，在塔座A上插有上插有n个直径大小各个直径大小各不相同、依小到大的编号为不相同、依小到大的编号为1，2，n的圆盘，如图的圆盘，如图3.6所示。现要求所示。现要求将将A座上的座上的n个圆盘移至个圆盘移至C座上并仍按同样顺序叠排，圆盘移动时必须遵座上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则循下列规则: 每次只能移动一个圆盘每次只

21、能移动一个圆盘; 圆盘可以插在圆盘可以插在A、B和和C中的任一塔座上中的任一塔座上; 任何时刻都不能将一个较大的圆盘压在较小圆盘之上。任何时刻都不能将一个较大的圆盘压在较小圆盘之上。 Hanoi塔问题可以这样来描述塔问题可以这样来描述：借助塔座借助塔座B，把把n个圆盘从塔座个圆盘从塔座A移到塔移到塔座座C。如何实现移动圆盘的操作呢如何实现移动圆盘的操作呢?下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈当当n=1时，问题很简单，只要将编号为时，问题很简单，只要将编号为1的圆盘从塔座的圆盘从塔座A直接移到塔座直接移到塔座C上；当上；当n=2时，也只需先将时，也只需先将1号盘从号盘从A

22、移到移到B，2号盘从号盘从A移到移到C，再将，再将1号盘从号盘从B移到移到C。当当n很大时，可以将上面的很大时，可以将上面的n-1个圆盘看成是个圆盘看成是一个整体一个整体。我们可以设想这样移到。我们可以设想这样移到圆盘：圆盘：将将n-1个圆盘借助个圆盘借助C，从，从A移到移到B；将第将第n个圆盘从个圆盘从A移到移到C；将将n-1个圆盘借助个圆盘借助A，从，从B移到移到C。注意：注意：这里的步骤这里的步骤1和和步骤步骤3是与原问题具有是与原问题具有相同特征的问题相同特征的问题，只是问题的，只是问题的规模规模变小变小，而步骤，而步骤1和步骤和步骤3又可以又可以分解为规模更小的同样性质的问题分解为规

23、模更小的同样性质的问题。庆幸的是，。庆幸的是，当当问题规模为问题规模为1时时，此问题可以简单求解此问题可以简单求解。如果我们把将。如果我们把将n个圆盘，借助个圆盘，借助B从从A移移到到C，表示为函数，表示为函数 Hanoi(n,A,B,C)；那末步骤；那末步骤1，就可以表示为函数，就可以表示为函数 Hanoi(n-1,A,C,B)；步骤；步骤3，就可以表示为函数，就可以表示为函数 Hanoi(n-1,B,C,A)；而如果；而如果步骤步骤2表示为函数表示为函数move(A,n,C) ，那末，当只有一个圆盘时，直接将其从，那末，当只有一个圆盘时，直接将其从A移到移到C，就可以表示为函数，就可以表示

24、为函数move(A,1,C) 。把上述分析综合起来，不难得到把上述分析综合起来，不难得到Hamoi塔的递归算法。塔的递归算法。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.1 栈栈void Hanoi(int n,char A,char B,char C) if(n=1)move(A,1,C);/*递归定义的基本项，它描述了递归过程的终结状态递归定义的基本项，它描述了递归过程的终结状态*/ else Hanoi(n-1,A,C,B);/*递归定义的归纳项，它描述了如何实现从当前状态递归定义的归纳项，它描述了如何实现从当前状态*/ move(A,n,C); Hanoi(n-1,B,A,C)

25、;/*到终结状态的转化到终结状态的转化*/ 下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.2 队列队列3.2.1 队列的定义队列的定义队列（队列（queue）也是一种特殊的也是一种特殊的线性表线性表，它仅允许在表的一，它仅允许在表的一端进行端进行插入插入，在表的另一端进行，在表的另一端进行删除删除。允许插入的一端称为允许插入的一端称为队尾队尾（rear），允许删除的一端称为），允许删除的一端称为队首队首（front）。）。队列这种队列这种插入在队尾插入在队尾，删除在对首删除在对首的规则，决定了队列具有的规则，决定了队列具有先进先出先进先出的特的特性，所以队列又称为性，所以队列又称为先进先

26、出表先进先出表（First In First Out，简称，简称FIFO）。）。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.2 队列队列队列的基本操作可以归纳为以下几种队列的基本操作可以归纳为以下几种:1.InitQueue（ &Q ）; 初始化一个空队列初始化一个空队列Q；2.GetFront（&Q，&y）; 取队列取队列Q的队头元素，的队头元素，y返回其值，但队列返回其值，但队列Q状态不变状态不变；3.EnQuene（&Q，x）; 若队列若队列Q还有空间，将元素还有空间，将元素x插入到插入到队尾队尾；4.DelQueue（&Q，&y）;若队列若队列Q不为空，删除队列不为空，删除队列

27、Q的的队头队头元素，元素，y返回其值；返回其值；5.Empty（&Q）; 判断队列判断队列Q是否为空，若为空返回一个真值，否则是否为空，若为空返回一个真值，否则返回一个假值。返回一个假值。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.2 队列队列3.2.2 队列的顺序存储结构及其运算队列的顺序存储结构及其运算1. 顺序队列顺序队列队列顺序存储结构称为队列顺序存储结构称为顺序队列（顺序队列（sequential queue）。顺序队列与顺。顺序队列与顺序表一样，用一个序表一样，用一个一维数组一维数组来存放数据元素。在内存中，用来存放数据元素。在内存中，用一组连续的一组连续的存储单元顺序存放

28、队列中各元素。存储单元顺序存放队列中各元素。顺序队列的顺序队列的C语言描述如下：语言描述如下：#define MAXLEN 100typedef int elementtype; /*根据需要根据需要elementtype可以是任何类型可以是任何类型*/typedef struct /*队列的顺序存储结构类型定义队列的顺序存储结构类型定义*/ elementtype elementMAXLEN; /*存放队列元素的数组存放队列元素的数组*/ int front,rear; /*队列头、尾指针队列头、尾指针*/ /*从从element0开始存放开始存放*/SeQueue; /*顺序队列类型名顺序

29、队列类型名*/ 下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.2 队列队列在在队列队列为为空空的初始状态时，的初始状态时，front=rear=-1。每当向队列中插入一个元素。每当向队列中插入一个元素，尾指针，尾指针rear向后移动一位向后移动一位，rear=rear+1。当。当rear= MAXLEN-1 时，表时，表示队示队满满;每当从队列中每当从队列中删除删除一个元素时，队首指针也一个元素时，队首指针也向后移动一位向后移动一位，front=front+1。下面给出下面给出顺序队列顺序队列中实现中实现入队入队和和出队出队运算的运算的算法描述算法描述。下一张幻灯片下一张幻灯片上一张幻灯

30、片上一张幻灯片3.2 队列队列（1） 入队入队int Enqueue_sq(SeQueue *q,elementtype x) /*用队列指针作参数用队列指针作参数*/ if(q-rear=MAXLEN-1) return(0); /*队列满返回队列满返回0*/ q-rear+; /*队尾指针先后移队尾指针先后移*/ q-elementq-rear=x; /*新元素入队新元素入队*/ return(1); /*入队成功返回入队成功返回1*/下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.2 队列队列（2） 出队出队int Delqueue_sq(SeQueue *q,elementtype

31、 *x) if(q-front=q-rear) return(0); /*队列空返回队列空返回0*/ q-front+; /*队首指针先后移队首指针先后移*/ *x=q-elementq-front; /*取出队首元素的值取出队首元素的值*/ return(1); /*出队成功返回出队成功返回1*/有关队列有关队列其它操作其它操作的算法可参看的算法可参看程序程序3-6和和程序程序3-7。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.2 队列队列2. 循环队列循环队列 对于对于顺序队列顺序队列可能会出现这样情况，尾指针指向一维数组最后，但前可能会出现这样情况，尾指针指向一维数组最后，但前面

32、有元素已经面有元素已经出队出队，这时要插入元素，仍然发生溢出，而实际上队列，这时要插入元素，仍然发生溢出，而实际上队列并未满并未满。这种溢出称为。这种溢出称为“假溢出假溢出”。为了解决这个问题，下面讨论。为了解决这个问题，下面讨论循循环队列环队列。 循环队列循环队列是将存储队列的存储区看成是一个是将存储队列的存储区看成是一个首尾相连的环首尾相连的环，即将表示，即将表示队列的数组元素队列的数组元素 element0与与elementMAXLEN-1连接起来，连接起来，形成一个形成一个环形表环形表。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.2 队列队列对循环队列的判空与判满对循环队列的判

33、空与判满在在循环队列循环队列中，容量设为中，容量设为MAXLEN，队首队首指针为指针为 front，队尾队尾指针指针为为rear。当。当rear=front时，不能判定循环时，不能判定循环 队列是队列是空队还是满队空队还是满队。对。对此作出规定，此作出规定，front=rear是循环队列是循环队列空空的标志。（的标志。（rear+1）%MAXLEN=front是循环队列满的标志。是循环队列满的标志。因此，在因此，在循环队列循环队列满满时，队列中实际上还有一个时，队列中实际上还有一个空闲单元空闲单元，以防止，以防止空队与满队的空队与满队的标志发生冲突标志发生冲突。下一张幻灯片下一张幻灯片上一张幻

34、灯片上一张幻灯片3.2 队列队列（1） 入队入队将一个新元素将一个新元素插入插入队尾队尾，首先要判断，首先要判断是否队满是否队满，若满若满，则返回队满信，则返回队满信息。若队不满，则插入新元素，返回息。若队不满，则插入新元素，返回插入成功插入成功信息。信息。int EnCqueue(CQueue *cq,elementtype x) if(cq-rear+1)%MAXLEN=cq-front) return(0); /*循环队列满返回循环队列满返回0*/ cq-rear=(cq-rear+1)%MAXLEN; /*尾指针加尾指针加1*/ cq-elementcq-rear=x; /*新元素入队

35、新元素入队*/ return(1);有关有关循环队列循环队列的其它算法，参看的其它算法，参看程序程序3-8。下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.2 队列队列（2） 出队出队出队时要判断是否出队时要判断是否队空队空，若若队空队空，则返回队空信息。若队，则返回队空信息。若队不空不空，则将，则将队队首元素首元素存入存入x中，返回中，返回出队成功出队成功信息。信息。int DelCqueue(CQueue *cq,elementtype *x) if(cq-rear=cq-front)return(0); /*循环队列空返回循环队列空返回0*/ cq-front=(cq-front+1

36、)%MAXLEN; /*队首指针后移队首指针后移*/ *x=cq-elementcq-front; /*保存队首元素保存队首元素*/ return(1);下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.2 队列队列3.2.3 队列的链式存储结构及其运算队列的链式存储结构及其运算队列队列的的链式存储结构链式存储结构称为称为链队列链队列（linked queue）。在链队列中，有一。在链队列中，有一个头指个头指针针front和一个和一个尾指针尾指针rear。另外，为链队列附加。另外，为链队列附加一个头结点一个头结点。队列头指针指向。队列头指针指向头结点，队尾指向队列的尾结点。当头结点，队尾指向

37、队列的尾结点。当头尾指针都指向队头结点时头尾指针都指向队头结点时（front=rear）队列为空队列为空。入队在队尾，出队在队头。入队在队尾，出队在队头。链队列链队列的的结点结构结点结构用用C语言描述如下：语言描述如下：typedef struct node/*定义链队列结点定义链队列结点*/ int data;/*以整型数据为例以整型数据为例*/ struct node *next; /*存放下一个结点地址存放下一个结点地址*/NODE; /*链队列结点类型链队列结点类型*/下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.2 队列队列（1）入队）入队将将新结点新结点插入到插入到队尾队尾，

38、并，并修改修改队尾指针队尾指针。void Enterqueue(NODE *rear,int x) /*入队操作入队操作*/ NODE *p; p=(NODE*)malloc(sizeof(NODE); /*创建新结点创建新结点*/ p-data=x;/*将要插入的数据将要插入的数据x存储到结点存储到结点p的数据域中的数据域中*/ p-next=NULL; rear-next=p; /*将将p所指结点插入链队列尾部所指结点插入链队列尾部*/ rear=p; /*修改尾指针修改尾指针*/下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.2 队列队列（2） 出队Void Delqueue(NOD

39、E *front,NODE *rear,int *x) /*出队操作出队操作*/ NODE *p; if(front!=rear) /*判断链队列空判断链队列空,若链队列不空若链队列不空*/ p=front-next;/*p指向链队列第一个元素指向链队列第一个元素*/ front-next=p-next;/*第一个结点出队第一个结点出队*/ if(p-next=NULL)/*表示原链队列中只有一个元素表示原链队列中只有一个元素*/ rear=front; /*出队后出队后,队空队空,修改修改rear指针指针*/ *x=p-data;/*保存出队后的元素值保存出队后的元素值*/ free(p);下一张幻灯片下一张幻灯片上一张幻灯片上一张幻灯片3.2 队列队列3.2.4 队列的应用队列的应用例例3.6 打印数据缓冲区问题打印数据缓冲区问题在打印机打印的时候，主机输出数据的速度比打印机打印的速度要快得多。在打印机打印的时候，主机输出数据的速度比打印机打印的速度要快得多。由于速度不匹配，大大影响了主机的工作效率。为了解决这个问题，通常由于速度不匹配，大大影响了主机的工作效率。为了解决