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

《数据结构课件 栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章栈和队列第三章栈和队列本章学习两种特殊的线性数据结构，它们特殊在定义的操作不同，即插入和删除操作只能在线性表的两端进行。只能在一端进行的-----栈分别在两端进行的-----队列重点本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。知识点顺序栈、链栈、循环队列、链队列１.你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n的次序往上叠的，那么使用时候的次序应是什么样的？２.在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？栈和队列是在程序设计中被广泛使用的两种线性数据结构．栈必须按“后进先出”的规则进行操作，而队列必须按“先进先出”的规则进行操

2、作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。插入　　　　　删除线性表：Insert(L,i,x)Delete(L,i)(1≤i≤n+1)(1≤i≤n)栈：Insert(L,n+1,x)Delete(L,n)队列：Insert(L,n+1,x)Delete(L,1)第三章栈和队列3.1栈1、栈（stack)：是一种特殊的线性表（数据元素之间的关系是线性关系），其插入、删除只能在表的一端进行，另一端固定不动。栈顶（top)：插入、删除的一端；栈底（bottom)：固定不动的一端；入栈（push)：又称压入，即插入一个元素；出栈（pop)：又称

3、弹出，即删除一个元素；一、抽象数据类型栈的定义2、说明：设（a1,a2,a3,…,an）是一个栈（a1,a2,...,ai-1,ai,ai+1,…,an）栈底栈顶进栈出栈1）表尾称为栈顶，表头称为栈底，即a1为栈底元素，an为栈顶元素;2）在表尾插入元素的操作称进栈操作，在表头删除元素的操作称为出栈操作;3）元素按a1,a2,a3,…,an的次序进栈,第一个进栈的元素一定在栈底，最后一个进栈的元素一定在栈顶,第一个出栈的元素为栈顶元素；栈的示意图栈特点：由于限制了插入删除只能在一端进行，那么元素的操作顺序有“先进后出”或“后进先出”的特点(LastInFirstout-LIFOFirs

4、tInLastout---FILO)第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素课堂练习假设有A，B,C,D四个元素；它们入栈次序为A一＞B一＞C一＞D出栈次序任意，请问不可能得到下面哪些出栈序列？(1)ABCD(2)DBCA(3)CDBA(4)CBAD(5)ACBD(6)DBAC(7)ADCB(8)CABD3、栈的基本操作1） 初始化操作InitStack(&S)功能：构造一个空栈S；2）销毁栈操作DestroyStack(&S)功能：销毁一个已存在的栈;3）置空栈操作ClearStack(&S)功能：将栈S置为空栈;4）

5、判空栈操作StackEmpty(S)功能：若栈为空栈，返回TRUE，否则FALSE5）取长度操作StackLength(S)功能：返回栈S的元素个数6）取栈顶元素操作GetTop(S,&e)功能：取栈顶元素，并用e返回;7）进栈操作Push(&S,e)功能：元素e进栈;8）退栈操作Pop(&S,&e)功能：栈顶元素退栈，并用e返回;7）栈遍历StackTraverse(S)功能：从栈底到栈顶依次调用函数visit().4、栈的ADT描述栈的抽象数据类型定义为：ADTStack{数据对象：D＝{ai

6、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{

7、>

8、ai-1,ai∈D,i=2,...,n}约定an端为栈顶,a1端为栈底。基本操作：…….}ADTStack二栈的存储表示和操作的实现和线性表类似，栈也有两种存储表示，其顺序存储结构简称为顺序栈。和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间。顺序存储方式：同一般线性表的顺序存储结构完全相同。是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素，栈顶元素的位置由一个称为栈顶指针的变量指示。实际是栈中元素的个数顺序栈类型的定义//结构定义：typedefstruct{ElemType*base;//存储空间基址inttop;//栈顶指针intstacksize

9、;//允许的最大存储空间}Stack;栈顶指针总是指在栈顶元素的后面一个位置上top=0123450栈空top123450进栈Atop出栈栈满BCDEF设数组维数为stacksizetop=0,栈空，此时出栈，则下溢（underflow)top=stacksize,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptop特点：简单、方便，但易产生溢出。上溢（Overflow)栈已经满，又要压入