数据结构与算法3

第3章栈和队列

（4课时）栈是一种插入和删除操作都只能在表的同一端进行的线性表。允许进行插入和删除操作的一端叫做栈顶(Top)，也称为表尾；另一端叫做栈底(Bottom)，也称为表头。当栈中没有元素时称为空栈。向栈中插入元素的操作称为进栈或入栈(push)，从栈中删除元素的操作称为退栈或出栈(pop)。3.1栈及其抽象数据类型3.1栈及其抽象数据类型3.1.1栈的基本概念3.1.2栈的抽象数据类型设栈S=(e1，e2，…，en)，则e1称为栈底元素，en为栈顶元素，图3-1是栈的示意图。栈中元素是以e1，e2，…，en的顺序进栈，而出栈的顺序却是en,…,e2,e1。也就是说栈是按照“先进后出”(FILO，FirstInLastOut）或“后进先出”(LIFO，LastInFirstOut）的原则组织数据的。所以，栈也被称为后进先出LIFO、先进后出FILO线性表或下推表。3.1栈及其抽象数据类型3.1.1栈的基本概念图3-1栈的示意图创建一个空栈删除一个栈判断栈是否为空判断栈是否为满栈顶插入一个元素求栈顶元素的值删除栈顶的一个元素输出栈3.1栈及其抽象数据类型栈一般需要进行下面的基本操作栈的抽象数据类型Stack定义如下：ADTStack{数据对象D={ei|ei∈T,i=1,2,…,n，n≥0}数据关系R={<ei-1,ei>|ei-1，ei∈T,i=2,3,…,n}基本操作P：

Create()：创建空栈

Destroy()：删除栈boolIsEmpty()：判断栈是否为空，空返回true，非空返回false boolIsFull()：判断栈是否为满，满返回true，不满返回false boolPush(constT&x)：在栈顶插入元素x，返回插入后的栈

boolTop(T&x)： 求栈顶元素的值放入x中boolPop(T&x)：从栈顶删除一个元素，并将该元素的值放入x中 voidOutPut()：输出栈}ADTStack3.1栈及其抽象数据类型3.1.2栈的抽象数据类型3.2栈的表示及实现栈是一种线性表，因此，将线性表的顺序和链式存储结构应用于栈时，就建立了顺序栈和链式栈。下面分别介绍栈的顺序表示及实现和链式表示及实现，以及栈的简单应用。3.2栈的表示及实现3.2.1栈的顺序表示及实现3.2.3栈的链式表示及实现3.2.2顺序栈代码复用实例3.2栈的表示及实现采用顺序存储结构表示的栈称为顺序栈。顺序栈需要分配一块连续的存储区域来存放栈中的元素。顺序栈可以用一维数组实现。因为栈底位置是固定不变的，所以可把栈底设置在一维数组的任意一端。栈顶位置随着进栈和出栈操作不断变化，因此用一个变量来指示当前栈顶位置。3.2.1栈的顺序表示及实现3.2栈的表示及实现由于一个栈可能有n个数据元素，也可能是空栈。所以，在顺序栈类模板的数据成员中，除了用来实现顺序栈的动态数组element，还有两个int型数据成员MaxSize和top。MaxSize用来标识栈的最大长度，top用来标识当前顺序栈的栈顶。顺序栈的Create创建操作和Destroy删除操作，使用的是类的构造函数和析构函数来实现的。使用构造函数LinearStack(intLSMaxSize)创建一个空栈时，首先根据参数LSMaxSize，为栈申请一个用指针element指向的长度为LSMaxSize*sizeof(T)个字节的连续空间，然后将栈顶top赋值为-1，表示空栈。析构函数~LinearStack()负责回收申请的栈空间。3.2.1栈的顺序表示及实现3.2栈的表示及实现假设一个空的顺序栈，元素A、B、C、D、E、F依次进栈；然后元素再出栈，则该顺序栈的进栈和出栈动态变化如图3-2所示。(a)空栈(b)插入元素A后(c)插入元素B、C、D、E、F后(d)两个元素出栈后(e)所有元素出栈后图3-2顺序栈的动态变化示意图3.2.1栈的顺序表示及实现3.2栈的表示及实现当栈中已有MaxSize个元素时，如果再进行进栈操作，则会产生溢出，此时称为上溢（Overflow）；而对空栈进行出栈操作时也会产生溢出，此时称为下溢（Underflow）。因此，在进行进栈或出栈操作时，应首先检查栈是否为满(IsFull)或是否为空(IsEmpty)。 IsEmpty()的算法是：

returntop==-1; IsFull()的算法是：

returntop==MaxSize;

实现求栈中元素的个数GetElementNumber()的算法是：

returntop+1;3.2.1栈的顺序表示及实现3.2栈的表示及实现进栈操作Push(constT&x)是向栈顶插入一个值为x的元素，进栈操作算法是： if(IsFull()) returnfalse; else { top++; element[top]=x; returntrue; }3.2.1栈的顺序表示及实现3.2栈的表示及实现出栈操作Pop(T&x)是将栈顶元素放到x中，然后，栈顶下移。出栈操作算法是：if(IsEmpty())

returnfalse;else{

x=element[top]; top--; returntrue;}上述算法都是在栈顶进行的，因此算法的复杂度为O(1)。3.2.1栈的顺序表示及实现3.2栈的表示及实现【例3-1】将十进制数转换为其他各种进制（如2、8、16）数。分析：将一个给定的十进制数n转化成基数为base的进制数，可以采用“除基取余法”。由于该方法最早除得的余数最后使用，所以可以使用栈。将每一次除得的余数进栈，等到所有除法结束后，再将栈中元素依次出栈即可得到转换后的结果。下面只需要基于LinearStack类模板生成数据类型为int类的模板类对象，就可以直接使用类中提供的相应成员函数解决问题了。3.2.2顺序栈代码复用实例把栈组织成一个单链表，即采用链接结构来表示栈，这样的数据结构称为链接栈。图3-3链接栈示意图栈的链式存储结构一般是通过单链表来实现的。在单链表中，每一个结点表示栈中的一个元素。由于栈是在链表头部进行插入和删除操作，故链接栈不需要再设置表头结点。栈顶指针top就是链接栈的头指针，它可以唯一地确定一个栈。假设元素e1,e2,...,en依次进栈，则图3-3是该链接栈的示意图。3.2栈的表示及实现3.2.3栈的链式表示及实现图3-3链接栈示意图由于链接栈具有动态分配元素结点的特点，所以，在内存足够大的情况下，可以认为链接栈中最大元素的个数没有限制。因此在下面的单向链接栈类模板描述中去掉了判断栈满的操作IsFull。其他基本操作与前面的顺序栈基本操作的含义完全相同。下面将链接栈存储结点的类模板命名为LinkNode，将单向链接栈的类模板命名为LinkStack。3.2栈的表示及实现3.2.3栈的链式表示及实现在对链接栈的基本操作中，使用较多的是进栈和出栈操作。进栈Push就是向链接栈的栈顶插入一个元素结点，先将待进栈结点的指针域指向原来的栈顶结点，然后将栈顶指针top修指向该结点，使进栈元素结点成为新的栈顶结点。出栈Pop就是从链接栈的栈顶删除一个元素结点，先将栈顶元素取出放到x中，然后使栈顶指针top指向原栈顶结点的后继结点，然后物理上删除该结点。当top为空时，链接栈为空。删除链接栈时使用析构函数~LinkStack来完成，~LinkStack的工作是将所有元素出栈。3.2栈的表示及实现3.2.3栈的链式表示及实现3.3队列及其抽象数据类型3.3.1队列的基本概念3.3.2队列的抽象数据类型排队是日常生活中最常见的现象，在车站买票、在银行办理业务等许多场合都需要排队。排队的特点是新来的人要站在在队尾，而队首的人先离开。这种“先来先服务”的办事方式就可以抽象成队列这种数据结构。队列是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。队列的插入操作也成为入队，允许入队的一端称为队尾（rear）；队列的删除操作也称为出队，允许出队的一端称为队头（front）。不含元素的队列称为空队列。因此，队列又称为“先进先出”（FIFO，FirstInFirstOut）或“后进后出”（LILO，LastInLastOut）线性表。3.3队列及其抽象数据类型3.3.1队列的基本概念3.3队列及其抽象数据类型3.3.1队列的基本概念设队列Q=(e1，e2，…，en)，队列中的元素是按e1、e2、e3、…、en

的顺序进入队列，则e1为队头元素，en为队尾元素。图3-4是队列的示意图。在元素退出队列时，只能按e1、e2、e3、…、en

的顺序进行。图3-4队列的示意图3.3队列及其抽象数据类型队列一般需要进行下面的基本操作：创建一个队列删除一个队列判断队列是否为空判断队列是否为满在队尾插入一个元素取队头元素的值队头元素出队输出队列3.3.1队列的基本概念3.3队列及其抽象数据类型根据3.3.1节对队列及其基本操作的抽象，抽象数据类型中的元素类型用T来表示，则队列的抽象数据类型Queue定义如下：

ADTQueue{

数据对象D={ei|ei∈T,i=1,2,…,n，n≥0}

数据关系R={<ei-1,ei>|ei-1，ei∈D,i=2,3,…,n}

基本操作P：

Create()：创建空队列

Destroy()：删除队列

boolIsEmpty()：判断队列是否为空，空返回true，非空返回false boolIsFull()： 判断队列是否为满，满返回true，不满返回false boolInsert(constT&x)：入队，在队列尾部插入元素x boolGetElement(T&x)：取队头元素的值放入x中

boolDelete(T&x)： 出队，从队头删除一个元素，并将该元素的值放入x中

voidOutPut()：输出队列 }ADTQueue3.3.2队列的抽象数据类型3.4队列的表示及实现队列的表示与栈和一般线性表一样，通常也可以采用顺序表示和链式表示。本节分别介绍队列的顺序表示及实现和链式表示及实现的方法。3.4队列的表示及实现3.4.1队列的顺序表示及实现3.4.2队列的链式表示及实现3.4队列的表示及实现采用顺序存储结构的队列也称为顺序队列。顺序队列通常用一个一维数组来存放队列中的数据元素。此外，还需设置两个整型变量front和rear，分别指示队头和队尾，称为头指针和尾指针。为了运算的方便，在此约定，在非空队列里，front始终指向队头元素，而rear始终指向队尾元素的下一位置。初始化队列时，front和rear均置为0。队列元素的入队和出队操作是最基本的操作。顺序队列入队时，将新元素插入到rear所指位置后，再将rear的值加1；顺序队列出队时，删除front所指位置的元素后，再将front的值加1并返回被删元素。可见，队列为空的条件是：front==rear3.4.1队列的顺序表示及实现3.4队列的表示及实现3.4.1队列的顺序表示及实现图3-5队列变化示意图3.4队列的表示及实现在顺序队列中，同顺序栈一样，也存在队列溢出的问题。当队列满时，再做入队操作，这种现象称为“上溢”。如在图3-5(c)所示状态下，再做入队操作，就会产生“上溢”。当队列空时，再做出队操作，这种现象称为“下溢”。如在图3-5(e)所示状态下，再做出队操作，就会产生“下溢”。由于队列经常要做插入或删除操作，front和rear会随着插入或删除操作进行变化。在图3-5(d)所示状态下，如果还有新元素请求入队时，虽然队列的实际可用空间没有占满，但由于尾指针已超越存储空间的上界，也不能做入队操作，这种现象称为“假上溢”。3.4.1队列的顺序表示及实现3.4队列的表示及实现为避免发生顺序队列的“假上溢”现象，充分利用队列的存储空间，可以将队列将顺序队列存储空间的最后一个位置和第一个位置逻辑上连接在一起。这样的队列称“循环队列”。假设当前循环队列最多能容纳MaxSize个元素，逻辑上的循环是通过头、尾指针的加1操作实现的： front=(front+1)%(MaxSize-1） rear=(rear+1)%(MaxSize-1)在循环队列中进行入队、出队操作时，头、尾指针仍然加1，但当头或尾指针已经指向了存储空间的上界时，通过上面逻辑上的循环方法，再加1的操作结果是指向下界0。3.4.1队列的顺序表示及实现3.4队列的表示及实现3.4.1队列的顺序表示及实现图3-6是对图3-5中的队列采用循环队列后的示意图。3.4队列的表示及实现在图3-6（d）状态时，如果还有新元素请求入队时，由于rear循环指向了0，所以能够进行入队操作，解决了“假上溢”的问题。但是，在队列满的3-5（c）状态和队列空的3-6(a)或3-6（e）状态，都有相同的front==rear关系。因此，在循环队列中，仅依据头尾指针相等是无法判断队列是“空”还是“满”。要解决判断循环队列是空还是满的问题，可以采用两种方法：（1）约定少用一个元素空间。入队前，如果关系“(rear+1)%(MaxSize-1)==front”存在，就认为队列已满，再要插入就会发生溢出。可见，这种方法rear始终指向那个空闲的元素空间。（2）使用一个计数器size记录当前队列的实际长度。如果size=0，则当“front==rear”时，当前队列是空队列，可以进行入队操作；否则，当前队列满，不能进行入队操作。3.4.1队列的顺序表示及实现【例3-2】在屏幕上显示杨辉三角。杨辉三角的特点是第n行有n个数，除了第一个数和最后一个数是1外，其他数是上一行中位其左右的两个数之和。如图3-7所示的是6行杨辉三角的情况。图3-7杨辉三角分析：根据第i行和第i+1行的变换规律，可以用循环队列来完成杨辉三角的显示任务。具体方法将第1行的1入队，然后循环进行如下操作：在输出第i行时，计算第i+1行的数据并将他们依次入队。为了便于计算，将队列的最大容量设置为n+2，在相邻的两行元素之间加一标识‘0’来区别不同行的队列元素。通过不断地入队和出队，来完成杨辉三角的输出。下面基于LinearStack类模板生成数据类型为int类的模板类对象，直接使用类中的相应成员函数解决这个问题。3.4队列的表示及实现3.4.1队列的顺序表示及实现队列的链式存储结构是仅在表头删除结点和在表尾插入结点的单链表，也为链接队列。因为需要在表头进行删除操作和在表尾进行插入操作，所以在链接队列中，需要增加指向队头和队尾的两个指针front和rear。这样，一个链接队列就由一个头指针front和一个尾指针rear唯一地确定了。图3-8是存储了n个元素的链接队列的示意图。3.4队列的表示及实现3.4.2队列的链式表示及实现图3-8链接队列示意图3.5应用实例栈的实际应用相当广泛，例如，除数制的转换外，栈还可用于解决括号匹配检查、行编辑处理和表达式求解、走迷宫，以及高级语言中函数的嵌套调用和递归的实现等问题。队列在日常生活中应用也很多，特别是在计算机科学领域中所起的作用很大，例如，操作系统中各种资源请求排队和各种缓冲区的先进先出管理，各种应用系统中的事件规划和事件模拟，树的层次遍历和图的广度优先遍历等，都使用了队列这样的数据结构。3.5应用实例3.5.1栈的应用实例3.5.2队列的应用实例【例3-3】计算机的编译程序需要检查一个表达式中括号是否匹配问题。如在C++语言中，表达式中允许使用两种括号：圆括号和方括号。设计一种对C++语言的表达式中的括号是否匹配进行检验的算法。求解思路：括号匹配的处理过程与栈的特点相吻合，可以用栈来实现。具体算法是：从左向右扫描表达式，并设置一个栈，若是左括号则压入栈中；若是右括号，如果它能与当前栈顶元素相匹配，则删除栈顶元素，继续下一次扫描，如果不能与栈顶元素匹配，则认为当前表达式括号匹配不正确而返回。下面采用链接栈来实现“检查括号是否匹配”的问题，假设一个表达式的结束符为‘#’。3.5应用实例3.5.1栈的应用实例下面举一个用队列来解决的生活中常见的日程安排问题。【例3-4】运动会日程安排问题。设计一个算法，使运动会的日程最短，同时保证每个运动员参加的不同项目在时间安排上不会出现冲突。3.5应用实例3.5.2队列的应用实例图3-9项目时间冲突矩阵分析：问题实质是将项目分成几个组，使参加每组中项目的运动员在时间上不会发生冲突；为了使运动会的日程最短，划分的项目组数要最少。运动员项目在时间上的冲突关系可以用一个矩阵R来表示出来，如图3-9所示。假设一名运动员报名参加项目1和项目3，则表示这两个项目在时间上冲突，在图3-9中的矩阵R的元素r1,3或r3,1的值就是1。如果没有任何运动员同时参加项目1和项目3，则矩阵R的元素r1,3或r3,1的值就是0。3.5应用实例3.5.2队列的应用实例具体实现方法：假设有n个项目，用一个二维数组R存放项目的冲突关系矩阵，用队列Q来存放待分组的项目编号，初始时为0，1，2,…,n-1。用Group[]存放当前划分到同一组的项目号，数组元素初始值都为0。用一维数组Result[n]来存放项目被划分的组号，数组元素初始值都为0，如果项目i被划分到第j组，则Result[i]=j。具体算法是采用循环筛选法,从第1个项目开始，凡与第1个项目无冲突的项目划归为一组，然后，在剩下的项目中进行类似操作划分出第二组，依此类推，直到所有的项目都被划分进组。3.5.2队列的应用实例3.5应用实例针对图3-9的运动会项目安排问题，程序的运行结果如下：

请输入运动会项目数：4请输入运动员时间冲突矩阵：0100，1010，0101，0010第1组同时比赛的项目包括：1号项目3号项目第2组同时比赛的项目包括：2号项目4号项目提示：这个问题的本质是一个无冲突子集的划分问题。无冲突子集的划分问题的形式化描述为：已知集合A={a1，a2，…，an}，对应于A上的关系有R={(ai，aj)|ai，aj∈A，i≠j，i，j=1，2，…，n}，其中ai与aj之间存在冲突关系。现要求将A划分成互不相交的子集A1，A2，…，Am(m≤n)，使任何子集上的数据元素均无冲突，同时要求划分出的子集的个数尽可能少。实际应用中的无冲突子集的划分问题都可以用上面的算法进行求解。3.5.2队列的应用实例3.5应用实例本章小结本章主要介绍了栈和队列的特点和抽象数据类型，并给出了实现顺序栈、链接栈、顺序队列和链接队列完整的C++程序代码以及如何复用这些代码解决实际应用问题的实例和方法。通过对本章的学习，读者应对栈和队列这两种被广泛用于日常生活和计算机领域的数据结构有一个全面的认识，掌握栈和队列的顺序结构及其链式结构的表示和实现方法，并通过一定的练习，能逐渐熟练地使用教材中的代码解决实际问题。1．具有什么特征的数据结构被称为栈和队列？先进后出、栈顶、栈底、先进先出、队头、队尾的概念是什么？2．简述在顺序栈的栈顶插入一个元素的操作过程。3.一个栈的输入序列为1、2、3，试给出全部可能的出栈序列。4．循环队列的优点是什么？在循环队列中，仅依据头尾指针相等，无法判断队列是“空”还是“满”。要解决这个问题，常用的两种方法是什么？5.简述在链接栈中插入一个元素的操作过程。6．请列举出一些可以用栈和队列表示的实际问题。习题3实习目的1.熟悉并掌握栈的定义及特点。2.熟悉并掌握顺序栈和链接栈的描述方法和基本操作的实现。3.能够使用栈解决实际应用问题。上机实习实习1栈的操作实习内容1.用链接栈实现例【例3-1】将十进制数转换为其他各种进制（如2、8、16）数的问题。2.针对【描述3-2】中输出顺序栈的运算是倒序输出