04《数据结构》第三节(上).pdf

数据结构 北京邮电大学信息安全中心 武斌 上章内容 上一章 （线性表）内容： 了解线性表的概念及其逻辑结构特性 理解顺序存储结构和链式存储结构的描述方法 掌握线性表的基本操作及算法实现 重点掌握线性链表的存储结构及算法实现 分析两种存储结构的时间和空间复杂度 2 本章课程学习目标 学习完本章课程，您应该能够： 掌握栈和队列这两种抽象数据类型的特点 熟练掌握栈类型的两种实现方法 理解递归算法执行过程中栈的状态变化过程 3 本章课程内容（第三章栈和队列） 3.1 栈 3.2 栈的应用举例 3.3 队列 3.4 队列应用举例 4 第三章栈和队列  栈和队列是在程序设计中被广泛使用的两种线性数据结构。  从数据结构角度看，栈和队列是操作受限的线性表。  从数据类型角度看，栈和队列是与线性表不同的两类重要的 抽象数据类型。  它们的特点在于基本操作的特殊性，栈必须按“后进先出” 的规则进行操作，而队列必须按“先进先出”的规则进行操 作。和线性表相比，它们的插入和删除操作受更多的约束和 限定，故又称为限定性的线性表结构。 5 第三章栈和队列  线性表与栈及队列的插入和删除操作对比如下：  插入 删 除 线性表：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) 队列只允许在表尾一端进行插入， 在表头一端进行删除 6 栈的类型定义 3.1 栈的类型定义 3.2 栈的应用举例 3.3 队列的类型定义 3.4 队列应用举例 7 栈的类型定义 栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表。在表 中，允许插入和删除的一端称作 “栈顶(top)”，不允许插入和删除的另 一端称作 “栈底(bottom)” 。当表中没有元素时称为空栈。 假设栈S=(a ，a ，a ，…a )，则a 称为栈底元素，a 为栈顶元素。 1 2