数据结构-栈和队列.ppt

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

1、3栈和队列信息学院暑期培训栈和队列学习目标掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。熟练掌握循环队列和链队列的基本操作实现算法。理解递归算法执行过程中栈的状态变化过程。重点和难点栈和队列是在程序设计中被广泛使用的两种线性数据结构，本章的学习重点是掌握这两种结构的特点，以便能在应用问题中正确使用。知识点顺序栈、链栈、循环队列、链队列栈和队列栈和队列是在程序设计中被广泛使用的两种线性数据结构。与线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。线性表允许在表内任一位置进行插入和删除；栈只允许在表尾一端进行插入和删除；队列只允许在

2、表尾一端进行插入，在表头一端进行删除。3栈和队列栈在计算机的实现有多种方式：◆硬堆栈：利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限，但速度很快；◆软堆栈：这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上，又有动态方式和静态方式两种。本章将讨论栈和队列的基本概念、存储结构、基本操作以及这些操作的具体实现。3.1栈1栈的概念栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO(LastInFirstOut)或先进后出FILO(FirstInLastOut)线性表。栈顶(Top)：允许进行插入、删除操作的一端，

3、又称为表尾。用栈顶指针(top)来指示栈顶元素。栈底(Bottom)：是固定端，又称为表头。空栈：当表中没有元素时称为空栈。3.1.1栈的基本概念3.1.1栈的基本概念设栈S=(a1，a2，…an)，则a1称为栈底元素，an为栈顶元素，如图3-1所示。栈中元素按a1，a2，…an的次序进栈，退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。图3-1顺序栈示意图a1a2aian⋯⋯⋯⋯bottomtop进栈（push）出栈(pop)栈的示意图特点先进后出（FILO）后进先出（LIFO）a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈顶栈的逻辑结构例

4、：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶c栈顶情况1：栈的逻辑结构栈底栈顶ab栈顶c栈顶出栈序列：c出栈序列：c、b出栈序列：c、b、a例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？情况1：栈的逻辑结构栈底栈顶ab栈顶出栈序列：b情况2：例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构栈底a出栈序列：b出栈序列：b、c出栈序列：b、c、ac栈顶栈顶注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除

5、操作进行的时间。例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？情况2：还有其他情况吗？3.1.1栈的基本概念2栈的抽象数据类型定义ADTStack{数据对象：D={ai

6、ai∈ElemSet,i=1,2,…,n，n≥0}数据关系：R={

7、ai-1，ai∈D,i=2,3,…,n}基本操作：初始化、进栈、出栈、取栈顶元素等}ADTStack栈的抽象数据类型定义ADTStack{数据对象：D＝{ai

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

9、ai-1,ai∈D,i=2,...,

10、n}基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。栈的抽象数据类型定义ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S中元素个数，即栈的长度。栈的抽象数据类型定义GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。

11、操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。栈的抽象数据类型定义StackTraverse(S,visit())初始条件：栈S已存在且非空，visit()为元素的访问函数。操作结果：从栈底到栈顶依次对S的每个元素调用函数visit()，一旦visit()失败，则操作失败。}ADTStack3.1.2栈的顺序存储表示栈的顺序存储结构简称为顺序栈，和线性表相类