栈的逻辑实现

张开发
• 2026/5/1 16:39:56 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

栈的逻辑实现
简单点说逻辑栈Array-based Stack就是用一个普通数组再加上一个标记“栈顶”在哪里的变量通常叫top就成了栈。它不需要复杂的struct和malloc它的“入栈”和“出栈”全靠手动修改top的数值。1. 它是怎么用的对比看最直观假设我们要存[10, 20, 30]这三个数。物理栈你的写法你需要调用函数stpush(s, 10); stpush(s, 20);内部在做检查容量 - 申请内存 - 拷贝指针 - 修改s-top。逻辑栈数组模拟你就写两行代码ints[100];// 数组就是栈的身子inttop0;// top 就是栈顶指针// 入栈 (Push)s[top]10;// top变成1s[1]10s[top]20;// top变成2s[2]20// 出栈 (Pop)top--;// 仅仅是把指针往下挪一位20还在数组里但我们逻辑上认为它不在栈里了2. 为什么要“逻辑上”用它核心优势你刚才那题为什么用逻辑栈最快看这个操作Q k询问前 k 个数的最大前缀和。物理栈你只能看到栈顶那个数。如果你想看第k个数你必须把上面的数全部pop出来存到别处看完再压回去。这叫破坏性访问逻辑栈虽然它是栈但它本质还是数组s[MAX]。你可以直接写printf(%d, f[k])。这叫随机访问既有栈的“先进后出”特性方便模拟光标移动又有数组的“随便看哪位”特性方便查前缀和。3. 我该什么时候用“逻辑栈”在明天的考试或平时的算法题中遵循这个原则情况 A什么时候用你的【物理栈struct malloc】明确要求实现“抽象数据类型ADT”老师说“请定义一个栈的结构体并实现其基本操作”。数据量完全未知你不知道会有 100 个还是 1 亿个数必须用动态内存管理。工程开发写一个库给别人用为了防止别人乱动栈底数据必须封装起来。情况 B什么时候用【逻辑栈数组 top 变量】限时算法题/考试比如明天只有 15 分钟写struct太浪费时间。已知数据范围题目说了N≤106N \le 10^6N≤106你直接开个int s[1000005]即可。需要“偷看”栈内元素像你这道编辑器题目需要频繁访问前k个数的状态逻辑栈数组是唯一的选择。4. 总结明天 15 分钟伪代码怎么选如果题目是“实现一个线性表的逆置算法”用指针或数组索引直接操作不要去套栈的操作浪费时间。如果题目是“利用栈实现 XXX 逻辑”如果你想写得快PUSH(x): top top 1 Stack[top] x POP(): top top - 1 RETURN Stack[top1]如果你想拿高分展示严谨性PUSH(S, x): IF S.top S.maxSize THEN RETURN OVERFLOW S.data[S.top] x一句话建议明天如果只是为了实现某种算法逻辑直接用数组 下标变量当做“逻辑栈/逻辑队列”来写逻辑最清晰不容易把自己绕进去。

更多文章