02-1 第2章 堆栈和队列.pptx

第1页：第二章线性表目录封面

第二章线性表、堆栈和队列2.1线性表的定义和基本操作2.2线性表的顺序存储结构2.3线性表的链接存储结构2.4复杂性分析2.5堆栈2.6队列

第2页：本节内容目录

22.5堆栈2.5.1堆栈的定义和主要操作2.5.2顺序栈2.5.3链式栈2.5.4顺序栈与链式栈的比较2.5.5堆栈的应用

第3页：堆栈的定义

31、堆栈的定义栈的定义：是一种操作受限的线性表，只允许在表的同一端进行插入和删除操作，且这些操作是按后进先出的原则进行的。栈顶：进行插入、删除的一端；栈底：另一端；空栈：栈中无元素时。a5a3a2a1a4进栈出栈栈顶栈底[例]线性表(a1,a2,…,a5)，进栈出栈情况

第4页：堆栈的定义（图）

a1a2a1a3a2a1a3a2a1a4a5a3a2a1a4a1a2a1a3a2a1a3a2a1a4a5a3a2a1a

第5页：栈的后进先出性

5●栈的后进先出性：可以对输入序列部分或全局求逆；凡符合后进先出性，都可应用栈，如制数转换问题、递归的实现、算数表达式求值等问题。●栈的封闭性：除了栈顶元素外，其他元素不会被改变。因而，栈的封闭性非常好，使用起来非常安全。

第6页：堆栈的基本操作

62、堆栈的基本操作（1）栈初始化（2）进栈Push（3）出栈Pop（4）读取栈顶元素Peek（5）判栈空StackEmpty（6）判栈满StackFull（7）置空栈

第7页：本节内容目录

72.5堆栈2.5.1堆栈的定义和主要操作2.5.2顺序栈2.5.3链式栈2.5.4顺序栈与链式栈的比较2.5.5堆栈的应用

第8页：堆栈的顺序存储使用数组

堆栈的顺序存储使用数组存放栈元素，栈的规模必须小于或等于数组的规模，当栈的规模等于数组的规模时，就不能再向栈中插入元素。存放堆栈元素的数组：T stackArray [MaxStackSize];栈顶所在数组元素的下标：int top;堆栈空：top =-1堆栈满：top = MaxStackSize-1

第9页：栈内变化情况

top1230-1top1230ACBtop1230ABtop1230Atop1230-1栈内变化情况

第10页：顺序栈

顺序栈AStack的类定义template < class T >class AStack {private:int size ;//数组的规模T * stackArray ;//存放堆栈元素的数组int top ;//栈顶所在数组元素的下标public:AStack( int MaxStackSize )//构造函数{ size = MaxStackSize ;stackArray = new T [MaxStackSize] ; top =-1 ; }~AStack( ) { delete [ ] stackArray ; }

第11页：向栈顶压入一个元素

boolPush( const T& item ) ;

第12页：算法Push

算法Push(A, item)

第13页：堆栈变化情况

top1230-1top1230ABtop1230A堆栈变化情况top1230ACB

第14页：算法Pop

算法Pop(A. item) P1. [栈空?]IF top=-1 THEN (PRINT“栈空无法弹出”. RETURN.)P2. [出栈]item←A[top].

第15页：堆栈变化情况（续2）

top1230ACBtop1230ABtop1230-1top1230A堆栈变化情况

第16页：算法Peek

算法Peek(A. item)

第17页：本节内容目录

172.5堆栈2.5.1堆栈的定义和主要操作2.5.2顺序栈2.5.3链式栈2.5.4顺序栈与链式栈的比较2.5.5堆栈的应用

第18页：182.5.3 堆栈的链式

182.5.3堆栈的链式存储用单链表实现堆栈要为每个栈元素分配一个额外的指针空间。考虑栈顶对应链表的表头还是表尾。因为堆栈主要操作（插入、删除、存取）的对象是栈顶元素，若栈顶对应表尾，则每次操作的时间复杂性为O(n)；若栈顶对应表头，则每个操作的时间复杂性是O(1)，显然，栈顶对应表头是合理的。链式栈中不需要哨位结点。

第19页：链式栈

链式栈LStack的类定义template < class T >class LStack{private :SLNode <T> * top ;//栈顶指针指向表头public :LStack ( ) { top = NULL ; }

第20页：向栈顶压入一个元素（续2）

boolPush( const T& item ) ;

第21页：算法Push（续2）

算法Push(item)//向栈顶指针为top的链式栈中压入一个元素itemP1. [创建新结点]s←AVAIL.

第22页：算法Pop（续2）

算法Pop( item) P1. [栈空？]IF top= NULL THEN (PRINT“栈空无法弹出”. RETURN.)P2. [出栈]item←data(top).//保存栈顶结点的字段值q←next(top).//令指针q指向次栈顶结点AVAIL←top.//释放栈顶结点的空间top←q.//更新栈顶指针，令其指向q所指结点▐

第23页：算法Peek（续2）

算法Peek(item) P1. [栈空？]IF top=NULL THEN (PRINT“栈空”. RETURN.)P2. [存取栈顶]item←data(top).

第24页：算法Clear

算法Clear( )

第25页：本节内容目录

252.5堆栈2.5.1堆栈的定义和主要操作2.5.2顺序栈2.5.3链式栈2.5.4顺序栈与链式栈的比较2.5.5堆栈的应用

第26页：顺序栈与链式栈的比较在空间复杂性上

顺序栈与链式栈的比较在空间复杂性上，顺序栈必须初始就申请固定的空间，当栈不满时，必然造成空间的浪费；链式栈所需空间是根据需要随时申请的，其代价是为每个元素提供空间以存储其next指针域。在时间复杂性上，对于针对栈顶的基本操作（压入、弹出和栈顶元素存取），顺序栈和链式栈的时间复杂性均为O(1).

第27页：本节内容目录

272.5堆栈2.5.1堆栈的定义和主要操作2.5.2顺序栈2.5.3链式栈2.5.4顺序栈与链式栈的比较2.5.5堆栈的应用

第28页：堆栈的应用

堆栈的应用——括号匹配高级语言程序设计中的各种括号应该匹配，例如：“(”与“)”匹配、“[”与“]”匹配、“{”与“}”匹配等。字符串{a=(b*c}+free()]中的括号就没有匹配上，因为串中第一个关括号“}”和最近的未匹配开括号“(”不匹配。

第29页：这里给出一个简单程序

这里给出一个简单程序，检查一个输入的文本文件中的括号是否正确匹配。文本文件的字符按次序依次输入，如果输入的字符是开括号，将其存放起来，继续下一字符的输入；如果输入的是关括号，应该考察其与最近未匹配的开括号是否匹配，若匹配，则将匹配的开括号从存放处删除，继续考察下一字符，若不匹配，说明整个文件中的括号没有匹配上。

也就是说，每次用来和关括号进行匹配的开括号都是最后输入的，这符合堆栈的后进先出特性，因此用堆栈来存放开括号。

第30页：括号的匹配检测

括号的匹配检测：void main ( ) {LStack<char> bracket ;

第31页：堆栈中仍有开括号

charopen_bracket;bracket.pop(open_bracket);if(!(open_bracket==‘(’&&read_in==‘)’)||(open_bracket==‘[’&&read_in==‘]’)||(open_bracket==‘{’&&read_in==‘}’)){cout<<“Badmatch”<<read_in<<open_bracket<<endl;return;}read_in=cin.get();}//若堆栈中仍有开括号，说明匹配失败，因为已无关括号与之匹配if(!bracket.IsEmpty())cout<<“Unmatchedopeningbracketdetected.”<<endl;return;}

第32页：堆栈的应用（续2）

堆栈的应用——数制转换例：十进制数转换成八进制数：(66)10=(102)866/8=8余28/8=1余01/8=0余1结果为余数的逆序:102。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的后进先出的性质，故可用栈来实现数制转换。

第33页：十进制数x转换

十进制数x转换为r进制数y1.十进制数x除以r，所得余数是r进制数y的最低位y0，放入堆栈；2.用x除以r的整数商，除以r，所得余数是y的次低位y1，放入堆栈；3.依此类推；4.直到商为0，所得余数是y的最高位ym，放入堆栈；此时，栈中有m+1个r进制数，将其依次弹出，即为所得。

第34页：第二章线性表目录

第二章线性表、堆栈和队列2.1线性表的定义和基本操作2.2线性表的顺序存储结构2.3线性表的链接存储结构2.4复杂性分析2.5堆栈2.6队列

第35页：本节内容目录

352.6队列2.6.1队列的定义和主要操作2.6.2顺序队列2.6.3链式队列2.6.4顺序队列与链式队列的比较2.6.5队列与堆栈的扩展

第36页：队列的定义

361、队列的定义队列的定义：是一个操作受限的线性表，对于它的所有插入都在表的一端进行，所有的删除（以至几乎所有的存取）都在表的另一端进行，且这些操作又都是按着先进先出（FIFO）的原则进行的。能进行删除的一端称为队头（front）；能进行插入的一端称为队尾（rear）；没有元素的队列称为空队列。a1a2a3a4a5队尾队头入队出队

第37页：队列的先进先出性

37●队列的先进先出性：可以对输入序列起缓冲作用；凡符合先进先出性，都可应用队列，如操作系统中作业调度、树的层次遍历、图的广度优先搜索等问题。●队列的封闭性：和栈类似，队列的封闭性也非常好，使用起来非常安全。

第38页：队列的基本操作

382、队列的基本操作(1）队列初始化（2）入队(插入）（3）出队（删除）（4）读取队首元素（5）判断队列是否空（6）确定队列中元素个数（7）置空队列

第39页：本节内容目录

392.6队列2.6.1队列的定义和主要操作2.6.2顺序队列2.6.3链式队列2.6.4顺序队列与链式队列的比较2.6.5队列与堆栈的扩展

第40页：队列的顺序存储

队列的顺序存储●存放队列元素的数组：T qlist[MaxQSize]front队首元素的数组下标rear (要入队元素的下标)队尾元素的下标加1……a1a2a3frontrear

第41页：等待处理某作业进队

41[例]等待处理某作业进队、出队情况。front=0rear=1……a0012MaxQsize-1a0进队……012MaxQsize-1front=0rear=0初始状态插入：rear=rear+1

第42页：进队

front=0……a0a1a2012MaxQsize-1a1a2进队rear=3front=1……a1a2012MaxQsize-1a0出队rear=3●删除队首元素的方法1：令front=front+1

第43页：出队

front=3……012MaxQsize-1a1a2出队rear=3012MaxQsize-1rear=nfront=n-3……an-3an-2无法利用的空间x

第44页：删除队首元素方法

44●删除队首元素方法2:元素向前移动，front总等于0……a2012MaxQsize-1a0出队front=0rear=2a1front=0……an-3an-2012MaxQsize-1rear=3x

第45页：删除队首元素的方法

45012front=n-3……an-3an-2MaxQsize-1rear=n-1●删除队首元素的方法3：循环队列删除时front顺时针移动一位rear=n-1front=n-2……an-2012MaxQsize-1

第46页：删除队首元素的方法（续2）

46012front=n-3……an-3an-2MaxQsize-1rear=n-1●删除队首元素的方法3：循环队列插入元素x：front=n-3……an-3an-2012MaxQsize-1rear=0xrear顺时针移动一位

第47页：循环队列

front=n-3……an-3an-2012MaxQsize-1rear=n-1●循环队列：很好的解决了(1)(2)中存在的问题。n-3rear= n-1an-3an-20.1...front=n-3n-2

第48页：插入元素

插入元素x：front=n-3……an-3an-2012MaxQsize-1rear=0xn-3an-3rear=0an-20.1n-1...front=n-3n-2xrear顺时针移动一位rear = (rear+1) MOD MaxQSize

第49页：删除队首元素

删除队首元素：front顺时针移动一位front = (front+1) MOD MaxQSize;rear0front=9.1...CD删除Crearfront=00.1...D

第50页：采用环状模型来实现队列

采用环状模型来实现队列，各数据成员的意义如下：front指定队首位置，删除一个元素就将front顺时针移动一位；rear指向元素要插入的位置，插入一个元素就将rear顺时针移动一位；count存放队列中元素的个数，当count等于MaxQSize时，不可再向队列中插入元素。队空：count=0队满：count=MaxQSize

第51页：顺序队列类

顺序队列类AQueue的类声明template < class T >class AQueue{private:int front ;//队首所在数组元素下标int rear ;//新元素要插入的位置（下标）int count ;//队列中元素个数T *QArray ;//存放队列元素的数组int Size ;//存放队列的数组规模public:AQueue( int MaxQueueSize = 10 )

第52页：向队尾插入元素

boolQInsert( const T& item )//向队尾插入元素itemboolQDelete( T & item ) ;

第53页：算法QInsert

算法QInsert(A, item)

第54页：算法QDelete

算法QDelete(A. item)//删除队列A的队首元素，并将其元素值赋给变量itemQD1. [队列空？]IF count=0 THEN (PRINT “队列空无法删除”. RETURN. )QD2. [出队]item←A[front].

第55页：算法QFront

算法QFront(A. item)//读取队列A的队首元素值，并将其赋给变量itemQF1. [队列空？]IF count=0 THEN (PRINT “队列空无法读取”.RETURN. )QF2. [存取]item←A[front].

第56页：创建一个队列

566543210a6543210FR(a)创建一个队列FR(b)插入元素a队列运行示意图

第57页：插入元素（续2）

cba65432106543210FR(c)插入元素b、cFR(d)取出元素a、b、c

第58页：插入元素（续2）

gfedih6543210gfedjih6543210RF(e)插入元素d、e、f、g、h、iFR(f)插入元素j

第59页：删除所有元素

596543210FR(g)删除所有元素

第60页：本节内容目录

602.6队列2.6.1队列的定义和主要操作2.6.2顺序队列2.6.3链式队列2.6.4顺序队列与链式队列的比较2.6.5队列与堆栈的扩展

第61页：队列的链接存储链式队列

队列的链接存储链式队列的结构：（a1,a2,… ,an)ana1a2∧frontrear…

第62页：链式队列

链式队列LQueue的类声明template < class T >classLQueue{private:SLNode <T> * front, * rear ;

第63页：算法QInsert（续2）

算法QInsert(item)

第64页：算法QDelete（续2）

算法QDelete(item)

第65页：算法QFront（续2）

算法QFront(item)//读取队首元素值，并将其赋给变量itemQF1. [队列空？]IF front=NULL THEN (PRINT “队列空无法读取”.RETURN. )QF2. [存取]item←data(front).

第66页：本节内容目录

662.6队列2.6.1队列的定义和主要操作2.6.2顺序队列2.6.3链式队列2.6.4顺序队列与链式队列的比较2.6.5队列与堆栈的扩展

第67页：顺序队列与链式队列的比较在空间复杂性上

顺序队列与链式队列的比较在空间复杂性上，顺序队列必须初始就申请固定的空间，当队列不满时，必然造成空间的浪费；链式队列所需空间是根据需要随时申请的，其代价是为每个元素提供空间以存储其next指针域。在时间复杂性上，对于队列的基本操作（入队、出队和存取），顺序队列和链式队列的时间复杂性均为O(1).

第68页：顺序队列

顺序队列与链式队列的比较顺序队列有固定的存储空间，不适于浪涌大小无法估计的情况，而且当浪涌很大时，顺序队列的空间效率低下，但链式队列却可满足这些应用环境。对于那些大致能预测浪涌统计特性的应用环境，可估计缓冲队列长度，为顺序队列选择比较恰当的存储空间。

第69页：本节内容目录

692.6队列2.6.1队列的定义和主要操作2.6.2顺序队列2.6.3链式队列2.6.4顺序队列与链式队列的比较2.6.5队列与堆栈的扩展

第70页：队列与堆栈

队列与堆栈的扩展基于栈和队列还可设计一些变种的栈或队列，虽然它们的应用不够广泛，但在一些特定场合却很有应用价值。——双端队列插入和删除都可在且只能在线性表的两端进行.它好像一个特别的书架，只能从左右两边的端点取书和存书。——双栈两个底部相连的栈。——超队列是一种被限制的双端队列，删除操作限制在一端进行，而插入操作允许在两端进行。

——超栈是一种插入受限的双端队列，即插入限制在一端而删除仍允许在两端进行。当栈溢出时，它允许将栈中保存最久的底部元素删除。

第71页：栈的输入序列

例：设栈的输入序列是（1，2，3，4），则( )不可能是其出栈序列。A. 1243B. 2134C. 1432D. 4312DD. 4312练习

第72页：课后作业

课后作业49页2-149页2-850页2-17