数据结构 第三章栈和队列.ppt

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

1、第三章第三章栈和队列栈和队列n教学目的教学目的n通过本章的学习，要求掌握栈和队列的定义，通过本章的学习，要求掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的算法设熟练掌握顺序和链接存储的栈和队列的算法设计及其程序实现，了解栈和队的各种应用。计及其程序实现，了解栈和队的各种应用。n本章主要介绍以下内容：本章主要介绍以下内容：l栈的概念、存储结构及其基本操作栈的概念、存储结构及其基本操作l队列的概念、存储结构及其基本操作队列的概念、存储结构及其基本操作l栈与队列的应用举例栈与队列的应用举例n重点：栈和队列的定义、特征；顺序栈、链栈重点：栈和队列的定义、特征；顺序栈、链栈的描述及基本操作实现算

2、法；循环队列和链队的描述及基本操作实现算法；循环队列和链队列的基本操作实现算法。列的基本操作实现算法。n难点：栈满、栈空的条件及描述方法；队满和难点：栈满、栈空的条件及描述方法；队满和队空的描述方法；循环队列上的插入、删除操队空的描述方法；循环队列上的插入、删除操作。作。栈（stack）n栈的定义n栈的类型定义n栈的存储方式栈的定义n栈是一种特殊的线性表。其特殊性在于限定插栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在入和删除数据元素的操作只能在线性表的一端线性表的一端进行。进行。a1ana2栈的示意图栈顶栈底进栈出栈进行插入和删除的进行插入和删除的一端是浮动端，被一端是

3、浮动端，被称为栈顶称为栈顶固定端一端被固定端一端被称为栈底称为栈底假设栈假设栈S=(a1，a2，a3，an)，则，则a1称为栈底称为栈底元素，元素，an为栈顶元素。栈中元素按为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈的次序进栈，退栈的第一个元素应为栈顶元素。顶元素。换句话说，栈的修改是按后进先出的原则进行换句话说，栈的修改是按后进先出的原则进行的。的。因此，栈称为后进先出表（因此，栈称为后进先出表（LIFO）LastInFirstOut。栈的类型定义ADTStack 数据对象数据对象：D=ai|ai ElemSeti=1,2,.,nn0数据关系数据关系：R1

4、=|ai,ai+1 ElemSet,i=1,2,.,n-10约定约定an端为栈顶，端为栈顶，a1端为栈底端为栈底基本操作基本操作：结构初始化结构初始化InitStack(&S)操作结果：构造一个空栈操作结果：构造一个空栈S销毁结构销毁结构DetroyStack(&S)初始条件：栈初始条件：栈S已经存在已经存在操作结果：销毁栈操作结果：销毁栈S引用型操作引用型操作StackEmpty(S)/判断判断S是否为空栈，若为空返回是否为空栈，若为空返回True，否则返回，否则返回FalseStackLength(S)/得到栈得到栈S的元素个数，即栈的长度的元素个数，即栈的长度GetTop(S，&e)/得

5、到得到S的栈顶元素，并将之放入变量的栈顶元素，并将之放入变量e中中StackTraverse(S,visit()/从栈底到栈顶遍历栈从栈底到栈顶遍历栈S，对每个元素调用，对每个元素调用visit()加工型操作加工型操作ClearStack(&S)/清空栈清空栈SPush(&S,e)/向栈中插入元素向栈中插入元素e为新的栈顶元素为新的栈顶元素Pop(&S,&e)/删除栈删除栈S的栈顶元素，并用的栈顶元素，并用e返回值返回值栈的存储方法栈的存储方法n栈有两种存储表示方法栈有两种存储表示方法:顺序存储和链式存储顺序存储和链式存储 由于栈是运算受限的线性表，因此线性表由于栈是运算受限的线性表，因此线性

6、表的存储结构对栈也适应。的存储结构对栈也适应。栈的顺序存储结构简称为栈的顺序存储结构简称为顺序栈顺序栈，它是运，它是运算受限的线性表。因此，可用数组来实现顺序算受限的线性表。因此，可用数组来实现顺序栈。栈。通常由一个一维数组和一个记录栈顶元素通常由一个一维数组和一个记录栈顶元素位置的变量组成。位置的变量组成。当当栈栈中中没没有有数数据据元元素素时时，表表示示为为栈栈空空。栈栈顶顶元元素素所所对对应应的的下下标标值值top=-1。在刚才基础上执行在刚才基础上执行Push(S,A)后得到这种状态后得到这种状态又又有有三三个个元元素素B、C、D先先后后入入栈栈，此此时时栈栈顶顶元元素素的的下下标标值

7、值top=3。栈已满。栈已满。在刚才状态下，执行两次在刚才状态下，执行两次Pop(S,x)运算后得到运算后得到Top-1D01230123Top-A0123Top-ABC0123Top-AB顺序存储结构n n顺序栈的顺序栈的顺序栈的顺序栈的C#C#语言描述如下：语言描述如下：语言描述如下：语言描述如下：publicclassSeqStackpublicclassSeqStackprivateintmaxSize;/privateintmaxSize;/顺序栈的容量顺序栈的容量顺序栈的容量顺序栈的容量privatechardata;/privatechardata;/数组，用于存储顺序栈的数据元

8、素，这里存数组，用于存储顺序栈的数据元素，这里存数组，用于存储顺序栈的数据元素，这里存数组，用于存储顺序栈的数据元素，这里存储的只有字符型储的只有字符型储的只有字符型储的只有字符型privateinttop;/privateinttop;/指示顺序栈的栈顶指示顺序栈的栈顶指示顺序栈的栈顶指示顺序栈的栈顶 n nmaxSizemaxSize 为栈中元素的最大容量。为栈中元素的最大容量。为栈中元素的最大容量。为栈中元素的最大容量。n ndatadata域域域域:为一个一维数组，用于存储栈中元素。为一个一维数组，用于存储栈中元素。为一个一维数组，用于存储栈中元素。为一个一维数组，用于存储栈中元素。n

9、 ntoptop域域域域:栈顶指针。取值范围为栈顶指针。取值范围为栈顶指针。取值范围为栈顶指针。取值范围为0 0MaxSize-1MaxSize-1。n ntop=-1top=-1表示栈空，表示栈空，表示栈空，表示栈空，top=MaxSize-1top=MaxSize-1表示栈满。表示栈满。表示栈满。表示栈满。类的实现类的实现publicclassSeqStackprivateintmaxSize;/顺序栈的容量顺序栈的容量privatechardata;/数组，用于存储顺序栈的数据元素，这数组，用于存储顺序栈的数据元素，这里存储的只有字符型里存储的只有字符型privateinttop;/指示

10、顺序栈的栈顶指示顺序栈的栈顶publicintMaxSize/最大容量属性最大容量属性getreturnmaxSize;setmaxSize=value;publicintTop/栈顶属性栈顶属性getreturntop;使用使用SeqListSeqList s=new s=new SeqListSeqList()()生成一个生成一个SeqListSeqList类的对象实例类的对象实例n栈底元素为栈底元素为n栈顶指针为栈顶指针为n进栈时需将进栈时需将s.tops.top加加1 1，退栈时需将，退栈时需将s.tops.top 减减1 1ns.tops.top00表示空栈，表示空栈，s.tops.

11、top=MaxSize-1=MaxSize-1表示栈表示栈满满s.data0s.top基本操作1.初始化栈初始化栈S/构造函数构造函数publicSeqStack(intsize)data=newcharsize;maxSize=size;top=-1;2.求栈的长度求栈的长度publicintGetLength()returntop+1;3.清空顺序栈清空顺序栈publicvoidClear()top=-1;4、判栈空、判栈空publicboolIsEmpty()if(top=-1)returntrue;elsereturnfalse;5、入栈、入栈publicvoidPush(charit

12、em)if(top=maxSize-1)/若栈已满，则不能再做入栈操作若栈已满，则不能再做入栈操作Console.WriteLine(TheStackisfull!);return;top+;datatop=item;6、出栈出栈publiccharPop()if(IsEmpty()/若栈为空栈，无法做出栈操作若栈为空栈，无法做出栈操作Console.WriteLine(TheStackisempty!);return;charitem=datatop;top-;returnitem;7、取栈顶元素、取栈顶元素publiccharGetTop()if(IsEmpty()Console.Writ

13、eLine(TheStackisemptye!);return;returndatatop;链式存储结构链式存储结构n栈的链式存储结构称为栈的链式存储结构称为链栈链栈，它是运算是受限的单链，它是运算是受限的单链表，可插入和删除操作仅限制在表头位置上进行表，可插入和删除操作仅限制在表头位置上进行.链栈的类型说明如下：链栈的类型说明如下：publicclasspublicclassStackNodeStackNodeprivateintdata;/privateintdata;/数据域数据域数据域数据域privateprivateStackNodeStackNodenext;/next;/指针域指

14、针域指针域指针域 链栈的几种状态链栈的几种状态栈的应用举例栈的应用举例n由于栈结构具有的后进先出的固有特性，致使由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。栈成为程序设计中常用的工具。n数值转换数值转换n括号匹配检验括号匹配检验数值转换数值转换n十进制数值转换成二进制 使用展转相除法将一个十进制数值转换成二进使用展转相除法将一个十进制数值转换成二进制数值。制数值。即用该十进制数值除以即用该十进制数值除以2，并保留其余数；重，并保留其余数；重复此操作，直到该十进制数值为复此操作，直到该十进制数值为0为止。为止。最后将所有的余数反向输出就是所对应的二进最后将所有的余数反向输

15、出就是所对应的二进制数值。制数值。5822920214170231212101十进制十进制58的二进制表示为：的二进制表示为：111010publicvoidDToB(intdecVal)SeqStacks=newSeqStack(50);while(decVal!=0)s.Push(decVal%2);decVal/=2;while(!s.IsEmpty()Console.Write(s.Pop().ToString();Console.WriteLine();Console.ReadLine();检验表达式中的括号匹配情况n 假设在一个算术表达式中，可以包含三种括号：圆括假设在一个算术表达

16、式中，可以包含三种括号：圆括号号“（”和和“）”，方括号，方括号“”和和“”和花括号和花括号“”和和“”，并且这三种括号可以按任意的次序嵌套，并且这三种括号可以按任意的次序嵌套使用。比如，使用。比如，.(.).。现。现在需要设计一个算法，用来检验在输入的算术表达式在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。中所使用括号的合法性。n算术表达式中各种括号的使用规则为：算术表达式中各种括号的使用规则为：出现左括号，出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况嵌套，但不能出现交叉情况。n检验括号

17、是否匹配的方法可以用检验括号是否匹配的方法可以用“期待的急迫程度期待的急迫程度”这个这个概念来描述。概念来描述。n()(),()()是正确的格式，而是正确的格式，而(),()是错是错误的格式误的格式()12345678()()()检验出错的情况n（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；于左括号；n（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；了括号交叉情况；n（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左）算术

18、表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。括号多于右括号。我们可以利用一个栈结构保存每个出现的左括号，当遇我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。不匹配的结论。算法基本思想算法基本思想n凡出现左括号，进栈凡出现左括号，进栈n凡出现右括号，首先检查栈是否是空凡出现右括号，首先检查栈是否是空若栈空，表明右括号多了若栈空，表明右括号多了否则和栈顶元素比较，否则和栈顶

19、元素比较，若相等，则左括号出栈若相等，则左括号出栈否则不匹配否则不匹配n表达式检查结束时，表达式检查结束时，若栈空，则匹配正确若栈空，则匹配正确否则表明左括号多了否则表明左括号多了迷宫求解.算法思想算法思想n若当前位置若当前位置“可通可通”，则纳入，则纳入“路径路径”，继续，继续前进前进n若当前位置若当前位置“不可通不可通”，则后退，换向探索，则后退，换向探索n若四周皆若四周皆“不可通不可通”，则从路径中删除，则从路径中删除汉诺塔问题：汉诺塔问题：n有三根柱子分别叫有三根柱子分别叫A柱、柱、B柱、柱、C柱。现假设有柱。现假设有N个圆盘（都是按从大到小依次放入柱中的）个圆盘（都是按从大到小依次放

20、入柱中的）已经放在了已经放在了A柱上，我们的任务就是把这柱上，我们的任务就是把这N个个圆盘移动到圆盘移动到C柱。但移动的过程，必须遵守大柱。但移动的过程，必须遵守大盘永远在小盘的下面这一个原则。盘永远在小盘的下面这一个原则。栈与递归栈与递归n n递归是一种非常重要的数学概念和解决问题的递归是一种非常重要的数学概念和解决问题的方法，在计算机科学和数学等领域有着广泛的方法，在计算机科学和数学等领域有着广泛的应用。在计算机科学中，许多数据结构，如广应用。在计算机科学中，许多数据结构，如广义表、树和二叉树等，由于其自身固有的递归义表、树和二叉树等，由于其自身固有的递归性质，都可通过递归方式加以定义并实

21、现许多性质，都可通过递归方式加以定义并实现许多问题的算法设计。问题的算法设计。n n在计算机内部，在计算机内部，通过栈来实现递归算法通过栈来实现递归算法。所以。所以递归是栈的一个实际应用。递归是栈的一个实际应用。当在一个函数的运行期间当在一个函数的运行期间调用另一个函数调用另一个函数时，时，在运行该被调用函数在运行该被调用函数之前之前，需要完成三件，需要完成三件事：事：n将所有的实在参数、返回地址等将所有的实在参数、返回地址等信息信息传递给被传递给被调用函数保存调用函数保存n为被调用函数的局部变量为被调用函数的局部变量分配存储存储区分配存储存储区n将将控制转移控制转移到被调用函数的入口到被调用

22、函数的入口从被调用函数返回调用函数从被调用函数返回调用函数之前之前，应完成：，应完成：n保存保存被调用函数的被调用函数的计算结果计算结果n释放释放被调用函数的被调用函数的数据区数据区n依照被调用函数保存的依照被调用函数保存的返回地址返回地址将将控制转移控制转移到到调用函数调用函数多个函数嵌套调用的规则是：多个函数嵌套调用的规则是：后调用先返回后调用先返回内存管理实行内存管理实行“栈式管理栈式管理”递归函数递归函数n斐波纳茨函数：斐波纳茨函数：1，1，2，3，5，8，13n求求n的阶乘的递归函数算法的阶乘的递归函数算法:longlongfact(intfact(intn)n)longf;long

23、f;if(nif(n=0)f=1;=0)f=1;elsef=n*fact(n-1);elsef=n*fact(n-1);returnf;returnf;if(nif(n=0)f=1;=0)f=1;elseelsef=n*fact(n-f=n*fact(n-1);1);returnf;returnf;函数函数fact(4)if(nif(n=0)f=1;=0)f=1;elseelsef=n*fact(n-f=n*fact(n-1);1);returnf;returnf;调用调用fact(3)if(nif(n=0)f=1;=0)f=1;elseelsef=n*fact(n-f=n*fact(n-1)

24、;1);returnf;returnf;调用调用fact(2)if(nif(n=0)f=1;=0)f=1;elseelsef=n*fact(n-f=n*fact(n-1);1);returnf;returnf;调用调用fact(1)if(nif(n=0)f=1;=0)f=1;elseelsef=n*fact(n-f=n*fact(n-1);1);returnf;returnf;调用调用fact(0)函数函数fact(3)函数函数fact(2)函数函数fact(1)函数函数fact(0)函数fact(0)的调用返回一个1值返回1函数fact(1)中f=1*1返回值1返回1函数fact(2)中f=

25、2*1返回值2返回2函数fact(3)中f=3*2返回值6返回6n递归函数：直接调用自身或通过一系列的调用递归函数：直接调用自身或通过一系列的调用语句间接地调用自己的函数语句间接地调用自己的函数调用调用fact(3)调用调用fact(4)longlongfact(intfact(intn)n)longf;longf;if(nif(n=0)f=1;=0)f=1;elsef=n*fact(n-1);elsef=n*fact(n-1);returnf;returnf;调用调用调用调用fact(4)fact(4)fact(4)fact(4)调用调用调用调用fact(3)fact(3)fact(3)fa

26、ct(3)调用调用调用调用fact(2)fact(2)fact(2)fact(2)调用调用调用调用fact(1)fact(1)fact(1)fact(1)调用调用调用调用fact(0)fact(0)调用调用fact(2)调用调用fact(1)调用调用fact(0)4r13r22r31r40r5汉诺塔问题汉诺塔问题n如果汉诺塔问题中盘子的个数为如果汉诺塔问题中盘子的个数为64，而，而64个盘个盘的移动次数是：的移动次数是：18，446，744，073，709，551，615这是一个天文数字，若每一微秒可能计算这是一个天文数字，若每一微秒可能计算(并不输出并不输出)一次移动，那么也需要几乎一百万一

27、次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决值时的汉诺塔，但很难用计算机解决64层的层的汉诺塔。汉诺塔。汉诺塔问题分析汉诺塔问题分析n首先考虑首先考虑a杆下面的盘子而非杆上最上面的盘杆下面的盘子而非杆上最上面的盘子，于是任务变成了：子，于是任务变成了：*将上面的将上面的63个盘子移到个盘子移到b杆上；杆上；*将将a杆上剩下的盘子移到杆上剩下的盘子移到c杆上；杆上；*将将b杆上的全部盘子移到杆上的全部盘子移到c杆上。杆上。将这个过程继续下去，就是要先完成移动将这个过程继续下去，就是要先完成移动63个

28、盘子、个盘子、62个盘子、个盘子、61个盘子个盘子.的工作的工作n为了更清楚地描述算法，可以定义一个函数为了更清楚地描述算法，可以定义一个函数hanoi(n,a,b,c)。该函数的功能是：将。该函数的功能是：将N个盘子从个盘子从A杆杆上借助上借助B杆移动到杆移动到C杆上。这样移动第杆上。这样移动第N个盘子的工作个盘子的工作就可以按照以下过程进行：就可以按照以下过程进行：1)hanoi(n-1,a,c,b);功能：将功能：将N-1个盘子从个盘子从A杆上借助杆上借助C杆移动到杆移动到B杆上杆上2)将一个盘子从将一个盘子从A杆杆移动到移动到C杆杆上；上；3)hanoi(n-1,b,a,c)；功能：将

29、功能：将N-1个盘子从个盘子从B杆上借助杆上借助A杆移到杆移到C杆上杆上这样就完成了工作，接着我们要做的就是看怎样完成这样就完成了工作，接着我们要做的就是看怎样完成hanoi(n-1,a,c,b);和和hanoi(n-1,b,a,c)；Voidhanoi(intn,charx,chary,charz)/从柱从柱x上按规则移动编号从上按规则移动编号从1到到n的的n个圆盘到柱个圆盘到柱z上，上，柱柱y辅助移动辅助移动if(n=1)move(1,x,z);/将编号为将编号为1的圆盘从柱的圆盘从柱x移到柱移到柱zelsehanoi(n-1,x,z,y);/将编号从将编号从1到到n-1的圆盘从柱的圆盘从

30、柱x移移到柱到柱y，柱，柱z辅助移动辅助移动move(n,x,z);/将编号为将编号为n的圆盘从柱的圆盘从柱x移到柱移到柱zhanoi(n-1,y,x,z);将编号从将编号从1到到n-1的圆盘从柱的圆盘从柱y移移到柱到柱z，柱，柱x辅助移动辅助移动Addr n x y zVoidhanoi(intn,charx,chary,charz)12if(n=1)3move(1,x,z);4else56hanoi(n-1,x,z,y);7move(n,x,z);8hanoi(n-1,y,x,z);910 0 3 a b c 6 2 a c b调用调用hanoi(3,a,b,c);执行语句执行语句1，2，

31、4，5调用调用hanoi(2,a,c,b);执行语句执行语句1，2，4，5调用调用hanoi(1,a,b,c);执行语句执行语句1，2，3，9hanoi(1,a,b,c)执行完毕执行完毕返回返回hanoi(2,a,c,b);中的第中的第6个语句个语句执行语句执行语句7，8调用调用hanoi(1,c,a,b);执行语句执行语句1，2，3，9hanoi(1,c,a,b)执行完毕执行完毕 6 1 a b c321abc12 8 1 c a b1递归习题n小猴子第一天摘下若干桃子小猴子第一天摘下若干桃子,当即吃掉一半当即吃掉一半,又又多吃一个多吃一个.第二天早上又将剩下的桃子吃一半第二天早上又将剩下的

32、桃子吃一半,又多吃一个又多吃一个.以后每天早上吃前一天剩下的一以后每天早上吃前一天剩下的一半另一个半另一个.到第到第10天早上猴子想再吃时发现天早上猴子想再吃时发现,只只剩下一个桃子了剩下一个桃子了.问第一天猴子共摘多少个桃问第一天猴子共摘多少个桃子？子？n有雌雄一对兔子，假定从两个月开始便可每月有雌雄一对兔子，假定从两个月开始便可每月繁殖雌雄各一的一对小兔子。问过繁殖雌雄各一的一对小兔子。问过n个月后共个月后共有多少对兔子？有多少对兔子？队列n n队列也是一种运算受限的线性表。在这种线性表上，队列也是一种运算受限的线性表。在这种线性表上，队列也是一种运算受限的线性表。在这种线性表上，队列也是

33、一种运算受限的线性表。在这种线性表上，插入限定在表的某一端进行，删除限定在表的另一端插入限定在表的某一端进行，删除限定在表的另一端插入限定在表的某一端进行，删除限定在表的另一端插入限定在表的某一端进行，删除限定在表的另一端进行。进行。进行。进行。n n允许插入的一端称为允许插入的一端称为允许插入的一端称为允许插入的一端称为队尾队尾队尾队尾，允许删除的一端称为，允许删除的一端称为，允许删除的一端称为，允许删除的一端称为队头队头队头队头。n n队列中数据元素的入队和出队过程是按照队列中数据元素的入队和出队过程是按照队列中数据元素的入队和出队过程是按照队列中数据元素的入队和出队过程是按照“先进先出先

34、进先出先进先出先进先出”的原则进行的。因此，队列又称为的原则进行的。因此，队列又称为的原则进行的。因此，队列又称为的原则进行的。因此，队列又称为“先进先出先进先出先进先出先进先出”的的的的线性表，简称线性表，简称线性表，简称线性表，简称(FirstInFirst(FirstInFirstOut)FIFOOut)FIFO表。表。表。表。an-1a1a2aian只允许插入只允许插入只允许插入只允许插入只允许删除只允许删除只允许删除只允许删除n举例举例1：到医院看病，首先需要到挂号处挂号，：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。然后，按号码顺序救诊。n举例举例2：乘坐公共汽车，应该

35、在车站排队，车：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。来后，按顺序上车。n举例举例3：在：在Windows这类多任务的操作系统环这类多任务的操作系统环境中，每个应用程序响应一系列的境中，每个应用程序响应一系列的“消息消息”，像用户点击鼠标；拖动窗口这些操作都会导致像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。断地从

36、队列中读取消息，并依次给予响应。队列的类型定义ADTQueue 数据对象数据对象：D=ai|ai ElemSeti=1,2,.,nn0数据关系数据关系：R1=|ai,ai+1 ElemSet,i=1,2,.,n-10约定约定an端为队列尾，端为队列尾，a1端为队列头端为队列头基本操作基本操作：结构初始化结构初始化InitQueue(&Q)操作结果：构造一个空队列操作结果：构造一个空队列Q销毁结构销毁结构DetroyQueue(&Q)初始条件：队列初始条件：队列Q已经存在已经存在操作结果：销毁队列操作结果：销毁队列Q引用型操作引用型操作QueueEmpty(Q)/判断判断Q是否为空队列，若为空返

37、回是否为空队列，若为空返回True，否则返，否则返回回FalseQueueLength(Q)/得到队列得到队列Q的元素个数，即队列的长度的元素个数，即队列的长度GetHead(Q，&e)/得到得到Q的队列头元素，并将之放入变量的队列头元素，并将之放入变量e中中StackTraverse(Q,visit()/从栈底到栈顶遍历队列从栈底到栈顶遍历队列Q，对每个元素调用，对每个元素调用visit()加工型操作加工型操作ClearQueue(&Q)/清空队列清空队列QEnQueue(&Q,e)/向队列中插入元素向队列中插入元素e为新的队尾元素为新的队尾元素DeQueue(&Q,&e)/删除删除Q的队头

38、元素，并用的队头元素，并用e返回值返回值队列的存储结构n n队列有两种存储表示方法队列有两种存储表示方法:顺序存储和链式存顺序存储和链式存储储队列的顺序存储结构队列的顺序存储结构n n队列的顺序存储结构简称队列的顺序存储结构简称顺序队顺序队n n顺序队是用一维数组依次存放队列中的元素顺序队是用一维数组依次存放队列中的元素,还需要有两个变量分别指示队列的首端和队列还需要有两个变量分别指示队列的首端和队列的尾端。这两个变量分别称为的尾端。这两个变量分别称为“队头指针队头指针”和和“队尾指针队尾指针”an-1a1a2aian出队入队frontrear队列初始为空时队列初始为空时n队头和队尾都为队头和

39、队尾都为0入队时入队时n将新元素插入将新元素插入rear所指的位置，然后将之加所指的位置，然后将之加出队时出队时n删去删去front所指的元素，然后将之减并返回所指的元素，然后将之减并返回被删元素被删元素abc 0 1 2 3 4 5 6 7frontrearrearrearrear由此可见，当头尾指针相等时由此可见，当头尾指针相等时队列为空。队列为空。在非空队列里，头指针始终指在非空队列里，头指针始终指向队头元素，而尾指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。向队尾元素的下一位置。frontabc 0 1 2 3 4 5 6 7defghfrontrear和栈类似，队列中亦有

40、上溢和下溢现象。和栈类似，队列中亦有上溢和下溢现象。0 1 2 3 4 5 6 7frontrearcfront?再继续插入再继续插入?再继续删除再继续删除?什么情况下什么情况下上溢上溢abc 0 1 2 3 4 5 6 7defghfrontrear队尾指针大于数组的最大下标时队尾指针大于数组的最大下标时 0 1 2 3 4 5 6 7rearfront?什么情况下什么情况下下溢下溢队头指针等于队尾指针时队头指针等于队尾指针时abc 0 1 2 3 4 5 6 7defghfrontrearfront队尾指针依然大于数组的最大下标队尾指针依然大于数组的最大下标n此外，顺序队列中还存在此外，顺

41、序队列中还存在“假上溢假上溢”现象。现象。n因为在入队和出队的操作中，头尾指针只增加因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现超出向量空间的上界而不能做入队操作。该现象称为假上溢。象称为假上溢。为克服上述假上溢现象的方法是将向量空间想象为一个为克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循

42、环向量，存储在其首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为中的队列称为循环队列循环队列（CircularQueue)。bacdfrontrearerear 0 1 2 3 4 5 6fronterearbdc 0 1 2 3 4 5 6ffront这种循环意义下的加这种循环意义下的加1 1操作可以描述为：操作可以描述为：if(I+1=if(I+1=QueueSizeQueueSize)i=0;i=0;else else i+;i+;利用模运算可简化为利用模运算可简化为：i=(i+1)%QueueSize？怎么判断队列已满？怎么判断队列已满在循环队列中进行出队、入队操作时，头尾

43、指针仍要在循环队列中进行出队、入队操作时，头尾指针仍要加加1，朝前移动。只不过当头尾指针指向向量上界，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加）时，其加1操作的结果是指向向量的操作的结果是指向向量的下界下界0。0 1 2 3 4 5 6 7rearfront当头尾指针相等时队列为空。当头尾指针相等时队列为空。abc 0 1 2 3 4 5 6 7defghrearfrontrear当头尾指针相等时队列为满。当头尾指针相等时队列为满。n由于入队时尾指针向前追赶头指针，出队由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头指针向前追赶尾指针

44、，故队空和队满时头尾指针均相等。因此，我们无法通过时头尾指针均相等。因此，我们无法通过front=rear来判断队列来判断队列“空空”还是还是“满满”。解决此问题的方法至少有三种：解决此问题的方法至少有三种：其一是另设一个布尔变量以匹别队列的空和满；其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加尾指针在循环意义下加1后是否等于头指针，若相后是否等于头指针，若相等则认为队满（注意：等则认为队满（注意：rear所指的单元始终为空）；所指的单元始终为空）；其三是使用一个计数器记录队列中元素的总数其三是

45、使用一个计数器记录队列中元素的总数（实际上是队列长度）（实际上是队列长度）顺序队列的顺序队列的C#语言描述：（利用计数器）语言描述：（利用计数器）classCSqQueueprivateintmaxSize;/存储队列的容量存储队列的容量privatechardata;/存储数据存储数据privateintfront;/存储队头指针存储队头指针privateintrear;/存储队尾指针存储队尾指针privateintcount;/存储元素个数存储元素个数（1）置空队）置空队voidInitQueue(CSqQueueq)q.Front=q.Rear=0;q.Count=0;（2）判断队空）判

46、断队空intQueueEmpty(CSqQueueq)returnq.Count=0;（4 4）入队）入队voidGetHead(CSqQueueq,charx)if(q.Count=q.MaxSize)Console.writeLine(“queueoverflow”);return;q.Count+;q.Dataq.Rear=x;q.Rear=(q.Rear+1)%q.MaxSize;（5）出队）出队charDeQueue(CSqQueueq)if(QueueEmpty(q)Console.WriteLine(“queueunderflow”);return;chartemp=q.Data

47、q.Front;q.Count-;q.Front=(q.Front+1)%q.MaxSize;returntemp;（6）取头指针）取头指针charQueueFront(CSqQueueq)if(QueueEmpty(q)Console.WriteLine(“queueisempty.”);return;returnq.Dataq.Front;顺序队列的顺序队列的C语言描述：（利用布尔变量）语言描述：（利用布尔变量）classCirQueueprivateintmaxSize;/存储队列的容量存储队列的容量privatechardata;/存储数据存储数据privateintfront;/存储

48、队头指针存储队头指针privateintrear;/存储队尾指针存储队尾指针privateboolempty;/为为True时为空，为时为空，为False为非空为非空（1）置空队）置空队voidInitQueue(CirQueueq)q.Front=q.Rear=0;q.Empty=True;（2）判断队空）判断队空boolQueueEmpty(CirQueueq)if(q.Rear=q.Front&q.Empty)returnq.EmptyelsereturnFalse;（4 4）入队）入队voidGetHead(CirQueueq,charx)if(q.Rear=q.Front&!q.Em

49、pty)Console.WriteLine(“queueoverflow”);return;if(q.Rear=q.Front)q.Empty=False;/如果是第一次插入则更改布尔便量的如果是第一次插入则更改布尔便量的值值q.Dataq.Rear=x;q.Rear=(q.Rear+1)%q.MaxSize;（5）出队）出队charDeQueue(CirQueueq)chartemp;if(q.Rear=q.Front&q.Empty)Console.WriteLine(“queueunderflow”);return;temp=q.Dataq.Front;q.Front=(q.Front+

50、1)%q.MaxSize;if(q.Rear=q.Front)q.Empty=True;returntemp;（6）取头指针）取头指针charQueueFront(CirQueueq)if(q.Rear=q.Front&q.Empty)Console.WriteLine(“queueunderflow”);return;returnq.Dataq.Front;队列的链式存储结构n队列的链式存储结构简称为队列的链式存储结构简称为链队列链队列，它是限制仅，它是限制仅在表头删除和表尾插入的单链表。在表头删除和表尾插入的单链表。n显然仅有单链表的头指针不便于在表尾做插入操显然仅有单链表的头指针不便于在