数据结构第3章栈和队列ppt课件.ppt

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

1、为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1 栈2 算术表达式求值3 队列 第三章第三章 栈和队列栈和队列本章学习导读本章学习导读 从数据结构上看，栈和队列也是线从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作允许在表的一端进行插入或删除操作;而队列只允许在表的一端进行插入操作、而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。队列也可以被称作为操作受限的线

2、性表。通过本章的学习，读者应能掌握栈和队通过本章的学习，读者应能掌握栈和队列的逻辑结构和存储结构，以及栈和队列的逻辑结构和存储结构，以及栈和队列的基本运算和算法的实现。列的基本运算和算法的实现。4学时学时为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.1栈在在各各种种程程序序设设计计语语言言中中都都有有子子程程序序（或或称称函函数数、过过程程）调调用用功功能能。而而子子程程序序也也可可以以调调用用其其它它的的子子程程序序。甚甚至至可可以以直直接接或或间间接接地地调调用用自自身身，这这种种调调用用关关系系就就是是递递归归。下下面面

3、以以求求阶阶乘乘的的递递归归方方法法为例，来分析计算机系统是如何处理这种递归调用关系的。为例，来分析计算机系统是如何处理这种递归调用关系的。求求n！的递归方法的思路是：！的递归方法的思路是：相应的相应的C语言函数是：语言函数是：floatfact(intn)floats;if(n=0|n=1)s=1;elses=n*fact(n-1);return(s);在该函数中可以理解为求在该函数中可以理解为求n！用！用fact(n)来表示，来表示，则求则求(n-1)！就用！就用fact(n-1)来表示。来表示。若求若求5!，则有，则有main()printf(“5!=%fn”,fact(5);)1()1

4、,0()!1(*1!=-=n nnnn为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图图3-1给给出出了了递递归归调调用用执执行行过过程程。从从图图中中可可看看到到fact函函数数共共被被调调用用5次次，即即fact(5)、fact(4)、fact(3)、fact(2)、fact(1)。其其中中，fact(5)为为主主函函数数调调用用，其其它它则则为为在在fact函函数数内内的的调调用。每一次递归调用并未立即得到结果，而是进一步向深用。每一次递归调用并未立即得到结果，而是进一步向深度递归调用，直到度递归调用，直到n=1或或n=0时

5、，函数时，函数fact才有结果为才有结果为1，然后再一一返回计算，然后再一一返回计算，最终得到结果。最终得到结果。主函数主函数mani()printf(“fact(5)”)第一层调用第一层调用n=5s=5*fact(4)第二层调用第二层调用n=4s=4*fact(3)第三层调用第三层调用n=3S=3*fact(2)第四层调用第四层调用n=2S=2*fact(1)第五层调用第五层调用n=1S=1fact(1)=1fact(2)=2fact(3)=6fact(4)=24fact(5)=120输出s=120.00图图3-1递归调用过程示意图递归调用过程示意图为深入学习习近平新时代中国特色社会主义思想

6、和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能计计算算机机系系统统处处理理上上述述过过程程时时，其其关关键键是是要要正正确确处处理理执执行行过过程程中中的的递递归归调调用用层层次次和和返返回回路路径径，也也就就是是要要记记住住每每一一次次递递归归调调用用时时的的返返回回地地址址。在在系系统统中中是是用用一一个个线线性性表表(栈栈)动动态态记记忆忆调调用用过过程程中中的的路径，其处理原则为：路径，其处理原则为：（1）在开始执行程序前，建立一个线性表，其初始状态为空。）在开始执行程序前，建立一个线性表，其初始状态为空。（2）当当发发生生递递归归调调用用时时，将将当当前前的的调

7、调用用的的返返回回点点地地址址插插入入到到线性表的末尾；线性表的末尾；（3）当递归调用返回时，其返回地址从线性表的末尾取出。）当递归调用返回时，其返回地址从线性表的末尾取出。根根据据以以上上的的原原则则，可可以以给给出出线线性性表表中中的的元元素素变变化化状状态态如如图图3-2所示（以递归调用时所示（以递归调用时n值的变化为例）：值的变化为例）：545453453245321图图3-2递归调用时线性表状态递归调用时线性表状态入栈入栈出栈出栈为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.1.1 栈的定义及其运算栈的定义及其运算1

8、栈的定义栈的定义栈栈（stack）是是一一种种只只允允许许在在一一端端进进行行插插入入和和删删除除的的线线性性表表，它它是是一一种种操操作作受受限限的的线线性性表表。在在表表中中只只允允许许进进行行插插入入和和删删除除的的一一端端称称为为栈栈顶顶（top），另另一一端端称称为为栈栈底底(bottom)。栈栈的的插插入入操操作作通通常常称称为为入入栈栈或或进进栈栈(push)，而而栈栈的的删删除除操操作作则则称称为为出出栈栈或退栈或退栈(pop)。当栈中无数据元素时，称为空栈。当栈中无数据元素时，称为空栈。根根据据栈栈的的定定义义可可知知，栈栈顶顶元元素素总总是是最最后后入入栈栈的的，因因而而是

9、是最最先先出出栈栈；栈栈底底元元素素总总是是最最先先入入栈栈的的，因因而而也也是是最最后后出出栈栈。这这种种表表是是按按照照后后进进先先出出（LIFO，lastinfirstout）的的原原则则组组织织数数据据的的，因此，栈也被称为因此，栈也被称为“后进先出后进先出”的线性表。的线性表。a1a2an入栈入栈出栈出栈栈顶栈顶top栈底栈底bottom图图3-3栈的示意图栈的示意图图图3-3是一个栈的示意图，通常用是一个栈的示意图，通常用指针指针top指示栈顶的位置，用指指示栈顶的位置，用指针针bottom指向栈底。栈顶指针指向栈底。栈顶指针top动态反映栈的当前位置。动态反映栈的当前位置。为深入

10、学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2栈的基本运算栈的基本运算（1）initStack(s)初始化：初始化一个新的栈。初始化：初始化一个新的栈。（2）IsEmpty(s)栈栈空空判判断断：若若栈栈s空空，则则返返回回TRUE；否则，返回；否则，返回FALSE。（3）push(s,x)入入栈栈：在在栈栈s的的顶顶部部插插入入元元素素x，若栈满，则返回若栈满，则返回FALSE；否则，返回；否则，返回TRUE。（4）pop(s,x)出出栈栈：若若栈栈s不不空空，则则返返回回栈栈顶顶元元素素，并并从从栈栈顶顶中中删删除除该该元元素素；

11、否否则则，返返回回空空元元素素NULL。（5）getTop(s,x)取取栈栈元元素素：若若栈栈s不不空空，则则返返回回栈顶元素；否则返回空元素栈顶元素；否则返回空元素NULL。（6）ClearEmpty(s)置栈空操作：置栈置栈空操作：置栈s为空栈。为空栈。栈栈是是一一种种特特殊殊的的线线性性表表，因因此此栈栈可可采采用用顺顺序序存存储储结构存储，也可以使用链式存储结构存储。结构存储，也可以使用链式存储结构存储。（7）stacklenth(s)返回栈中元素的个数返回栈中元素的个数.为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.

12、1.2 栈的顺序存储结构栈的顺序存储结构1顺序栈的数组表示顺序栈的数组表示与与第第二二章章讨讨论论的的一一般般的的顺顺序序存存储储结结构构的的线线性性表表一一样样，利利用用一一组组地地址址连连续续的的存存储储单单元元依依次次存存放放自自栈栈底底到到栈栈顶顶的的数数据据元元素素，这这种种形形式式的的栈栈也也称称为为顺顺序序栈栈。因因此此，我我们们可可以以使使用用一一维维数数组组来来作作为为栈栈的的顺顺序序存存储储空空间间。设设指指针针top指指向向栈栈顶顶元元素素的的下下一一个个位位置置，以以数数组组小小下下标标的的一一端端作作为为栈栈底底，通通常常以以top=0时时为为空空栈栈，在在元元素素进

13、进栈栈时时指指针针top不不断断地地加加1，当，当top等于数组的最大下标值时则栈满。等于数组的最大下标值时则栈满。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能top=0top=1Atop=5top=3图图3-4栈的存储结构栈的存储结构（a）空栈）空栈（b）插入元素）插入元素A后后（c）插入元素）插入元素B、C、D、E后后d）删除元素）删除元素E、D后后（a）（b）（c）（d）图图3-4展示了顺序栈中数据元素与栈顶指针的变化。展示了顺序栈中数据元素与栈顶指针的变化。ABABCCDEbasebasebasebase43210432

14、104321043210为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能用用C语言定义的顺序存储结构的栈如下：语言定义的顺序存储结构的栈如下：#defineTRUE1#defineFALSE0#defineSTACK_SIZE50;/存储空间分配增量存储空间分配增量typedefstructStackElementTypeelemSTACK_SIZE;inttop;SqStack;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2顺序栈的基本运算算法顺序栈的基本运算算法（

15、1）初始化栈）初始化栈【算法【算法3.1栈的初始化】栈的初始化】StatusInitStack(SqStack*S)/创建一个空栈由指针创建一个空栈由指针S指出指出S-TOP=0;/InitStack为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（2）入栈操作）入栈操作【算法【算法3.2入栈操作】入栈操作】StatusPush(SqStack&S,SElemTypee)/将元素将元素e插入到栈插入到栈S中，作为中，作为S的新栈顶的新栈顶if(S-top=Stacksize)returnFALSE;S-elemtop=e;S-top

16、+;returnTRUE;/Push为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（3）出栈操作）出栈操作【算法【算法3.3出栈操作】出栈操作】StatusPop(SqStack*S,SElemType*e)/若若栈栈s不不为为空空，则则删删除除栈栈顶顶元元素素,有有e返返回回其其值，并返回值，并返回TRUE；否则返回；否则返回ERRORif(S-top=0)returnERROR;/栈空栈空elseS-top-;*e=S-elemS-top;returnTRUE;/Pop为深入学习习近平新时代中国特色社会主义思想和党的十九大精神

17、,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（4）取栈顶元素操作）取栈顶元素操作【算法【算法3.4取栈顶元素】取栈顶元素】StatusGetTop(SqStackS,SElemType*e)/若若栈栈S不不为为空空，则则用用e返返回回栈栈顶顶元元素素，并并返返回回OK；否则返回；否则返回ERRORif(S-top=0)returnERROR;/栈空栈空else*e=S-elemS-top1;returnOK;/GetTop取取栈栈顶顶元元素素与与出出栈栈不不同同之之处处在在于于出出栈栈操操作作改改变变栈栈顶顶指指针针top的的位位置置，而而取取栈栈顶顶元元素素操操作作不不改改变变栈栈的

18、栈顶指针。的栈顶指针。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（5）判断栈空）判断栈空intIsEmpty(SeqStack*s)return(S-top=0?TRUE:FALSE);为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（6）求栈顶元素个数）求栈顶元素个数intIsFull(SeqStack*S)return(S-top);为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.1.3 多栈共享

19、邻接空间多栈共享邻接空间在在计计算算机机系系统统软软件件中中，各各种种高高级级语语言言的的编编译译系系统统都都离离不不开开栈栈的的使使用用。常常常常一一个个程程序序中中要要用用到到多多个个栈栈，为为了了不不发发生生上上溢溢错错误误，就就必必须须给给每每个个栈栈预预先先分分配配一一个个足足够够大大的的存存储储空空间间，但但实实际际中中很很难难准准确确地地估估计计。另另一一面面方方面面，若若每每个个栈栈都都预预分分配配过过大大的的存存储储空空间间，势势必必会会造造成成系系统统空空间间紧紧张张。若若让让多多个个栈栈共共用用一一个个足足够够大大的的连连续续存存储储空空间间，则则可可利利用用栈栈的的动动

20、态态特特性性使使它它们们的的存存储储空空间间互补。这就是栈的共享邻接空间。互补。这就是栈的共享邻接空间。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1双向栈在一维数组中的实现双向栈在一维数组中的实现栈栈的的共共享享中中最最常常见见的的是是两两栈栈的的共共享享。假假设设两两个个栈栈共共享享一一维维数数组组stackMAXNUM，则则可可以以利利用用栈栈的的“栈栈底底位位置置不不变变，栈栈顶顶位位置置动动态态变变化化”的的特特性性，两两个个栈栈底底分分别别为为-1和和MAXNUM，而而它它们们的的栈栈顶顶都都往往中中间间方方向向延延

21、伸伸。因因此此，只只要要整整个个数数组组stackMAXNUM未未被被占占满满，无无论论哪哪个个栈的入栈都不会发生上溢。栈的入栈都不会发生上溢。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能C语语言言定定义义的的这这种种两两栈栈共共享享邻邻接接空空间间的的结结构构如如下：下：TypedefstructElemtypestackMAXNUM;intlefttop;/*左栈栈顶位置指示器左栈栈顶位置指示器*/int righttop;/*右右栈栈栈栈顶顶位位置置指指示示器器*/dupsqstack;两两个个栈栈共共享享邻邻接接空空间间

22、的的示示意意图图如如图图3-5所所示示。左左栈栈入入栈栈时时，栈栈顶顶指指针针加加1，右右栈栈入入栈栈时时，栈栈顶顶指指针减针减1。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能自由区lefttoprightto0MAXNUM-1图图3-5两个栈共享邻接空间两个栈共享邻接空间charstatus;status=L;/*左栈左栈*/status=R;/*右栈右栈*/在在 进进 行行 栈栈 操操 作作 时时，需需 指指 定定 栈栈 号号：status=L为为 左左 栈栈，status=R为右栈；判断栈满的条件为：为右栈；判断栈满的条件

23、为：s-lefttop+1=s-rigthtop;为了识别左右栈，必须另外设定标志：为了识别左右栈，必须另外设定标志：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2共享栈的基本操作共享栈的基本操作（1）初始化操作）初始化操作【算法【算法3.7共享栈的初始化】共享栈的初始化】intinitDupStack(dupsqstack*s)/*创建两个共享邻接空间的空栈由指针创建两个共享邻接空间的空栈由指针S指出指出*/if(s=(dupsqstack*)malloc(sizeof(dupsqstack)=NULL)returnFALSE

24、;s-lefttop=-1;s-righttop=MAXNUM;returnTRUE;（2）入栈操作）入栈操作【算法【算法3.8共享栈的入栈操作】共享栈的入栈操作】intpushDupStack(dupsqstack*s,charstatus,Elemtypex)*把数据元素把数据元素x压入左栈（压入左栈（status=L）或右栈（）或右栈（status=R）*/if(s-lefttop+1=s-righttop)returnFALSE;/*栈满栈满*/if(status=L)s-stack+s-lefttop=x;/*左栈进栈左栈进栈*/elseif(status=R)s-stack-s-l

25、efttop=x;/*右栈进栈右栈进栈*/elsereturnFALSE;/*参数错误参数错误*/returnTRUE;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（3）出栈操作）出栈操作【算法【算法3.9共享栈的出栈操作】共享栈的出栈操作】ElemtypepopDupStack(dupsqstack*s,charstatus)/*从左栈（从左栈（status=L）或右栈（）或右栈（status=R）退出栈顶元素）退出栈顶元素*/if(status=L)if(s-lefttopstacks-lefttop-);/*左栈出栈左栈出

26、栈*/elseif(status=R)if(s-righttopMAXNUM-1)returnNULL;/*右栈为空右栈为空*/elsereturn(s-stacks-righttop+);/*右栈出栈右栈出栈*/elsereturnNULL;/*参数错误参数错误*/为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.1.4 栈的链式存储结构栈栈也也可可以以采采用用链链式式存存储储结结构构表表示示，这这种种结结构构的的栈栈简简称称为为链链栈栈。在在一一个个链链栈栈中中，栈栈底底就就是是链链表表的的最最后后一一个个结结点点，而而栈栈顶

27、顶总总是是链链表表的的第第一一个个结结点点。因因此此，新新入入栈栈的的元元素素即即为为链链表表新新的的第第一一个个结结点点，只只要要系系统统还还有有存存储储空空间间，就就不不会会有有栈栈满满的的情情况况发发生生。一一个个链链栈栈可可由由栈栈顶顶指指针针top-next唯唯一一确确定定，当当top-next为为NULL时时，是是一一个个空空栈。图栈。图3-6给出了链栈中数据元素与栈顶指针给出了链栈中数据元素与栈顶指针top的关系。的关系。链栈的链栈的C语言定义为：语言定义为：typedefstructStacknodeElemtypedata;StructStacknode*next;slSta

28、cktype;BATop-nextCATop-next（a）含有两个元素）含有两个元素A、B、C的栈的栈（b）删除元素）删除元素C、B后的栈后的栈图图3-6链栈的存储结构图链栈的存储结构图（a）（b）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（1）入栈操作）入栈操作【算法【算法3.10单个链栈的入栈操作】单个链栈的入栈操作】intpushLstack(slStacktype*top,Elemtype*x)/将元素将元素x压入链栈压入链栈top中中slStacktype*p;if(p=(slStacktype*)malloc(s

29、izeof(slStacktype)=NULL)returnFALSE;/申请一个结点申请一个结点p-data=x;p-next=top-next;top-next=p;returnTRUE;（2）出栈操作）出栈操作【算法【算法3.11单个链栈的出栈操作】单个链栈的出栈操作】ElemtypepopLstack(slStacktype*top,elem*x)/从链栈从链栈top中删除栈顶元素中删除栈顶元素slStacktype*p;Elemtypex;if(top-next=NULL)returnFALSE;/空栈空栈p=top-next;top-next=p-next;*x=p-data;fr

30、ee(p);returnx;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.2算术表达式求值算术表达式求值表表达达式式求求值值是是程程序序设设计计语语言言编编译译中中的的一一个个最最基基本本问问题题。它它的的实实现方法是栈的一个典型的应用实例。现方法是栈的一个典型的应用实例。在在计计算算机机中中，任任何何一一个个表表达达式式都都是是由由操操作作数数（operand）、运运算算符符（operator）和和界界限限符符（delimiter）组组成成的的。其其中中操操作作数数可可以以是是常常数数，也也可可以以是是变变量量或或常常量量的

31、的标标识识符符；运运算算符符可可以以是是算算术术运运算算符符、关关系系运运算算符符和和逻逻辑辑运运算算符符；界界限限符符为为左左右右括括号号和和标标识识表表达达式式结结束束的的结结束束符符。在在本本节节中中，仅仅讨讨论论简简单单算算术术表表达达式式的的求求值值问问题题。在在这这种种表表达达式式中中只只含含加加、减减、乘乘、除除四四则则运运算算，所所有有的的运运算算对对象象均均为为单单变变量量。表达式的结束符为表达式的结束符为“#”。算术四则运算的规则为：算术四则运算的规则为：（1）先乘除、后加减；）先乘除、后加减；（2）同级运算时先左后右；）同级运算时先左后右；（3）先括号内，后括号外。）先括

32、号内，后括号外。计算机系统在处理表达式前，首先设置两个栈：计算机系统在处理表达式前，首先设置两个栈：（1）操作数栈（）操作数栈（OPRD）存放处理表达式过程中的操作数。）存放处理表达式过程中的操作数。（2)运运算算符符栈栈（OPTR）存存放放处处理理表表达达式式过过程程中中的的运运算算符符。开开始时，在运算符栈中先在栈底压入一个表达式的结束符始时，在运算符栈中先在栈底压入一个表达式的结束符“#”。表表3-1给给出出了了+、-、*、/、（、）、和和#的的算算术术运运算算符符间间的的优优先先级级的的关系。关系。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发

33、挥中小学图书室育人功能+*/()#+*/(#next=NULL;returnOK;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（2）入队列操作）入队列操作【算法【算法3.24链队列的入队列操作】链队列的入队列操作】StatusEnQueue(LinkQueue&Q,QElemTypee)/将元素将元素e插入到链队列插入到链队列Q中，作为中，作为Q的新队尾的新队尾p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);/存储分配失败存储分配失败p-data=e;p-next=NU

34、LL;/置新结点的指针为空置新结点的指针为空Q.rear-next=p;/将链队列中最后一个结点的指针指向新结点将链队列中最后一个结点的指针指向新结点Q-rear=p;/将队尾指向新结点将队尾指向新结点returnOK;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（3）出队列操作）出队列操作【算法【算法3.25链队列的出队列操作】链队列的出队列操作】StatusDeQueue(LinkQueue&Q,QElemType&e)/若链队列不空，则删除队头元素，用若链队列不空，则删除队头元素，用e返回其值，并返回返回其值，并返回/OK

35、；否则返回；否则返回ERRORif(Q.front=Q.rear)returnERROR;/空队列空队列p=Q.front-next;/取队头取队头e=p-data;Q.front-next=p-next;/删除队头结点删除队头结点if(Q.rear=p)Q.rear=Q.front;free(p);returnOK;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.3.3 队列的顺序存储结构队列的顺序存储结构1顺序队列的数组表示顺序队列的数组表示队队列列的的顺顺序序存存储储结结构构可可以以简简称称为为顺顺序序队队列列，也也就就是

36、是利利用用一一组组地地址址连连续续的的存存储储单单元元依依次次存存放放队队列列中中的的数数据据元元素素。一一般般情情况况下下，我我们们使使用用一一维维数数组组来来作作为为队队列列的的顺顺序序存存储储空空间间，另另外外再再设设立立两两个个指指示示器器：一一个个为为指指向向队队头头元素位置的指示器元素位置的指示器front，另一个为指向队尾的元素位置的指示器，另一个为指向队尾的元素位置的指示器rear。C语语言言中中，数数组组的的下下标标是是从从0开开始始的的，因因此此为为了了算算法法设设计计的的方方便便，在在此此我我们们约约定定：初初始始化化队队列列时时，空空队队列列时时令令front=rear

37、=0，当当插插入入新新的的数数据据元元素素时时，尾尾指指示示器器rear加加1，而而当当队队头头元元素素出出队队列列时时，队队头头指指示示器器front加加1。另另外外还还约约定定，在在非非空空队队列列中中，头头指指示示器器front总总是是指指向向队队列列中中实实际际队队头头元元素素，而尾指示器而尾指示器rear总是指向队尾元素的下一个位置。总是指向队尾元素的下一个位置。与栈完全一样与栈完全一样图图3-9队列的存储结构队列的存储结构（a）空队列（）空队列（b）元素）元素A入队列后（入队列后（c）元素）元素B、C、D、E入队列后（入队列后（d）元素）元素A、B、C出队列后出队列后front=0

38、front=0Afront=0ABED（a）（b）（c）rear=0rear=1rear=5rear=5（d）Efront=3图图3-9给出了队列中头尾指针的变化状态。给出了队列中头尾指针的变化状态。CDD为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2顺序队列的基本运算算法顺序队列的基本运算算法（1）初始化队列）初始化队列【算法【算法3.14顺序队列的初始化】顺序队列的初始化】intinitQueue(sqqueue*q)/创建一个空队列由指针创建一个空队列由指针q指出指出if(q=(sqqueue*)malloc(sizeof

39、(sqqueue)=NULL)returnFALSE;q-front=;q-rear=;returnTRUE;（2）入队列操作）入队列操作【算法【算法3.15顺序队列的入队列操作】顺序队列的入队列操作】intappend(sqqueue*q,Elemtypex)/将元素将元素x插入到队列插入到队列q中，作为中，作为q的新队尾的新队尾if(q-rearMAXNUM-1)returnFALSE;/队列满队列满q-queueq-rear=x;returnTRUE;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（3）出队列操作）出队列操作

40、【算法【算法3.16顺序队列的出队列操作】顺序队列的出队列操作】Elemtypedelete(sqqueue*q)/*若队列若队列q不为空，则返回队头元素不为空，则返回队头元素*/Elemtypex;if(q-rear=q-front)returnNULL;/*队列空队列空*/x=q-queueq-front;returnx;（4）取队头元素操作）取队头元素操作【算法【算法3.17顺序队列的取头元素操作】顺序队列的取头元素操作】ElemtypegetHead(sqqueue*q)/*若队列若队列q不为空，则返回队头元素不为空，则返回队头元素*/if(q-rear=q-front)returnN

41、ULL;/*队列空队列空*/return(q-queues-front);（5）判队列非空操作）判队列非空操作【算法【算法3.18顺序队列的非空判断操作】顺序队列的非空判断操作】intEmpty(sqqueue*q)/*队列队列q为空时，返回为空时，返回TRUE；否则返回；否则返回FALSE*/if(q-rear=q-front)returnTRUE;returnFALSE;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（6）求队列长度操作）求队列长度操作【算法【算法3.19顺序队列的求长度操作】顺序队列的求长度操作】intlen

42、gth(sqqueue*q)/*返回队列返回队列q的元素个数的元素个数*/return(q-rear-q-front);3循环队列循环队列MAXNUM-101rearfront图3-10循环队列示意图在在顺顺序序队队列列中中，当当队队尾尾指指针针已已经经指指向向了了队队列列的的最最后后一一个个位位置置时时，此此时时若若有有元元素素入入列列，就就会会发发生生“溢溢出出”。在在图图3-9（c）中中队队列列空空间间已已满满，若若再再有有元元素素入入列列，则则为为溢溢出出；在在图图3-9（d）中中，虽虽然然队队尾尾指指针针已已经经指指向向最最后后一一个个位位置置，但但事事实实上上队队列列中中还还有有3

43、个个空空位位置置。也也就就是是说说，队队列列的的存存储储空空间间并并没没有有真真正正满满，但但队队列列却却发发生生了了溢溢出出，我们称这种我们称这种现象为假溢现象为假溢出。解决这出。解决这个问题有两个问题有两种可行的方种可行的方法：法：rear=5（d）Efront=3D图图3-9队列的存储结构队列的存储结构为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（1）采采用用平平移移元元素素的的方方法法，当当发发生生假假溢溢出出时时，就就把把整整个个队队列列的的元元素素平平移移到到存存储储区区的的首首部部，然然后后再再插插入入新新元元素素

44、。这这种种方方法法需需移移动动大量的元素，因而效率是很低的。大量的元素，因而效率是很低的。（2）将将顺顺序序队队列列的的存存储储区区假假想想为为一一个个环环状状的的空空间间，如如图图3-10所所示示。我我们们可可假假想想q-queue0接接在在q-queueMAXNUM-1的的后后面面。当当发发生生假假溢溢出出时时，将将新新元元素素插插入入到到第第零零号号位位置置上上，这这样样做做，虽虽然然物物理理上上队队尾尾在在队队首首之之前前，但但逻逻辑辑上上队队首首仍仍然然在在前前。入入列列和和出出列列仍仍按按“先进先出先进先出”的原则进行，这就是循环队列。的原则进行，这就是循环队列。很很显显然然，方方

45、法法二二中中不不需需要要移移动动元元素素，操操作作效效率率高高，空空间间的的利利用率也很高。用率也很高。在在循循环环队队列列中中，每每插插入入一一个个新新元元素素时时，就就把把队队尾尾指指针针沿沿顺顺时时针方向移动一个位置。即：针方向移动一个位置。即：q-rear=q-rear+1;if(q-rear=MAXNUM)q-rear=0;在在循循环环队队列列中中，每每删删除除一一个个元元素素时时，就就把把队队头头指指针针沿沿顺顺时时针针方方向移动一个位置。即：向移动一个位置。即：q-front=q-front+1;if(q-front=MAXNUM)q-front=0;为深入学习习近平新时代中国特

46、色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能012345frontrear(b)ABBC012345frontrear(a)25D0134frontABEFCrear(c)图图3-11循环队列示意图循环队列示意图（a）队列空；（）队列空；（b）队列非空；）队列非空；(c)队列满队列满图图3-11所所示示，为为循循环环队队列列的的三三种种状状态态，图图3-11（a）为为队队列列空空时时，有有q-front=q-rear；图图3-11（c）为为队队列列满满时时，也也有有q-front=q-rear；因因此此仅仅凭凭q-front=q-rear不不能能判判定定队

47、队列列是空还是满。是空还是满。D为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能ABEC循循环环队队列列不不论论是是空空还还是是满满front始始终终和和rear相相等等，为为了了区区分分循循环环队队列列是是空空还还是是满满，我我们们可可有有两两种种处处理理方方法法：其其一一是是设设定定一一个个标标志志位位s，当当s=0时时为为空空队队列列，s=1时时队队列列非非空空；其其二二是是少少用用一一个个元元素素空空间间，约约定定以以“队队列列头头指指针针在在队队列列尾尾指指针针的的下下一一个个位位置置（指指环环状状的的下下一一个个位位置置

48、）上上”作作为为队队列列呈呈“满满”状状态态的的标标志志。如下图。如下图。用用C语言定义循环队列结构如下：语言定义循环队列结构如下：#defineMAX100/最大队列长度最大队列长度typedefstructQElemTypeelemMAX;/初始化的动态分配存储空间初始化的动态分配存储空间intfront;/头指针，若队列不空，指向队列头元素头指针，若队列不空，指向队列头元素intrear;/尾指针，若队列不空，指向队列尾元素的下一个尾指针，若队列不空，指向队列尾元素的下一个/位置位置SqQueue;0134CfrontrearD25当当Q.rear+1)%MAXSIZE=Q.front当

49、当Q.front=Q.rear队列为满队列为满队列为空队列为空为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（1）初始化队列）初始化队列【算法【算法3.20循环队列的初始化】循环队列的初始化】StatusInitQueue(SqQueue&Q)/创建一个空队列创建一个空队列QQ.front=Q.rear=0;returnOK;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（2）入队列操作）入队列操作【算法【算法3.21循环队列的入队列操作】循环队列的入队列操作】Sta

50、tusEnQueue(SqQueue&Q,QElemTypee)/*将元素将元素e插入到队列插入到队列Q中，作为中，作为Q的新队尾的新队尾*/if(Q.rear+1)%MAXSIZE=Q.front)returnERROR;/队列满队列满Q-elemQ.rear=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;（3）出队列操作）出队列操作【算法【算法3.22循环队列的出队列操作】循环队列的出队列操作】StatusDeQueue(SqQueue&q,QElemType&e)/若队列不空，则删除若队列不空，则删除Q的队头元素，用的队头元素，用e返回其值，并返回返回其值，并