栈的难题

来源：百度知道 编辑：UC知道 时间：2024/05/30 06:28:04
假设有 N 个栈共同使用一块顺序存储的空间，为简单起见可设为共同使用数组 int a〔200〕。初始状态为各栈等分备用空间。每当有某栈上溢时，按下述方法调整各栈的备用空间；将全部备用空间的 X％ 均分给各栈，其余 （100 - X）% 按上一次调整以来各栈的增长的比例分配给各栈，请给出这 N 个栈的出、入栈算法。

思路：

栈a(200)，d为等分空间大小（初次及二次等分1段部分）
N个栈起末位置l、h、栈大小m及指针zz位置b(N)(4)，需初始化
c(N)，增长比例，动态设置

入栈算法：

1、zz<d 或 栈顶>zz>d，入栈
2、zz=m，调用“调整栈”，入栈
3、zz=d(这时m>d），d处数据为2段栈始位置，修改zz后入栈

调整栈算法：
按x%得新的d值，按c(N)分配其余空间，见示意图，同时调整各栈数据（对于新增2段有数据的，对于2段有数据且位置变化者），调整b数组

新栈示意图，分两段：
1段栈底l---------------d处填l2
2段栈底l2处填d处位置----------栈顶h

出栈算法：

1、zz<d 或 栈顶>zz>d，出栈
2、zz=d（数据在2段始位置）d处数据为2段栈始位置，修改zz后出栈

另：可在b中设各栈两段始末位置4个