《数据结构与算法分析 第3章.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析 第3章.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第3 3章章 栈和队列栈和队列 第第3 3章章 栈和队列栈和队列 堆栈和队列是两种特殊的线性表。堆栈的主要特点是只能在栈顶操作，也就是遵循先进后出的运算规则。队列的主要的特点是只能在一端插入，另一端删除的一种线性表，也就是遵循先进先出的运算规则。3.1 3.1 栈栈3.1.1 栈定义及基本概念栈定义及基本概念栈（Stack）又称堆栈，是限制在表的一端进行插入和删除运算的线性表。通常称能够进行插入、删除运算的这一端为栈顶（Top），另一端称为栈底（Bottom）。当表中没有元素时称为空栈。习惯上将每次删除（也称为退栈）操作又称为弹出（POP）操作。删除的元素总是当前栈中“最新”的元素（栈顶元素
2、）。每次插入（称为进栈）操作称为压入（PUSH）操作，压入的元素总是当前栈中“最新”的元素。3.1 3.1 栈栈3.1.1 栈定义及基本概念栈定义及基本概念 在空栈中最先插入的元素总被放在栈的底部，只有所有元素被弹出之后它才能被删除。当栈满时进栈运算称为“上溢”；当栈空时退栈运算称为“下溢”。堆栈的存储结构有顺序存储结构和链式存储结构两种，在顺序存储结构下，可以考虑堆栈的上溢，而在链式存储结构下，不必考虑对杂货内的上溢现象，只需要考虑堆栈的下溢现象。3.1 3.1 栈栈3.1.1 栈定义及基本概念栈定义及基本概念堆栈上溢是一种出错状态，应该设法避免之；而下溢则可能是正常现象，通常下溢用来作为程
3、序控制转移的条件。堆栈的运算规则是按后进先出的原则进行的（又称为后进先出），简称为LIFO（last in first out）表。就线性表而言，实现栈的方法有很多，我们着重介绍顺序栈（arrary-based stack）和链式（linked stack）栈，它们类似于顺序表和链式表。3.1 3.1 栈栈3.1.1 栈定义及基本概念栈定义及基本概念栈的基本运算一般有以下几种：InitStack（S）构造一个空栈S。StackEmpty（S）判栈空，若S为空栈返回TRUE，否则返回FALSE。StackFull（S）判栈满，若S为满栈，则返回TRUE，否则返回 FALSE。该运算只适用于栈的顺
4、序存储结构。Push（S，x）进栈。若栈S不满，则将元素x压入S的栈顶。Pop（S）退栈。若栈S非空，则将S的栈顶元素弹出，并返回该元素。StackTop（S）取堆栈的栈顶元素，不修改栈顶指针。比较重要的运算就是入栈和出栈两种。3.1 3.1 栈栈3.1.2 顺序栈顺序栈 顺序栈的实现从本质上讲，就是顺序线性表实现的简化。惟一重要的是需要确定应该用数组的哪一端表示栈顶。一种选择是把数组的第0个位置作为栈顶。根据线性表的函数，所有的插入(insert)和删除(remove)操作都在第0个位置的元素上进行。由于这时每次push(insert)或者pop(remove)操作都需要把当前栈中的所有元素
5、在数组中移动一个位置，因此效率不高。如果栈中有n个元素，则时间代价为O(n)。另一种选择是当栈中有n个元素时把位置n-1作栈顶。也就是说，当向栈中压人元素时，把它们添加到线性表的表尾，成员函数pop也是删除表尾元素。在这种情况下，每次push或者pop操作的时间代价仅为O(1)。3.1 3.1 栈栈3.1.2 顺序栈顺序栈堆栈的运算主要考虑堆栈的入栈和出栈算法。其原因是在堆栈的基本运算中有六种：判断堆栈空、堆栈初始化、判断堆栈满（仅限于顺序存储的情况下），入栈元素、出栈元素、取栈顶元素等，而入栈时需要考虑的操作步骤是：堆栈初始化，然后判断堆栈是否为满，如果不满，则可以插入元素（入栈）；出栈时，
6、需要考虑的步骤是：判断堆栈是否为空，如果不空，删除元素（出栈），出栈之前，保存栈顶元素。也就是说，堆栈的入出栈运算包含了其他的六种基本运算，取栈顶元素的运算，只是不用修改栈顶的指针而已。3.1 3.1 栈栈3.1.3 链式栈链式栈 堆栈的链式存储，称为链栈（单向链表存储堆栈）。链式栈的基本运算同顺序栈，定义也同线性表的链表定义，它是对链表实现的简单化（因为它只是对链表的头部操作）。它的元素只能在表头进行插入和删除。在链式存储结构中，不需要给出表头结点，因为其中惟一的已知条件是栈顶指针top，它是指向链式栈的第一个结点（相当于头结点）。堆栈的各种运算比链式存储的普通线性表运算实现时要方便得多，主
7、要原因是堆栈的各种运算只能在堆栈的一端操作，堆栈是特殊的线性表，我们只要考虑对线性表的一端操作的情况，并且只能在一端插入删除（栈顶）；而线性表除此之外（不限定一端插入删除），还需要考虑另外一端结点以及中间的结点的插入、删除、查询等操作，理解时，我们可以把堆栈的入出堆栈运算当作线性表的一端进行插入删除的特例即可。注意：堆栈的运算一定遵循“先进后出”的运算规则。3.1 3.1 栈栈3.1.4 顺序栈和链式栈的比较顺序栈和链式栈的比较 实现链式栈和顺序栈的操作，都是需要常数时间，即时间复杂度为O（1）。主要两者从空间和时间两个方面考虑：初始时，顺序堆栈必须说明一个固定的长度，当堆栈不够满时，造成一些
8、空间的浪费，而链式堆栈的长度可变则是长度不需要预先设定，相对比较节省空间，但是在每个结点中，设置了一个指针域，从而产生了结构开销。3.1 3.1 栈栈3.1.4 顺序栈和链式栈的比较顺序栈和链式栈的比较当需要多个堆栈共享时，顺序存储中可以充分利用顺当需要多个堆栈共享时，顺序存储中可以充分利用顺序栈的单向延伸性。可以使用一个数组存储两个堆栈，序栈的单向延伸性。可以使用一个数组存储两个堆栈，使每个堆栈从各自的端点向中间延伸，这样浪费的空使每个堆栈从各自的端点向中间延伸，这样浪费的空间就会减少。但这种情况只有当两个堆栈的空间需求间就会减少。但这种情况只有当两个堆栈的空间需求有相反的需求时，这种方法才
9、有效。也就是说，最好有相反的需求时，这种方法才有效。也就是说，最好一个堆栈增长，一个堆栈缩短。反之，如果两个堆栈一个堆栈增长，一个堆栈缩短。反之，如果两个堆栈同时增长，则可能比较容易造成堆栈的溢出。如果多同时增长，则可能比较容易造成堆栈的溢出。如果多个顺序堆栈共享空间，则可能需要大量的数据移动，个顺序堆栈共享空间，则可能需要大量的数据移动，造成时间的开销增大。而链式堆栈由于存储的不连续造成时间的开销增大。而链式堆栈由于存储的不连续性，一般不存在堆栈满的问题，所以一般不需要栈的性，一般不存在堆栈满的问题，所以一般不需要栈的共享。共享。3.1 3.1 栈栈3.1.5 栈的应用举例栈的应用举例（一）
10、表达式的转换（一）表达式的转换（二）递归（二）递归（三）汉内塔（三）汉内塔（hanoi）问题）问题（四）互递归（四）互递归 3.2 3.2 队列队列 3.2.1 队列定义及基本概念队列定义及基本概念 1、队列定义队的操作是在两端进行，其中一端只能进行插入，该端称为队列的队尾，而另一端只能进行删除，该端称为队列的队首。一般情况下，入队操作又称为队列的插入，出队操作又称为队列的删除。队列的运算规则是FIFO（First In First Out），或者叫做先进先出规则。队列的存储具有顺序和链式存储两种。队列在顺序存储时，经常出现“假溢出”现象，解决“假溢出”现象的方法有很多种，但通常采用循环队列方
11、式存储。队列的主要作用是：用于某种先后顺序处理的问题中，如：操作系统的作业调度、打印任务的调度等。3.2 3.2 队列队列3.2.1 队列定义及基本概念队列定义及基本概念2、队列的基本运算、队列的基本运算队列的基本运算通常和堆栈的基本运算类似，有队列的基本运算通常和堆栈的基本运算类似，有以下以下6种：种：置空队；置空队；/构造一个空队列。构造一个空队列。判对空；判对空；/队空返回真，否则返回假。队空返回真，否则返回假。判对满；判对满；/队满返回真，否则返回假，仅限于顺队满返回真，否则返回假，仅限于顺序存储结构。序存储结构。入队；入队；/队列非满时，从队尾插入元素。队列非满时，从队尾插入元素。出
12、队；出队；/队列非空时，从队首删除元素。队列非空时，从队首删除元素。取队首元素；取队首元素；/返回队首元素，不修改队首指针。返回队首元素，不修改队首指针。3.2 3.2 队列队列3.2.2 顺序队列顺序队列 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设置两个指针front和和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时可以置为0。入队时将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将fr
13、ont加1并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。3.2 3.2 队列队列3.2.2 顺序队列顺序队列 队列同堆栈一样也有上溢和下溢现象。此外队列中还存在“假溢出”现象。所谓“假溢出”是指在入队和出队操作中，头尾指针不断增加而不减小或只减小而不增加，致使被删除元素的空间无法重新利用，最后造成队列中有空闲空间，但是不能够插入元素，也不能够删除元素的现象。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针已超越向量空间的上界而不能进行入队或出队操作。该现象称为假上溢。解决假上溢现象的方法有
14、很多种，如固定队首指针，一旦删除元素，需要移动所有元素后，修改队尾指针，这样又可以插入元素了，只有在不能插入元素时，队列才满，否则可以一直插入元素，这种方法虽然能够解决“假溢出”，但需要造成大量的数据元素的移动；现在解决“假溢出”比较好的解决方案是使用循环向量，存储在循环向量中的队列称为循环队列（circular Quene）。3.2 3.2 队列队列3.2.2 顺序队列顺序队列 假设向量的空间是m，只要在入出队列时，将队首和队尾的指针对m做求模运算即可实现队首和队为指针的循环，即队首和队尾指针的取值范围是0到m-1之间。入队时：rear=（rear+1）%maxsize出队时：front=（
15、front+1）%mixsize但是入队和出队时front和rear的取值不能够确定队列的空和满。因为入队时，rear指针不断增加一个，当rear指针“追上”front指针时，此时队列已经满了，此时满的条件是rear=front；反之，当出队时，front指针不断增加一个，当front指针“追上”rear指针时，此时队列已经空了，此时队列空的条件是rear=front。由此可见队空和队满的条件是相同的，都是front=rear。3.2 3.2 队列队列3.2.2 顺序队列顺序队列 区分队空和队满的方法有多种。方法一：我们可以设置浪费一个空间单元，也就是假定rear指向的是刚刚插入元素的位置，f
16、ront指向刚刚删除元素的位置。也就是说在入队时，先不修改rear的值，而是先判断（rear+1）%maxsize=front，如果成立，表示队列已满（此时实际还有front指向的位置空闲），出队时，只要判断front=rear，如果成立表示队已空，否则只要front=（front+1）%maxsize直接删除元素即可。此种方法存储的数据元素个数是maxsize-1个，是利用浪费一个空间来换取队空与满的条件。方法二：设定一个变量来表示队列中的元素个数，利用该变量的值与队列的最大容量比较，如果该变量的值与最大容量相等，则表示队满，如果该变量的只为0，此时表示队列为空。此方法与第一种方法的不同之处
17、在于，每次入队、出队一个元素时，需要修改队列中的数据元素的个数。3.2 3.2 队列队列3.2.3 链式队列链式队列 定义链队列的存储结构基本和线性表的定义相同，不过需要在结构中指明的是队首和队尾的数据类型不再是整型而是指针类型。队列的各种运算比链式存储的普通线性表运算实现时要方便得多，主要原因是队列的各种运算只能在队列的两端操作，队列是特殊的线性表，我们只要考虑对线性表的两端操作的情况，并且只能一端插入（队首），另一端删除（队尾）；而线性表除此之外（不限定一端插入、一端删除），还需要考虑中间的结点的插入、删除、查询等操作，理解时，我们可以把队列的入出队运算当作线性表两端进行插入删除的特例即可
18、。3.2 3.2 队列队列3.2.3 链式队列链式队列 主要考虑队列的入队和出队算法。其原因是在队列的基本运算中有六种：判断队空、队列初始化、判断队列满（仅限于顺序存储的情况下），入队元素、出队元素、取队首元素等，而入队时需要操作的步骤是：初始化，然后判断队列是否为满，如果不满，则可以插入元素（入队）；出队时，需要考虑的操作步骤是：判断队列是否为空，如果不空，删除元素（出队），出队之前，保存队首元素。也就是说，队列的入出队运算包含了其他的六种基本运算，取队首元素的运算，只是不用修改队首的指针而已。3.2 3.2 队列队列3.2.3 链式队列链式队列 以单向循环队列为例，只要保留末尾结点指针（假
19、设是队尾指针），主要原因是如果保存队首和队尾指针，结构开销较大，原因是循环队列中，已知任意结点，可以找到所有结点，所以只要保留一个结点就可以了。如果已知结点的指针是头结点指针，此时入队出队运算的时间复杂度为O（n）（主要时间花费在查询结点上）；而如果已知结点的指针是末尾结点指针，此时不需要查询结点，直接进行入队和出队运算，时间复杂度O（1），各种运算实现也比较方便。在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。3.2 3.2 队列队列3.2.4 队列的应用队列的应用（一）合并两个队列（一）合并两个队列假设有两个队列，要求将两个队列合并到一起，合并时交替使用两个队列中的元素，并把剩余的队列中的元素添加在最后，将产生的新队列返回。（二）模拟客户服务系统（二）模拟客户服务系统