- 1、本文档共22页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第四章 堆栈和队列 提纲 4.1堆栈的概念及其运算 4.2堆栈的顺序存储结构 4.3堆栈的链式存储结构 4.1堆栈的概念及其运算 堆栈的逻辑结构 堆栈:限定仅在表尾进行插入和删除操作的线性表。 空栈:不含任何数据元素的栈。 允许插入和删除的一端称为栈顶,另一端称为栈底。 4.1堆栈的概念及其运算 4.1堆栈的概念及其运算 4.1堆栈的概念及其运算 4.1堆栈的概念及其运算 4.1堆栈的概念及其运算 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.3堆栈的链式存储结构 4.3堆栈的链式存储结构 4.3堆栈的链式存储结构 时间性能:相同,都是常数时间O(1)。 空间性能: 顺序栈:有元素个数的限制和空间浪费的问题。 链栈:没有栈满的问题,只有当内存没有可用空间时才会出现栈满,但是每个元素都需要一个指针域,从而产生了结构性开销。 总之,当栈的使用过程中元素个数变化较大时,用链栈是适宜的,反之,应该采用顺序栈。 * (a1, a2, ……, an) 栈顶 栈底 a b c 入栈 出栈 栈底 栈顶 插入:入栈、进栈、压栈 删除:出栈、弹栈 栈顶 栈顶 栈的示意图 栈的操作特性:后进先出 例:有三个元素按a、b、c的次序依次进栈,且每个元素只允许进一次栈,则可能的出栈序列有多少种? 栈底 栈顶 a b 栈顶 c 栈顶 情况1: 出栈序列:c 出栈序列:c、b 出栈序列:c、b、a 例:有三个元素按a、b、c的次序依次进栈,且每个元素只允许进一次栈,则可能的出栈序列有多少种? 栈底 栈顶 a b 栈顶 情况2: 出栈序列:b 栈底 a 出栈序列:b 出栈序列:b、c 出栈序列: b、 c、a c 栈顶 栈顶 注意:栈只是对表插入和删除操作的位置进行了限制,并没有限定插入和删除操作进行的时间。 情况2: 例:有三个元素按a、b、c的次序依次进栈,且每个元素只允许进一次栈,则可能的出栈序列有多少种? 堆栈的操作 Push(S,x) Pop(S) Empty(S) Top(S) Create(S) 如何改造数组实现栈的顺序存储? 0 1 2 3 4 5 6 7 8 a1 确定用数组的哪一端表示栈底。 附设指针top指示栈顶元素在数组中的位置。 top 出栈:top减1 进栈:top加1 栈空:top= -1 0 1 2 3 4 5 6 7 8 a1 top a2 top a3 top 栈满:top= MAX_SIZE 堆栈是否为空测试算法p70 进栈算法p71 退栈算法 解决方案1: 直接解决:为每个栈开辟一个数组空间。 解决方案2: 顺序栈单向延伸——使用一个数组来存储两个栈 在一个程序中需要同时使用具有相同数据类型的两个栈,如何顺序存储这两个栈? 会出现什么问题?如何解决? 两栈共享空间:使用一个数组来存储两个栈,让一个栈的栈底为该数组的始端,另一个栈的栈底为该数组的末端,两个栈从各自的端点向中间延伸。 栈1的底固定在下标为0的一端; 栈2的底固定在下标为MaxSize-1的一端。 top1和top2分别为栈1和栈2的栈顶指针; MaxSize为整个数组空间的大小(图中用S表示); a1 a2 … ai top1 0 1 2 … … S-1 top2 bj … … b2 b1 栈1底 栈2底 top1= -1 什么时候栈1为空? a1 a2 … ai top1 0 1 2 … … S-1 top2 bj … … b2 b1 top1 top1= -1 什么时候栈1为空? a1 a2 … ai top1 0 1 2 … … S-1 top2 bj
文档评论(0)