4、多栈共享问题 如何充分利用栈空间,这是解决存储空间紧张这样一个 实际矛盾所要考虑的问题。 作为一种策略,就是多栈共享一个栈空间。具体作法是: 对两栈共享情况来说,将两个栈底分别设在两端, 两个栈顶指针top1和top2相对中间位置动态移动, 两个栈之间的分界线是不定的。 a 空栈 topl =-1 top2=MAXSIZE 栈1、栈2均有若干元素 上一页 p top 「停止放映 栈满的情况 下一页 op top2 第16页
下一页 上一页 停止放映 第 16 页 4、多栈共享问题 ⚫ 如何充分利用栈空间，这是解决存储空间紧张这样一个 实际矛盾所要考虑的问题。 ⚫ 作为一种策略，就是多栈共享一个栈空间。具体作法是： – 对两栈共享情况来说，将两个栈底分别设在两端， 两个栈顶指针top1和top2相对中间位置动态移动， 两个栈之间的分界线是不定的。 a. b. c. top1 =-1 top2=MAXSIZE 空栈 top1 top2 栈1、栈2均有若干元素 top1 top2 栈满的情况
5、栈的链式存储结构 由前面介绍的链表结构可知,链结构 操作灵活。对栈结构也是一样的。 ●顺序栈最多可用于2个栈的共享,对 于更多的栈就难于表达了。 对于最大空间需要量事先不知的情况, 就不能使用顺序栈了。这时,就需要 采用链栈。 上一页 「停止放映 链栈:栈的链式存储结构 下一页 第17页
下一页 上一页 停止放映 第 17 页 5、栈的链式存储结构 ⚫ 由前面介绍的链表结构可知，链结构 操作灵活。对栈结构也是一样的。 ⚫ 顺序栈最多可用于2个栈的共享，对 于更多的栈就难于表达了。 ⚫ 对于最大空间需要量事先不知的情况， 就不能使用顺序栈了。这时，就需要 采用链栈。 链栈：栈的链式存储结构
链栈存储结构 ●(1)链栈存储结构的C语言描述: struct snode I int data struct snode link typedef struct snode Snode ●链栈为空的条件: top= NULL 上一页 链栈为满的条件: 「停止放映 t= NULL 下一页 t为申请的结点,为NU表示失败 第18页
下一页 上一页 停止放映 第 18 页 链栈存储结构 ⚫ (1) 链栈存储结构的C语言描述： struct snode { int data; struct snode *link; }; typedeef struct snode SNODE ; ⚫ 链栈为空的条件： top = NULL ⚫ 链栈为满的条件: t = NULL t 为申请的结点,为NULL表示失败
链栈示意图 top 栈顶 ●●●●●● a3 a 上一页 「停止放映 a1入栈底 下一页 第19页
下一页 上一页 停止放映 第 19 页 链栈示意图 a1 a2 a3 ^ 栈底 top 栈顶 …... ai
(2)算法1-10进栈操作 算法1-10操作步骤: stepl申请一个链栈结点,若 t=NULL,则表示链满;否则,执行 step2 ●step2在top所指结点之前插入 新结点,并将top指向新申请的结 点t。 上一页 「停止放映 下一页 第20页
下一页 上一页 停止放映 第 20 页 (2) 算法1-10 进栈操作 算法1-10操作步骤: ⚫ step1 申请一个链栈结点,若 t=NULL,则表示链满;否则,执行 step2 ; ⚫ step2 在top所指结点之前插入 新结点,并将top指向新申请的结 点t