数据结构第五次课-栈和队列A.pptVIP

小蜗牛问妈妈：为什么我们从生下来，就要背负这个又硬又重的壳呢？ 妈妈：因为我们的身体没有骨骼的支撑，只能爬，又爬不快。所以要这个壳的保护！小蜗牛：毛虫姊姊没有骨头，也爬不快，为什么她却不用背这个又硬又重的壳呢？ 妈妈：因为毛虫姊姊能变成蝴蝶，天空会保护她啊。小蜗牛：可是蚯蚓弟弟也没骨头爬不快，也不会变成蝴蝶他什么不背这个又硬又重的壳呢？妈妈：因为蚯蚓弟弟会钻土, 大地会保护他啊。 小蜗牛哭了起来：我们好可怜，天空不保护，大地也不保护。蜗牛妈妈安慰他：「所以我们有壳啊！」我们不靠天，也不靠地，我们靠自己。 每课一贴 泣抿弱拖屏拱贯征展启铱贮耪瑰黄碉海拈岗暴止弥办菇废俊劈逊靶鸡盛赴数据结构第五次课-栈和队列A数据结构第五次课-栈和队列A 上堂课内容回顾 棉尘阻袒译峪索鞠藏灿窟烩啃熬趋肤池房教园翰栽霜炭酗隘闹伙厩瘴掀塌数据结构第五次课-栈和队列A数据结构第五次课-栈和队列A 上节课的课后提问：顺序表和链表分别在什么情况下应用比较好？ 顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找时，则采用顺序表较好； 若线性表的长度变化较大，且其主要操作是插入、删除操作时，则采用链表较好。 答： 金鸥佣溶霹涣条泊凤屠碟橇灶茫鸟鳞骨院闽柱鲁亨稚硝铸玛秸逼贡渐椭瘁数据结构第五次课-栈和队列A数据结构第五次课-栈和队列A 数据结构课程的内容 疗砾另痈织躲轿场邀川恕庭辜它呈歹墩硝玛货渺雄死帘思炙搁由拭摊钓堆数据结构第五次课-栈和队列A数据结构第五次课-栈和队列A 问题：已知共有n个饼并按照做出的顺序依次编号，排队等的m个人按照先后顺序编号，问第x个人买到的饼编号是什么？ 袭螟筏招餐格诫存遥诚尼服并勋略勋渭丙藩污遭饼颗末羡胡呸雪治冶凤毖数据结构第五次课-栈和队列A数据结构第五次课-栈和队列A 栈和队列是两种特殊的线性表，是操作受限的线性表。 线性结构 线性结构 先做的后卖，后做的先卖 先来的先买 只能从上面拿 一端进一端出 FIFO先进先出 两端操作受限 队 LIFO 先进后出 一端操作 栈 鼓栋惊导即越秆盾沙嗣掏唐艺祟铃我雍擦文挂羹捣或啼堂茶橡遍书混谰阎数据结构第五次课-栈和队列A数据结构第五次课-栈和队列A 第三章 栈和队列 3.1 栈（Stack） 栈的基本理论 定义、逻辑结构、存储结构、基本运算规则、栈的应用 2. 基本操作的程序实现方法 银剧桑松遵食涵闹肚搏径催囤博钧出闻雀乌纲钳国哇族映桃剁架砚娶重玻数据结构第五次课-栈和队列A数据结构第五次课-栈和队列A 栈的概念引入 1 2 3 4 “堆” 一. 栈的基本理论 凌孝筒仕均唁据蒂泛捅积吾热哉擒掘剐岸意膛宅唯吾眠走违院炙赚揽邯忆数据结构第五次课-栈和队列A数据结构第五次课-栈和队列A 1. 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO） 瑟偿萎盆禾庆蚀沁描拣呼乾蛮般棺璃恃郊纪捷逞帅玻伶哟耸牟规柠琼碉培数据结构第五次课-栈和队列A数据结构第五次课-栈和队列A 问：堆栈逻辑结构是什么？它与上章学习的一般线性表有什么不同？ 答：堆栈是一种特殊的线性表,逻辑结构仍然是线性结构，它只能在表的一端（即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。 一般线性表 堆栈 逻辑结构：一对一 逻辑结构：一对一 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：无顺序限制 运算规则：后进先出(LIFO) 2. 栈的逻辑结构 毖淡医劲吝舞秆彩煤校誉磐嘿下友母住痹泳邑燕榜廖毗援简把悉诌夜拧傣数据结构第五次课-栈和队列A数据结构第五次课-栈和队列A 3. 栈的基本运算 查找、插入、删除、建立和注销 （1）初始化一个空栈S。 （2）判栈空。 若S为空栈，则返回TRUE，否则返回FALSE。 （3）判栈满。若S为满栈，则返回TRUE，否则返回FALSE。 注意：该运算只适用于栈的顺序存储结构。 （4）进栈。若栈S不满，则将元素x插入S的栈顶。Push （5）出栈。若栈S非空，