[工学]数据结构第五次课-栈和队列A.ppt

上堂课内容回顾 上节课的课后提问：顺序表和链表分别在什么情况下应用比较好？ 第三章 栈和队列 3.1 栈（Stack） 1. 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈 问：堆栈逻辑结构是什么？它与上章学习的一般线性表有什么不同？ 2. 栈的逻辑结构 3. 栈的存储结构 3.1 顺序栈 实现：一维数组s[M] 多个栈共享空间 补充：表和栈的操作区别—对线性表 s= (a1 , a2 , …. , an-1 , an ) 3.2 链栈 例1：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？ 43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，只需压入一个立即弹出一个即可。 12534的顺序可以实现么？ 例2：华工计算机系2001年考研题（程序设计基础） 设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是： （隐含条件） Ａ）a，b，c，d Ｂ）c，d，a，b Ｃ）b，c，d，a Ｄ）a，c，d，b 例3 一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？ 例1：回文游戏 设计思路：用栈暂存回文 例2：数制转换（十转N） 设计思路：用栈暂存低位值 例3 ：括号匹配的检验 设计思路：用栈暂存左括号 例4：表达式求值 设计思路：用栈暂存运算符 * 电气信息学院 计算机系 刘勇 数据结构 小蜗牛问妈妈：为什么我们从生下来，就要背负这个又硬又重的壳呢？ 妈妈：因为我们的身体没有骨骼的支撑，只能爬，又爬不快。所以要这个壳的保护！小蜗牛：毛虫姊姊没有骨头，也爬不快，为什么她却不用背这个又硬又重的壳呢？ 妈妈：因为毛虫姊姊能变成蝴蝶，天空会保护她啊。小蜗牛：可是蚯蚓弟弟也没骨头爬不快，也不会变成蝴蝶他什么不背这个又硬又重的壳呢？妈妈：因为蚯蚓弟弟会钻土, 大地会保护他啊。 小蜗牛哭了起来：我们好可怜，天空不保护，大地也不保护。蜗牛妈妈安慰他：「所以我们有壳啊！」我们不靠天，也不靠地，我们靠自己。 每课一贴 1. 线性表 逻辑结构：“一对一” 或 1:1 存储结构：顺序、链式 运 算 ：修改、插入、删除 3.链式存储 特征：逻辑上相邻，物理上不一定相邻； 优点：插入删除效率高 O(1) 缺点：查找慢 O(n)，空间利用效率低 2.顺序存储 特征：逻辑上相邻，物理上也相邻； 优点：随机查找快O(1),存储紧凑 缺点：插入、删除慢 O(n) 顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找时，则采用顺序表较好； 若线性表的长度变化较大，且其主要操作是插入、删除操作时，则采用链表较好。 答： 数据结构课程的内容 问题：已知共有n个饼并按照做出的顺序依次编号，排队等的m个人按照先后顺序编号，问第x个人买到的饼编号是什么？ 栈和队列是两种特殊的线性表，是操作受限的线性表。 线性结构 线性结构 先做的后卖，后做的先卖 先来的先买 只能从上面拿 一端进一端出 FIFO先进先出 两端操作受限 队 煎饼 排队的人 LIFO 先进后出 一端操作 栈 栈的基本理论 定义、逻辑结构、存储结构、基本运算规则、栈的应用 2. 基本操作的程序实现方法 栈的概念引入 1 2 3 4 “堆” 一. 栈的基本理论 栈底 栈顶 出栈 进栈 ... an a1 a2 ……... 栈s=(a1,a2,……,an) 特点：先进后出（FILO）或后进先出（LIFO） 答：堆栈是一种特殊的线性表,逻辑结构仍然是线性结构，它只能在表的一端（即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。 一般线性表 堆栈 逻辑结构：一对一