10数据结构-第3章-栈和队列.pdf

第三章 栈和队列 第一章 绪论 第二章 线性表 目录 第三章 栈和队列 第四章 串 第五章 数组和广义表 1、栈的定义 2. 栈的应用 3.队列的定义及应用 课前思考 1. 什么是线性结构？ 简单地说，线性结构是一个数据元素的序列 2. 餐馆中盘子如果它们是按1,2,…,n 的次序往上叠 的，那么使用时候的次序应是什么样的？ 从上往下的次序，即n,…,2,1。“后进先出”：栈 3. 在日常生活中，为了维持正常的社会秩序而出 现的常见现象是什么？ 是排队。程序中模拟排队的数据结构是队列。 知识要点： • 栈和队列是两种重要的线性结构。 • 从数据结构的角度看，栈和队列也是线性 表，其特殊性在于栈和队列的基本操作是线 性表操作的子集 ，即它们是操作受限的线性 表。 • 从数据类型的角度看，它们是和线性表大不 相同的两类重要的抽象数据类型，广泛应用 在各种软件系统中。 限定性的线性表结构 插入 删除 插入 删除 线性表 Insert(L,i,x) Delete(L,i,x) 线性表 (1≤i≤n+1) (1≤i≤n) 栈 栈 Insert(L,n+1,x) Delete(L,n,x) 队列 队列 Insert(L,n+1,x) Delete(L,1,x) 3.1 栈的定义 3.1 栈的定义 栈的类型定义 a b c 栈顶元素 栈顶元素 栈顶top 栈底bottom 栈底元素 栈底元素 思考 • 若数据:1，2，3，4依次进栈，则出栈顺 序？ • 关于铁路调度图： –若进栈车厢的序列为123456，能否得到435 612和135426的出站车厢序列? –若进栈车厢的序列为123，则可能得到的出 站车厢序列是什么？ 栈是先进后出的数据结构 栈是后进先出的数据结构 思考：栈的基本操作 • 初始化 • 销毁 • 求栈长 • 判栈空 • 遍历栈 • 插入 入栈 • 删除 出栈（弹栈） 2. 栈的抽