第3章 栈和队列

1、13.1 栈（栈（stack） 基本概念、抽象数据类型、顺序表示和实基本概念、抽象数据类型、顺序表示和实现、链式表示和实现现、链式表示和实现3.2 队列（队列（queue） 基本概念、抽象数据类型、顺序队列、顺基本概念、抽象数据类型、顺序队列、顺序循环队列、链式队列序循环队列、链式队列3.3 栈和队列的应用实例栈和队列的应用实例 数制转换，栈和递归，约瑟夫环数制转换，栈和递归，约瑟夫环第三章第三章 限定性线性表限定性线性表-栈和队列栈和队列23.1 栈（栈（stack） 3.1.1 栈的基本概念栈的基本概念 3.1.2 栈的存储结构栈的存储结构 3.1.3 栈的基本运算栈的基本运算31.定义定

2、义与线性表相同，仍为一对一与线性表相同，仍为一对一( 1:1)关系关系。用用或或存储均可，但以顺序栈更常存储均可，但以顺序栈更常见。见。只能在只能在运算，且访问结点时依照运算，且访问结点时依照（lifo）或）或（filo）的原则。）的原则。关键是编写关键是编写和和函数，具体实现依顺函数，具体实现依顺序栈或链栈的存储结构有别而不同。序栈或链栈的存储结构有别而不同。3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式 2. 逻辑结构逻辑结构限定只能在表的限定只能在表的进行插入和删除操作进行插入和删除操作的线性表。特点：后进先出。的线性表。特点：后进先出。基本操作有基本操作有：建栈、判

3、断栈满或栈空、入栈、出栈、建栈、判断栈满或栈空、入栈、出栈、取栈顶元素值等。取栈顶元素值等。4在栈满时还进行入栈运算，必定会在栈满时还进行入栈运算，必定会产生空间的溢出。这是一种出错状产生空间的溢出。这是一种出错状态，应设法避免之。态，应设法避免之。7. 栈栈“下溢下溢”6. 栈栈“上溢上溢”当栈空时仍进行出栈运算，必定会产当栈空时仍进行出栈运算，必定会产生空间的溢出。下溢可能是正常现象，生空间的溢出。下溢可能是正常现象，因为栈在程序中使用时，其初态或终因为栈在程序中使用时，其初态或终态都是空栈，所以下溢可用来作为程态都是空栈，所以下溢可用来作为程序控制转移的条件。序控制转移的条件。5 是仅在

4、是仅在表尾表尾进行插入、删除操作的线性表。进行插入、删除操作的线性表。表尾表尾(即即 an 端端)称为称为栈顶栈顶 /top ; 表头表头(即即 a1 端端)称为称为栈底栈底/base/bottom例如：例如： 栈栈 = (a1 , a2 , a3 , .,an-1 , an )插入元素到栈顶的插入元素到栈顶的操作，称为操作，称为入栈入栈。从栈顶删除最后一从栈顶删除最后一个元素的操作，称个元素的操作，称为为出栈出栈。a an n称为栈顶元素称为栈顶元素a a1 1称为栈底元素称为栈底元素插入和删除都只能在表插入和删除都只能在表的一端（栈顶）进行！的一端（栈顶）进行！注：栈可以完成比较复杂的数据

5、元素特定注：栈可以完成比较复杂的数据元素特定序列的转换任务。序列的转换任务。6例例1 1：栈是什么？它与一般线性表有什么不同？：栈是什么？它与一般线性表有什么不同？ 栈是一种特殊的线性表，栈是一种特殊的线性表，它只能在表的一端（即栈它只能在表的一端（即栈顶）顶）进行插入和删除运算。进行插入和删除运算。栈与一般线性表的区别：仅在于栈与一般线性表的区别：仅在于不同。不同。逻辑结构：逻辑结构： 1:1 逻辑结构：逻辑结构： 1:1 存储结构：顺序存储结构：顺序表表、链、链表表 存储结构：顺序存储结构：顺序栈栈、链、链栈栈运算规则：运算规则： 运算规则：运算规则：(lifo)7例例2 2：一个栈的输入

6、序列为一个栈的输入序列为a,b,c，若在，若在入栈的过程中入栈的过程中允许出栈允许出栈，则可能得到的出栈序列是什么？，则可能得到的出栈序列是什么？解：可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解： a a入入a a出，出， b b入入b b出，出，c c入入c c出，出， 即即abcabc； a a入入a a出，出， b b、c c入，入，c c、b b出，出， 即即acbacb； a a、b b入，入，b b出，出， c c入入c c出，出，a a出，即出，即bcabca； a a、b b入，入，b b、a a出，出，c c入入c c出，出， 即即bacbac； a a、b b

7、、c c入，入，c c、b b、a a出，出， 即即cbacba； 合计有合计有5 5种可能性。种可能性。8二、栈抽象数据类型二、栈抽象数据类型数据集合：数据集合： a a0 0, a, a1 1, , , a , an-1 n-1 a ai i的数据类型为的数据类型为 datatypedatatype操作集合操作集合：(1)initstack (s) (1)initstack (s) 初始化栈初始化栈s s为空栈为空栈 (2)stackempty(s) (2)stackempty(s) 判断栈判断栈s s空否空否 (3)push(s,x) (3)push(s,x) 入栈入栈 (4)pop(s

8、,d) (4)pop(s,d) 出栈出栈 (5)gettop(s) (5)gettop(s) 取栈顶数据元素取栈顶数据元素 等等实现栈的基本运算取决于栈的存储结构，存储结构不实现栈的基本运算取决于栈的存储结构，存储结构不同，算法描述也不同。同，算法描述也不同。9栈在计算机中主要有两种基本的存储结构：栈在计算机中主要有两种基本的存储结构： 顺序顺序存储结构和存储结构和链式链式存储结构。存储结构。 1.顺序顺序栈栈 2.链链栈栈 10三、栈的顺序表示和实现三、栈的顺序表示和实现1、顺序栈顺序栈 顺序存储结构的栈。顺序存储结构的栈。2、顺序栈的存储结构、顺序栈的存储结构 它是利用一组地址连续的存储它

9、是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元单元依次存放自栈底到栈顶的数据元素，同时设指针素，同时设指针top指示栈顶元素的指示栈顶元素的当前位置。用当前位置。用c语言定义为：语言定义为：#define maxsize 100typedef struct datatype stackmaxsize; int top;seqstack; a0 a1 an-1顺序栈顺序栈s ai an栈底栈底栈顶栈顶注意：这里采用栈注意：这里采用栈顶指针指向栈顶元顶指针指向栈顶元素的方法，还有的素的方法，还有的书上将栈顶指针指书上将栈顶指针指向待压入栈的位置向待压入栈的位置11ana1a0栈底栈底 栈

10、顶栈顶 进栈进栈 出栈出栈 栈的示意图栈的示意图 12 a0 a1 an-1顺序栈顺序栈s ai问：顺序表和顺序栈的操作有何区别？问：顺序表和顺序栈的操作有何区别？表头表头表尾表尾低地址低地址高地址高地址写入：写入：si= ai读出：读出： e= si压入压入(pushs s +toptop=a=an n弹出弹出( pope=se=stoptop- 低地址低地址高地址高地址si a0 a1 ai an-1 顺序表顺序表s an以线性表以线性表 s= (a0 , a1 , . , an-2 , an-1)为例为例栈底栈底base栈顶栈顶top前提：一定要前提：一定要预设预设栈顶指针栈顶指针top

11、top栈顶栈顶top13栈为空栈为空 的条件的条件 ： base=top=-1;栈满的条件栈满的条件 ： top-base=maxsize-1; a0 a1 an-1顺序栈顺序栈s ai低地址低地址高地址高地址 an栈底栈底栈顶栈顶入栈入栈口诀：栈指针口诀：栈指针top “先加先加后压后压” : ss+toptop=a=an n出栈出栈口诀：栈指针口诀：栈指针top “先弹先弹后减后减” : e=se=stoptop- - - 注意：再次强调这里的操作时针注意：再次强调这里的操作时针对采用对采用栈顶指针指向栈顶元素的栈顶指针指向栈顶元素的方法方法14问：为什么要设计栈？它有什么独特用途？问：为

12、什么要设计栈？它有什么独特用途？1.调用函数或子程序调用函数或子程序(程序调用时现场程序调用时现场的保护及返回的保护及返回)；2.递归运算的有力工具；递归运算的有力工具；3.用于保护现场和恢复现场；用于保护现场和恢复现场；4.简化了程序设计的问题简化了程序设计的问题。下面用下面用3个例子来帮助理解栈：个例子来帮助理解栈：15void test(int *sum)int x;cinx;if(x=0)sum=0;else;*sum+=x;cout*sum;断点地址断点地址入栈入栈例例1 1、阅读下列递归过程，说明其功能。阅读下列递归过程，说明其功能。输入输入x10输入输入x50输入输入x2输入输入

13、x3输入输入x4输出输出*sum0输出输出*sum0+x4输出输出*sumx4+x3输出输出*sum x4+x3 +x2输出输出*sum x4+x3 +x2+x1注意：最先注意：最先输入的数据输入的数据 x x1 1 最后才被最后才被累加累加程序功能：对键盘输入数程序功能：对键盘输入数据求和，直到输入据求和，直到输入0 0结束结束断点：程序停止执行，转断点：程序停止执行，转向执行其它函数体返回的向执行其它函数体返回的程序地址信息程序地址信息16例例2 2、一个栈的输入序列是一个栈的输入序列是12345，若在，若在入栈的入栈的过程中允许出栈过程中允许出栈，则栈的输出序列则栈的输出序列43512可

14、能实可能实现吗现吗？12345的输出呢？的输出呢？答：答：4351243512不可能实现，主要是其中的不可能实现，主要是其中的1212顺序不能实顺序不能实现；现；1234512345的输出可以实现，每压入一数便立即弹出的输出可以实现，每压入一数便立即弹出即可。即可。 思考：有无通用的判别原则？思考：有无通用的判别原则？17例例3、设依次进入一个栈的元素序列为设依次进入一个栈的元素序列为3，1，2，4，则可得到出栈的元素序列是：则可得到出栈的元素序列是： ）1，2，3，4 ）3，4，1，2 ）2，3，4，1 ）1，3，4，2a）、）、d）可以，）可以， b）、）、c）不行。）不行。答：答：即对于

15、输入序列即对于输入序列1，2，3，不存在输出序列，不存在输出序列3，1，2讨论：有无通用的判别原则？讨论：有无通用的判别原则？有！若借助栈由输入序列有！若借助栈由输入序列1,2,n得到的输出序列为得到的输出序列为p1,p2,pjpkpipn(p1,p2,pn为输入序列为输入序列12n的一个排列的一个排列)(pjpktop = -1; /*将顺序栈置为空栈*/19(2)(2)判栈顺序栈是否为空判栈顺序栈是否为空 int stackempty(seqstack *s)/*判顺序栈s非空否，空则返回1，否则返回0*/ if(s-top = -1) return 1; else return 0; 2

16、0(3)(3)判栈满判栈满int stackfull(seqstack *s)/*若栈满则返回1，否则返回0 */ if(s-top = maxsize-1) return 1;else return 0; 21(4)(4)入栈入栈int stackpush(seqstack *s, datatype x)/*把数据元素值x压入顺序栈s，入栈成功则返回1，否则返回0 */ if (stackfull(s)printf(栈已满无法插入! n); return 0; else +s-top; s-stacks-top = x; return 1; 22(5)(5)出栈出栈int stackpop(

17、seqstack *s, datatype *d)/*弹出顺序栈s的栈顶数据元素值到参数d ，出栈成功则返回1，否则返回0*/ if (stackempty(s)printf(栈已空无数据元素出栈! n);return 0;else *d = s-stacks-top; s-top-; return 1; 23(6)(6)取栈顶数据元素取栈顶数据元素datatype gettop(seqstack *s)/*取顺序栈s的当前栈顶数据元素值返回*/ if(stackempty(s)printf(栈已空! n);return 0; else return s-stacks-top;24例：用栈存放

18、（例：用栈存放（a a，b b，c c，d d） aacbabatop 顺序栈顺序栈入栈入栈函数的核心语句：函数的核心语句： s-top +; s-stacks-top = x;toptoptoptop低地址低地址l高地址高地址mbcd25例：从栈中取出例：从栈中取出 dcbatoptopdcabdcbatopdcbatop低地址低地址l高地址高地址m顺序栈出栈函数的核心语句：顺序栈出栈函数的核心语句：*d = s-stacks-top;s-top -;注：注：datatype *d； seqstack *s；26当一个程序中同时使用两个顺序栈时，为了防止上溢错误，需要为每个栈当一个程序中同时

19、使用两个顺序栈时，为了防止上溢错误，需要为每个栈 分配一个较大的空间，但是在某一个栈发生上溢的同时，可能其余栈未用分配一个较大的空间，但是在某一个栈发生上溢的同时，可能其余栈未用 的空间很多，如果将这多个栈安排在同一个向量里，即让多个栈共享存储的空间很多，如果将这多个栈安排在同一个向量里，即让多个栈共享存储 空间，就可以互相调节余缺，这样既可节约了存储空间，又降低了上溢空间，就可以互相调节余缺，这样既可节约了存储空间，又降低了上溢 发生的概率。发生的概率。 a0a1a2a3a4栈栈1栈栈2栈栈1栈栈2考虑有两个栈共有一个数组空间的情况考虑有两个栈共有一个数组空间的情况 27栈栈1栈栈20下标：

20、下标：maxsize-1s1.tops2.top(1)判断两个栈栈空的条件：判断两个栈栈空的条件：s1.top=-1; s2.top=maxsize; (2)判断两个栈栈满的条件：判断两个栈栈满的条件：s1.top+1=s2.top；或；或 s1.top=s2.top-1； (3)进栈操作：进栈操作： 栈栈s1进栈方向进栈方向 栈栈s2进栈方向进栈方向对对s1栈：栈： s1.stack+s1.top=x;对对s2栈：栈： s2.stack-s2.top=x;28(4)出栈：出栈： 对对s1栈：栈： x=s1.stacks1.top-; 对对s2栈：栈： x=s2.stacks2.top+; (

21、5)取栈取栈s1的栈顶元素并保存到的栈顶元素并保存到x中的中的gettop算算 法：法： void gettop(seqstack s1,datatype *x) if (s1.top=-1) cout“该该s1栈为空栈，无法取出元素！栈为空栈，无法取出元素！”；return ; *x=s1.stacks1.top; 采用顺序栈存储方式的优点是，采用顺序栈存储方式的优点是，可使可使多个栈共享空间多个栈共享空间；当栈中元素个数变化较大，当栈中元素个数变化较大，且存在多个栈的情况下，且存在多个栈的情况下，顺序栈是栈的首选存储方式。顺序栈是栈的首选存储方式。29四、栈的链式表示和实现四、栈的链式表示

22、和实现1、 链栈的存储结构链栈的存储结构 以头指针为栈顶，以头指针为栈顶，在头指针处在头指针处插入或删除插入或删除.栈顶栈顶栈底栈底栈也可以用链式结构来表示，用链式结构来表示的栈就是栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈链栈top a a0 0 a a1 1a an-2n-2a an-1n-1nextdata链栈中每个结点由两个域构成：链栈中每个结点由两个域构成：data域和域和next域，其定义为：域，其定义为：typedef struct stacknode datatype data; struct stacknode * next; linkstack;302 2、链式

23、堆栈的操作实现、链式堆栈的操作实现(1) 初始化链栈void initstack(linkstack *s) s=null;栈顶指针栈顶指针s312 2、链式堆栈的操作实现、链式堆栈的操作实现(2) 入栈linkstack stackpush(linkstack *s, datatype x) stacknode *p;if(p = (linkstack *)malloc(sizeof(linkstack) = null) cout内存空间不足无法插入! “data = x;p-next = s; /*新结点链入栈顶*/s = p; /*新结点成为新的栈顶*/return s;32(3)(3)

24、出栈出栈datatype stackpop(linkstack *s) datatype x; linkstack *p; /保存栈顶指针if (p = null) cout堆栈已空出错！“data; /*原栈顶结点元素赋予d*/ s = p-next;/*删除原栈顶结点*/ free(p); /*释放原栈顶结点内存空间*/ return x; 注： 由此可以看出：一个链栈由其由此可以看出：一个链栈由其栈顶指针栈顶指针s s唯一指定唯一指定 33一般一般不会出现栈满不会出现栈满情况；除非没有空间导致情况；除非没有空间导致malloc分配分配失败。失败。链栈的入栈、出栈操作就是栈顶的插入与删除操

25、作，链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成修改指针即可完成。几点说明几点说明:34例：从键盘输入一批正整数，按照相反的次序打印例：从键盘输入一批正整数，按照相反的次序打印 出来。出来。 分析：此输入和输出正好对应栈的后进先出。分析：此输入和输出正好对应栈的后进先出。 算法思想：首先对栈进行初始化，然后依次读入字算法思想：首先对栈进行初始化，然后依次读入字符（以符（以-1作为结束）并压入栈中，最后依次弹出栈作为结束）并压入栈中，最后依次弹出栈中的元素。中的元素。 35只能在表的一端进行插入操作，而在表的另一只能在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。端

26、进行删除操作的线性表。队尾插队尾插入入队头删队头删除除与线性表相同，仍为一对一关系与线性表相同，仍为一对一关系。顺序队列顺序队列或或链队列链队列，以，以循环顺序队列循环顺序队列更常见。更常见。只能在队首和队尾运算，且访问结点时依照只能在队首和队尾运算，且访问结点时依照先进先出先进先出（fifo）的原则。的原则。关键是掌握关键是掌握入队入队和和出队出队操作，具体实现依队操作，具体实现依队列的存储结构的不同而不同。列的存储结构的不同而不同。基本操作基本操作：入队或出队，建空队列，判队空或队满等操作。入队或出队，建空队列，判队空或队满等操作。36队列队列 （queue）是仅在是仅在表尾表尾进行插入操

27、作，在进行插入操作，在表头表头进进行删除操作的线性表。它是一种先进先出行删除操作的线性表。它是一种先进先出（fifo）的线性表。的线性表。例如：队列例如：队列 q= (a1 , a2 , a3 , .,an-1 , an )在队尾插入元素称为在队尾插入元素称为；在队首删除元素称为；在队首删除元素称为。当队列中没有数据元素时称为空队列。此时队列当队列中没有数据元素时称为空队列。此时队列的长度为的长度为0.队首队首队尾队尾37关键是掌握关键是掌握入队入队和和出队出队操作。操作。具体实现依具体实现依存储结构存储结构（链队列链队列或或顺序队列顺序队列）的不同而不同。）的不同而不同。1. 离散事件的模拟

28、离散事件的模拟（模拟事件发生的先后顺序（模拟事件发生的先后顺序, ,例如例如 到银行办理存取款业务到银行办理存取款业务）；2. 打印机和键盘的输出缓冲打印机和键盘的输出缓冲（因为信息必须串（因为信息必须串行执行）行执行）；3. 简化程序设计。简化程序设计。答：答：问：为什么要设计队列？它有什么独特用途？问：为什么要设计队列？它有什么独特用途？38二、队列抽象数据类型二、队列抽象数据类型数据集合：数据集合：aa0 0,a,a1 1, ,a,ai i , ,a,an-1n-1 a ai i的数据类型为的数据类型为 datatypedatatype操作集合操作集合：(1)queueinitiate(

29、q) (1)queueinitiate(q) 初始化队列初始化队列q q (2)queueempty(q) (2)queueempty(q) 队列队列q q空否空否 (3)enqueue(q,x) (3)enqueue(q,x) 入队列入队列 (4)dequeue(q,d) (4)dequeue(q,d) 出队列出队列 (5)queueget(q,d) (5)queueget(q,d) 取队头数据元素取队头数据元素 等等39三、顺序队列三、顺序队列1、顺序队列顺序队列采用顺序存储结构的队列。采用顺序存储结构的队列。2 2、顺序队列的存储结构、顺序队列的存储结构它利用一个一维数组来它利用一个一维

30、数组来存储数据元素，另再设立一存储数据元素，另再设立一个队头指示器和一个队尾指个队头指示器和一个队尾指示器分别指向当前队头元素示器分别指向当前队头元素和当前队尾元素。用和当前队尾元素。用c c语言语言定义为：定义为： typedef struct node datatype datamaxsize; int head; int rear; sequeue; a4 a3 a2data a1 headrear(队尾队尾)(队头队头)403 3、顺序队列的、顺序队列的“假溢出假溢出”问题问题(1)(1)假溢出假溢出顺序队列因多次入队和出队操作后出现有存储空间但不能顺序队列因多次入队和出队操作后出现有

31、存储空间但不能进行入队操作的溢出。进行入队操作的溢出。原因原因：队头队尾指针移动方向不断增大。：队头队尾指针移动方向不断增大。(2)(2)如何解决顺序队列的假溢出问题？如何解决顺序队列的假溢出问题？可采取二种方法：可采取二种方法：1)1)采用循环队列采用循环队列； 2)2)采用计数器记录顺序队列中有多少元素；采用计数器记录顺序队列中有多少元素； 3 3）采用每出队列一个元素，将队列整体往前移一个）采用每出队列一个元素，将队列整体往前移一个位置；位置； 4 4）采用统计出队列的个数，然后队列整体往前移统）采用统计出队列的个数，然后队列整体往前移统计的个数个位置；计的个数个位置；41四、顺序循环队

32、列的表示和实现四、顺序循环队列的表示和实现、顺序循环队列的基本原理、顺序循环队列的基本原理 把顺序队列所使用的存储空间构造成一个逻辑上把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当首尾相连的循环队列。当rear和和head达到达到maxsize-1后，再前进一个位置就自动到。后，再前进一个位置就自动到。a3a2a1headrear 0 1 2 3 . .n-11a3a2a103n-12rearhead相当于取模运算相当于取模运算422、顺序循环队列的队空和队满判断问题、顺序循环队列的队空和队满判断问题新问题：新问题：在循环队列中，空队特征是在循环队列中，空队特征是head=r

33、ear；队满时也会有队满时也会有head=rear；如何解决呢？如何解决呢？解决方案有三：解决方案有三：使用一个使用一个计数器计数器记录队列中元素个数（即队列长度）；记录队列中元素个数（即队列长度）；判队满：判队满：count0 & rear=head 判队空：判队空：count=0加加设标志位设标志位，出队出队时置时置, ,入队入队时置时置, ,则可识别当前则可识别当前head=rear属于何种情况属于何种情况判队满：判队满：tag=1 & rear=head 判队空：判队空：tag=0 & rear=head 少用一个存储单元空间少用一个存储单元空间进行区分进行区分

34、判队满：判队满：head=(rear+1)%maxsize 判队空：判队空： rear=head43例：例： 一循环队列如下图所示，若先删除一循环队列如下图所示，若先删除4个元素，接着再个元素，接着再插入插入4个元素，请问队头和队尾指针分别指向哪个位置个元素，请问队头和队尾指针分别指向哪个位置? j2 j3j1 j4 j5head=1rear=0解：解：由图可知，队头和队尾指针的初态分别为由图可知，队头和队尾指针的初态分别为head=1和和rear=0。删除删除4个元素后个元素后head=5；再插入再插入4个元素后，个元素后，rear=(0+4)%6=4 head=5j6 j5j7j8 j9r

35、ear=4rear=0head=544、顺序循环队列的实现、顺序循环队列的实现采用对顺序循环队列的分析，其结构体定义为采用对顺序循环队列的分析，其结构体定义为：typedef struct nodedatatype datamaxqueuesize;int rear; /*队尾指针*/int head;/*队头指针*/ sequeue; 45讨论：循环队列的基本操作如何实现？讨论：循环队列的基本操作如何实现？以建队、入队和出队三种基本操作为例以建队、入队和出队三种基本操作为例1）初始化一个顺序循环队列）初始化一个顺序循环队列算法要求：生成一空队列算法要求：生成一空队列算法操作：算法操作： 设置

36、队列为设置队列为空队列空队列，其特征即：，其特征即： head=rear=046具体算法：具体算法：void initiatecirqueue (seqqueue *q)/*初始化顺序循环队列初始化顺序循环队列q*/ q-rear = maxsize-1; /*定义初始队尾指针下标值定义初始队尾指针下标值*/ q-head = maxsize-1; /*定义初始队头指针下标值定义初始队头指针下标值*/47算法说明：向循环队列的算法说明：向循环队列的队尾插入队尾插入一个元素一个元素分分 析析：(1) 插入前应当先判断队列是否满？插入前应当先判断队列是否满？ if (sq-head=(sq-rea

37、r+1)%maxsize) coutrear = (sq-rear + 1) % maxsize; sq-datasq-rear = x; return 1;2） 入队操作入队操作48int en_cirqueue (sequeue *sq, datatype x)if (sq-head=(sq-rear+1)%maxsize)cout队列已满无法插入队列已满无法插入! “rear = (sq-rear + 1) % maxsize; sq-datasq-rear = x; return 1;入队操作完整算法入队操作完整算法493）出队操作）出队操作算法说明：删除队头元素，返回其值算法说明：删

38、除队头元素，返回其值 e 分析：分析： （1） 在删除前应当判断队列是否空？在删除前应当判断队列是否空？ if (sq-head=sq-rear) return 0; （2）删除动作删除动作 sq-head = (sq-head + 1) % maxsize; m = sq-datasq-head; headhead指针在先加，然后元素出队指针在先加，然后元素出队50int cirqueuedelete(sequeue *sq, datatype *d)if (sq-head=sq-rear ) cout“队列已空无数据元素出队列队列已空无数据元素出队列! head = (sq-head +

39、1) % maxsize; *d = sq-datasq-head; return 1; 出队操作完整算法出队操作完整算法51五、链式队列五、链式队列1 1、链式队列、链式队列采用链式存储结构的队列。采用链式存储结构的队列。2 2、链式队列的存储结构、链式队列的存储结构 链式队列的队头指针指在队列的当前队头结点链式队列的队头指针指在队列的当前队头结点位置，队尾指针指在队列的当前队尾结点位置。位置，队尾指针指在队列的当前队尾结点位置。下图是一个不带头结点的链式队列的结构：下图是一个不带头结点的链式队列的结构：rearrearheadheadaa1/an-1aa1/an-152链式队列中结点的结构

40、体定义为：链式队列中结点的结构体定义为： typedef structtypedef struct nodenode datatype data; datatype data; struct struct node node * *next;next; linkqueue; linkqueue; 为了方便参数调用，通常把链式队列的队头指针为了方便参数调用，通常把链式队列的队头指针headhead和队尾指针和队尾指针rearrear也定义为结构体类型，如下：也定义为结构体类型，如下：typedef structtypedef struct linkqueue linkqueue * *head;

41、head; linkqueue linkqueue * *rear;rear; linkqueuehead; linkqueuehead;53、链式队列操作的实现、链式队列操作的实现(1)初始化队列初始化队列 void initqueue(linkqueuehead *q) q-head=q-rear=null;nullnullq 54算法说明：向链队列的算法说明：向链队列的队尾队尾插入一个元素插入一个元素分分 析析：(1)申请一个链结点申请一个链结点p=(linkqueue *)malloc(sizeof(linkqueue)；p-data = x;p-next = null;(2)插入动作插入动作 if(q-rear != null) q-rear-next = p; q-rear = p; if(q-head = null) q-head = p;入链队列的入链队列的完整算法如下：完整算法如下：(2)入链队列入链队列 55int enlinkqueue (linkqueueh