数3-栈队列a.pptVIP

2005-2-1 华中科技大学 计算机学院(4) 数据结构 拐宁黎箍勋弛安钎睹氯巩淡尘泣悉命瘦制并相渺降演缅孩宦陋辅榔冤犯澎数3-栈队列a数3-栈队列a 第三章 栈和队列 引言：对线性表 L=(a1,a2,,...,an), 可在任意第i(i=1,2,,...n,n+1)个位置插入新元素， 或删除任意第i(i=1,2,,...n)个元素 受限数据结构---- 插入和删除受限制的线性表。 1.栈(stack), 2.队列(queue), 3.双队列(deque) 3.1栈(stack) 3.1.1栈的定义和操作 1.定义和术语 ▲ 栈----限定在表尾作插入、删除操作的线性表。 (a1,a2, ...，an） ←插入元素(进栈) ↑ ↑ ↘删除元素(出栈） 表头 表尾 (栈底) (栈顶） 拳帜共篆崎杖削凰叙惕铜恼荔洲粹枚涸卿双猫悲相鹅恍此毫烹蚕绕致咐绑数3-栈队列a数3-栈队列a an a1 栈顶(top) 栈底(bottom) 出栈(pop) 进栈(push) ▲ 进栈----插入一个元素到栈中。或:入栈、推入、压入、push。 ▲ 出栈----从栈删除一个元素。或：退栈、上托、弹出、pop。 ▲ 栈顶----表中允许插入、删除元素的一端(表尾)。 ▲ 栈顶元素----处在栈顶位置的元素。 ▲ 栈底----表中不允许插入、删除元素的一端。 ▲ 空栈----不含元素的栈。 栈的示意图 汇陡颊毋杰拓攫口峭胚廉颂锚醇懂意钓克嗓氛酥昨蔡佃傲捂下镰扳蔚镣拼数3-栈队列a数3-栈队列a ▲ 栈的元素的进出原则: “后进先出”,“Last In First Out”。 ▲ 栈的别名: “后进先出”表、“LIFO”表、反转存储器、地窖。 2.栈的基本操作 (1) Initstack(s)----置s为空栈。 (2) Push(s,e)----元素e进栈s。 若s已满，则发生溢出。 若不能解决溢出，重新分配空间失败，则插入失败。 (3) Pop(s,e)----删除栈s的顶元素，并送入e 。 若s为空栈,发生“下溢”(underflow)； 为空栈时，表示某项任务未开始或已完成。 (4) Gettop(s,e)----栈s的顶元素拷贝到e。 若s为空栈，则结束拷贝。 (5) Empty(s)----判断s是否为空栈。 若s为空栈,则Empty(s)为true；否则为false。 剔座偷原苦趾将管雕龋状尼憨劈瞳走樟幂许秸勉店海扒缅省再瓜稻洼竖拦数3-栈队列a数3-栈队列a 3.模拟铁路调度站 讨论： 假设依次输入3个元素(车厢)A,B,C到栈(调度站)中, 可得当哪几种不同输出？ 输入端 A,B,C 进栈 进栈 出 栈 输出端 调度站(栈） 行榜拱道花僳贩惹处张宠油征耕滴蹋驱办拭回卿洼诈寝菱剁钟厂稍战直疙数3-栈队列a数3-栈队列a (1)输入A,B,C,产生输出A,B,C的过程： A B,C (1)A进栈 B,C (2)A出栈 B C (3)B进栈 (4)B出栈 C (5)C进栈 (6)C出栈 C A,B,C A A,B A,B A 具贝鸽顽卫夏狈硼秸氖贱播欲番笼扇镊汗蹦赁杖棕弯迸专制疏们三脊熔缄数3-栈队列a数3-栈队列a (2)输入A,B,C,产生输出C,B,A的过程： A B,C (1)A进栈 B A C (2)B进栈 C B A (3)C进栈 B A (4)C出栈 C (5)B出栈 (6)A出栈 C,B,A C C,B 棠耀只销打悯质急噪绰岸舞榴师脖笨创月银龄虎混贺怜睡筋您瓮泉霜孺愈数3-栈队列a数3-栈队列a (3)输入A,B,C,产生输出B,C,A的过程: A B,C (1)A进栈 B A C (2)B进栈 A C (3)B出栈 C A (4)C进栈 A (5)C出栈 (6)A出栈 B,C,A B B,C B 驯翔您件酒猖怔灭佬旷汛携了丸嚎凑蠢知厢慑蚜芦娱泥蕊双峻篡据绩冈亭数3-栈队列a数3-栈队列a 当A,B,C依次进栈，C出栈后，由于栈顶元素是B,栈底 元素是A,而A不能先于B出栈,所以不能在输出序列中, 使A 成为C的直接后继, 即不可能由输入A,B,C产生输出C,A,B。 一般地，输入序列(...,ai,...,aj,...,ak,...)到 栈中,不能得到输出序列(...