(Java版)数据结构与算法第3章

《(Java版)数据结构与算法第3章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章栈和队列第3章栈和队列堆栈和队列是两种特殊的线性表。堆栈的主要特点是只能在栈顶操作，也就是遵循先进后出的运算规则。队列的主要的特点是只能在一端插入，另一端删除的一种线性表，也就是遵循先进先出的运算规则。3.1栈3.1.1栈定义及基本概念栈（Stack）又称堆栈，是限制在表的一端进行插入和删除运算的线性表。通常称能够进行插入、删除运算的这一端为栈顶（Top），另一端称为栈底（Bottom）。当表中没有元素时称为空栈。习惯上将每次删除（也称为退栈）操作又称为弹出（POP）操作。删除的元素总是当前栈中“最新”的元素

2、（栈顶元素）。每次插入（称为进栈）操作称为压入（PUSH）操作，压入的元素总是当前栈中“最新”的元素。3.1栈3.1.1栈定义及基本概念在空栈中最先插入的元素总被放在栈的底部，只有所有元素被弹出之后它才能被删除。当栈满时进栈运算称为“上溢”；当栈空时退栈运算称为“下溢”。堆栈的存储结构有顺序存储结构和链式存储结构两种，在顺序存储结构下，可以考虑堆栈的上溢，而在链式存储结构下，不必考虑对杂货内的上溢现象，只需要考虑堆栈的下溢现象。3.1栈3.1.1栈定义及基本概念堆栈上溢是一种出错状态，应该设法避免之；而下溢则可能是

3、正常现象，通常下溢用来作为程序控制转移的条件。堆栈的运算规则是按后进先出的原则进行的（又称为后进先出），简称为LIFO（lastinfirstout）表。就线性表而言，实现栈的方法有很多，我们着重介绍顺序栈（arrary-basedstack）和链式（linkedstack）栈，它们类似于顺序表和链式表。3.1栈3.1.1栈定义及基本概念栈的基本运算一般有以下几种：①InitStack（S）构造一个空栈S。②StackEmpty（S）判栈空，若S为空栈返回TRUE，否则返回FALSE。③StackFull（S）判栈

4、满，若S为满栈，则返回TRUE，否则返回FALSE。该运算只适用于栈的顺序存储结构。④Push（S，x）进栈。若栈S不满，则将元素x压入S的栈顶。⑤Pop（S）退栈。若栈S非空，则将S的栈顶元素弹出，并返回该元素。⑥StackTop（S）取堆栈的栈顶元素，不修改栈顶指针。比较重要的运算就是入栈和出栈两种。3.1栈3.1.2顺序栈顺序栈的实现从本质上讲，就是顺序线性表实现的简化。惟一重要的是需要确定应该用数组的哪一端表示栈顶。一种选择是把数组的第0个位置作为栈顶。根据线性表的函数，所有的插入(insert)和删除(r

5、emove)操作都在第0个位置的元素上进行。由于这时每次push(insert)或者pop(remove)操作都需要把当前栈中的所有元素在数组中移动一个位置，因此效率不高。如果栈中有n个元素，则时间代价为O(n)。另一种选择是当栈中有n个元素时把位置n-1作栈顶。也就是说，当向栈中压人元素时，把它们添加到线性表的表尾，成员函数pop也是删除表尾元素。在这种情况下，每次push或者pop操作的时间代价仅为O(1)。3.1栈3.1.2顺序栈堆栈的运算主要考虑堆栈的入栈和出栈算法。其原因是在堆栈的基本运算中有六种：判断堆

6、栈空、堆栈初始化、判断堆栈满（仅限于顺序存储的情况下），入栈元素、出栈元素、取栈顶元素等，而入栈时需要考虑的操作步骤是：堆栈初始化，然后判断堆栈是否为满，如果不满，则可以插入元素（入栈）；出栈时，需要考虑的步骤是：判断堆栈是否为空，如果不空，删除元素（出栈），出栈之前，保存栈顶元素。也就是说，堆栈的入出栈运算包含了其他的六种基本运算，取栈顶元素的运算，只是不用修改栈顶的指针而已。3.1栈3.1.3链式栈堆栈的链式存储，称为链栈（单向链表存储堆栈）。链式栈的基本运算同顺序栈，定义也同线性表的链表定义，它是对链表实现的

7、简单化（因为它只是对链表的头部操作）。它的元素只能在表头进行插入和删除。在链式存储结构中，不需要给出表头结点，因为其中惟一的已知条件是栈顶指针top，它是指向链式栈的第一个结点（相当于头结点）。堆栈的各种运算比链式存储的普通线性表运算实现时要方便得多，主要原因是堆栈的各种运算只能在堆栈的一端操作，堆栈是特殊的线性表，我们只要考虑对线性表的一端操作的情况，并且只能在一端插入删除（栈顶）；而线性表除此之外（不限定一端插入删除），还需要考虑另外一端结点以及中间的结点的插入、删除、查询等操作，理解时，我们可以把堆栈的入出堆

8、栈运算当作线性表的一端进行插入删除的特例即可。注意：堆栈的运算一定遵循“先进后出”的运算规则。3.1栈3.1.4顺序栈和链式栈的比较实现链式栈和顺序栈的操作，都是需要常数时间，即时间复杂度为O（1）。主要两者从空间和时间两个方面考虑：初始时，顺序堆栈必须说明一个固定的长度，当堆栈不够满时，造成一些空间的浪费，而链式堆栈的长度可变则是长度不需要预先设定，相对比