栈的基本操作详解：初始化、入栈、出栈与判空

要说数据结构里最容易被轻视、却又最能在细节上坑人的内容栈绝对排得上号。oj3335 数据结构实验之栈与队列八栈的基本操作就是这么一道看起来人畜无害、实则把“后进先出”四个字和边界条件考得明明白白的实验题。很多同学拿到题第一反应是“不就入栈出栈嘛”结果不是栈满栈空判断颠倒就是top指针初始化犯迷糊再不然就是输出格式被卡到怀疑人生。这道题能帮你把栈的底层逻辑真正落地。它不要求你背概念而是要求你在一个真实可运行的代码里把初始化、入栈、出栈、读取栈顶、判空这一整套动作做得滴水不漏。这篇文章我打算用带新人踩坑攒下来的经验把栈的基本操作掰开揉碎讲一遍顺便把OJ提交时那些没人明说、却人人绕不开的坑都填平。适合正在赶实验报告的初学者适合期末前突击数据结构的人也适合想回头巩固基础、给自己代码找找茬的老同学。1. 这道实验题到底在考什么1.1 栈的本质就是一句话后进先出栈是一种操作受限的线性表。线性表大家都熟数组、链表都是线性表区别在于栈只在“栈顶”这一端做插入和删除。后进去的元素先出来先进去的元素反而压在底下这个特性缩写叫LIFOLast In First Out。理解它最舒服的方式是叠盘子。你往桌上叠盘子后放上去的盘子一定在最上面你要拿盘子也一定先拿最上面的那个。你不可能越过最上面的盘子直接抽底下的除非你想体验餐具粉碎机。栈就是这么一摞盘子栈底是第一个放进去的元素栈顶是最后一个放进去的元素所有操作都围着栈顶转。这种“限制”听着像是缺点实际恰恰是栈强大的原因。因为操作位置固定入栈、出栈、取栈顶这三个动作的时间复杂度全是O(1)不管栈里有1个元素还是100万个元素速度都差不多。这也是后续很多算法愿意拿栈当辅助结构的原因比如括号匹配、表达式求值、函数调用、浏览器的前进后退底层全是栈在撑腰。1.2 基本操作清单少一个都不行实验题目叫“栈的基本操作”基本操作就那么五个串起来就是栈的全部使用方式InitStack初始化把栈结构准备好top指针归位。Push入栈把元素放到栈顶。Pop出栈把栈顶元素拿走。GetTop取栈顶只看栈顶元素不删除它。StackEmpty判空判断栈里还有没有元素。有些教材还会加一个StackFull判满内存写死的情况下需要它来防止越界。这五个操作就是全部考点别觉得简单真正写起来每个函数都有值得抠的细节。比如初始化时top到底赋-1还是0入栈是先移动top再赋值还是先赋值再移动top出栈时要不要把原来的值清零这些细节没见过坑的人很容易踩着雷。2. 存储结构怎么选顺序栈还是链栈2.1 顺序栈的结构体与内存布局栈可以用数组实现也可以用链表实现分别叫顺序栈和链栈。oj3335这类实验题大多数情况下用顺序栈就够了因为题目一般会给出栈的最大容量而且顺序栈代码短、逻辑直观调试起来也省心。顺序栈的定义通常长这样#define MAXSIZE 1000 typedef struct { int data[MAXSIZE]; int top; } SqStack;data数组用来存元素top用来记录栈顶位置。这里有个非常关键的分歧点top到底指向哪里。如果你让top指向栈顶元素那空栈时top应该为-1。入栈时先top再把元素放进data[top]。出栈时先取data[top]再top--。如果你让top指向栈顶元素的下一个位置那空栈时top应该为0入栈时先存再top出栈时先top--再取。两种写法本身没有对错但混着写就完了。我见过太多人在看别人的代码时被这两种写法绕晕明明都是对的却以为有一个是错的。建议你自己定死一种比如统一用“top指向栈顶元素、初始为-1”然后所有函数都按这一套来。这样以后写括号匹配、写单调栈都不会因为top语义不清而出bug。2.2 为什么top要初始化为-1很多初学同学会问数组下标不是从0开始吗为什么空栈的top不设成0因为top-1意味着“栈里一个元素都没有”如果设成0就表示下标为0的位置上已经有一个元素了。这两个初始值代表着完全不同的栈状态搞混的后果是判断栈空时出错本该是空栈程序却认为有一个元素。打个比方这就像电梯的楼层显示。你在地下室显示-1说明你不在任何可用楼层上你停在一楼显示0或1说明你已经到了某个楼层。top就是一个楼层指示器-1代表“没有任何一层能用”0代表“第0层已经有东西了”。初始化的工作就是把这块“指示灯”拨到正确位置void InitStack(SqStack *s) { s-top -1; }有同学可能会问为什么不用malloc动态分配能用而且很多教材确实是malloc一个数组再让base指针指向它。但对实验题来说数组固定容量最简单也最容易避免内存泄漏问题。如果想要代码更通用也可以定义成int *data然后在init里malloc只是提交OJ时千万别忘了free虽然不free程序也能正常跑完但代码评审时会被挑毛病。2.3 链栈什么时候用链栈就是用单链表模拟栈头结点方向作为栈顶。入栈相当于头插法出栈相当于删除第一个节点。链栈的好处是理论上没有栈满问题内存随用随申请适合处理“数据量不固定且可能很大”的场景。typedef struct StackNode { int data; struct StackNode *next; } StackNode, *LinkStack;入栈时新节点直接插在链表头部top指针更新为新节点出栈时把头部节点摘掉。这个思路不难难点在于链表操作容易写漏指针。实验题没特别要求的话建议优先顺序栈省时间少出错。但概念题、面试题里链栈的实现方法还是要会因为面试官特别喜欢问“栈的两种存储结构是什么各自优缺点”你只答数组一种会显得基本功不扎实。3. 核心操作逐行拆解3.1 入栈Push先动指针还是先放数据顺序栈的入栈代码标准写法是这样int Push(SqStack *s, int x) { if (s-top MAXSIZE - 1) { return 0; // 栈满 } s-data[(s-top)] x; return 1; }注意这句data[(s-top)] x它是先让top加1再把x放进新top指向的位置。这个顺序不能反。如果你写成data[(s-top)] x元素放到了旧top位置然后top才加1看起来好像也“进去了”但栈顶指针指向的是空位下次出栈取到的就是未初始化的垃圾值。入栈前判断栈满是很重要的一步。数组容量有限一旦top超过MAXSIZE-1再写入就是数组越界。OJ不会给你报分段错误那么温柔通常就是直接Runtime Error甚至整个程序跑飞。所以判满不是可选项是必选项。3.2 出栈Pop数据还在但逻辑上已经删了int Pop(SqStack *s) { if (s-top -1) { return 0; // 栈空 } int x s-data[s-top]; s-top--; return x; }很多人会纠结一个问题出栈时要不要把data[top]的位置清零比如写成s-data[s-top] 0。我的答案是不需要。栈的逻辑状态只由top决定只要top减下去了那个位置的数据虽然还残留在数组里但永远不会再被当作有效元素访问。下次有新元素入栈时写入操作会直接覆盖它。你去餐厅吃饭服务员擦完桌子让你重新入座你不会在意上一位客人是不是在椅子上留下了体温逻辑上一个座位就是空闲的。不过如果你的代码里需要“出栈后检查栈内是否还存在某个值”那就得小心了。因为旧数据还在数组里躺着如果你遍历整个数组而不是只遍历0到top的范围就会把已经出栈的元素也扫进去。这个坑在后续做某些算法题时偶尔会出现提前知道能少踩好多雷。3.3 取栈顶与判空别把读和删混为一谈取栈顶GetTop和出栈Pop的最大区别是前者不改变栈的状态。简单说GetTop是“瞄一眼”Pop是“拿走”。int GetTop(SqStack *s) { if (s-top -1) { return -1; // 根据题意处理 } return s-data[s-top]; } int StackEmpty(SqStack *s) { return s-top -1; }判断空栈的条件和初始化是对应的。top-1就是空top0表示第一个位置有数据。很多初学同学容易把StackEmpty写成return s-top 0如果你的top初始是-1那这个判断在栈确实为空时返回0false于是程序就认为栈“不空”后续出栈操作就会取到一个不存在的数据。这个问题在OJ上表现得很典型输入数据本来不涉及非法出栈但因为判空逻辑错了程序自己把自己搞崩。3.4 五个操作的复杂度一张表记牢操作顺序栈复杂度链栈复杂度说明InitStackO(1)O(1)只是初始化指针或头结点PushO(1)O(1)顺序栈可能触发扩容均摊O(1)PopO(1)O(1)链栈需要释放节点GetTopO(1)O(1)不改变栈状态StackEmptyO(1)O(1)比较指针即可这张表看着平平无奇但“栈的基本操作都是O(1)”这个结论是很多算法题分析复杂度的起点。比如后面学单调栈时每个元素最多入栈一次、出栈一次所以总复杂度是O(n)。如果栈的基本操作不是O(1)整个算法框架就得重写。4. 完整代码与OJ提交细节比你想的多4.1 一套可以直接参照的完整代码以一套常见的实验题输入格式为例先输入初始元素个数n和操作次数m第二行输入n个元素接下来m行是操作指令比如PUSH、POP、TOP、EMPTY。我写了一份可以直接跑通的代码你在自己OJ上提交时只需要对照题目描述微调输出部分。#include stdio.h #include string.h #define MAXSIZE 1000 typedef struct { int data[MAXSIZE]; int top; } SqStack; void InitStack(SqStack *s) { s-top -1; } int StackEmpty(SqStack *s) { return s-top -1; } int StackFull(SqStack *s) { return s-top MAXSIZE - 1; } int Push(SqStack *s, int x) { if (StackFull(s)) { printf(栈满无法入栈\n); return 0; } s-data[(s-top)] x; return 1; } int Pop(SqStack *s) { if (StackEmpty(s)) { printf(栈空无法出栈\n); return -1; } int x s-data[s-top]; s-top--; return x; } int GetTop(SqStack *s) { if (StackEmpty(s)) { printf(栈空无栈顶元素\n); return -1; } return s-data[s-top]; } int main() { int n, m, x; char op[20]; SqStack s; InitStack(s); scanf(%d %d, n, m); for (int i 0; i n; i) { scanf(%d, x); Push(s, x); } while (m--) { scanf(%s, op); if (strcmp(op, PUSH) 0) { scanf(%d, x); Push(s, x); } else if (strcmp(op, POP) 0) { Pop(s); } else if (strcmp(op, TOP) 0) { GetTop(s); } else if (strcmp(op, EMPTY) 0) { printf(StackEmpty(s) ? 空栈\n : 非空\n); } } return 0; }代码里的MAXSIZE我写了1000如果你的题目给的元素数量上限更大就改成更大值比如100000。用这种静态数组的好处是代码短、不容易出内存错误坏处是浪费空间题目给多大上限就得多开多少空间。要是真有1e6级别的数据量还是建议用动态扩容或者链栈。4.2 输入输出里那些没人明说的大坑C语言处理输入命令时最常见的问题就是回车符残留。如果你先用scanf(%d)读入数字再用scanf(%c)读字符很容易把末尾的换行符当成操作符读进来然后逻辑直接乱掉。我的建议是能读字符串就不读字符读操作命令时用scanf(%s, op)它会自动跳过前导空白包括换行和空格。这是在OJ上最省心的做法。输出那边也有讲究。OJ比较输出的时候多一个空格可能算你错少一个换行也可能算你错这类错误叫Presentation Error简称PE。PE通常不会直接给Accepted检查时又很难一眼看出来。解决办法是先把调试用的输出全都去掉只保留题目要求的输出如果你拿不准行末空格就看题目有没有给示例输出格式严格照着复制。我当初写这类题就吃过一次亏在调试时加了句“当前栈顶元素是”作为提示交之前忘了删结果输出格式全错。后来我学乖了提交前把代码从头到尾读一遍凡是printf内容不是题目要求的那几行全删干净。这个习惯虽然笨但真的能省下大量改错时间。4.3 多组数据输入如何处理部分实验题喜欢搞多组测试数据每组都读一遍直到文件结束。很多同学第一次遇到时不知道怎么写直接在main里写死一次处理结果OJ只过了一部分数据。处理多组输入的标准姿势是while (scanf(%d %d, n, m) ! EOF) { InitStack(s); // 处理这一组数据 }这个! EOF就是“一直读到文件尾”的意思。OJ判题时会把多组数据放进一个文件里你的程序如果能循环读完所有组就能全部跑对。单组数据测试自然也会正确因为读完第一组后scanf返回EOF循环结束。如果你用的是C也可以写成while (cin n m)效果一样。这个细节看起来小却是很多人“明明本地测试都对交上去就错”的常见原因之一。5. 常见问题与排查技巧实录5.1 栈满和栈空的判断总是搞反我辅导过不少同学发现最集中的问题就是满和空判断颠倒。栈空看的是top是否等于-1栈满看的是top是否等于MAXSIZE-1。两者一个是底儿朝天一个是顶到天花板方向完全不同。有个很稳的记忆方法top的值等于“数组里已有的元素个数减一”。数组里一个元素没有个数是0top就是-1数组里全满了个数是MAXSIZEtop就是MAXSIZE-1。顺着这个关系推怎么写都不会错。如果换成“top指向下一个空位置”的实现空栈top0满栈topMAXSIZE公式就变成“top等于数组中元素个数”。所以首先搞清楚你的top语义再套公式比死记硬背判断条件靠谱得多。5.2 输出格式卡到怀疑人生怎么办遇到PE先用肉眼比对题目的示例输出和自己的输出差异注意换行、空格、全角半角。眼睛看不出来就换个便宜的思路把自己输出里的所有空格和换行先原样保留但确认是不是每行末尾多打了一个空格。多行输出时每行末尾多一个空格有时候OJ不判错有时候判错全看评测机有多严格。另外一个常见问题是不同平台的OJ对中文输出支持程度不一样。实验题里如果要求输出“栈空”有的平台支持UTF-8中文有的平台可能因为编码问题判错。为了避免麻烦优先去读题目的英文Or输出符号说明如果题目说输出“error”就用小写英文不要自作主张换成“ERROR”或“错误”。5.3 出栈和取栈顶时栈顶元素到底怎么处理上面说过出栈不需要物理删除元素只要让top减一。但有一种情况要特别小心如果题目要求出栈后还要输出当前栈顶元素而你是先取栈顶、再判断是否为空顺序就反了。正确的逻辑顺序应该是先判断栈是否为空。为空就按题目要求输出错误信息。不为空才执行取栈顶或出栈操作。顺序颠倒后在空栈时会触发对data[某个非法下标]的访问返回值是脏数据程序还可能因为数组越界直接崩溃。凡是要用到GetTop或Pop的指令进函数先判空这应该形成肌肉记忆。5.4 一组常见错误速查表症状可能原因解决方案程序崩溃/段错误栈满没判断数组越界Push前检查StackFull输出错乱命令读到了换行符用%s读操作字符串结果多出一行调试printf没删除提交前清理多余输出只有部分测试点通过没处理多组输入改用while循环读到EOF空栈判断失败top初始化与判断不一致统一top语义为-1或0局部变量栈溢出数组开在main里栈区爆了改全局数组或减小MAXSIZE最后一行值得多说一句。有些题目数据量大在main函数里开int data[1000000]这种超大数组会直接把程序的调用栈压爆报错可能跟你的业务逻辑毫无关系。遇到莫名其妙崩掉的情况把大数组挪到全局区试一次立竿见影。6. 栈不只是作业题学完能干什么6.1 函数调用栈就是活生生的例子你在写代码时每调用一个函数系统就会把当前函数的返回地址、参数和局部变量压进一个栈。函数执行完系统弹栈回到上一层继续跑。所以递归调用过深时会爆栈本质就是系统栈空间被压满了。理解了函数调用栈你就理解了为什么递归的终止条件那么重要。终止条件缺失函数不停压栈最终栈满程序崩溃这和在顺序栈里猛Push不判满是一样的后果。这个类比能帮你在学树、学图的遍历时快速建立直觉因为递归遍历本质上就是栈在幕后帮忙维护状态。6.2 括号匹配栈的经典课代表括号匹配题是栈最经典的应用之一。拿到一个字符串遇到左括号就入栈遇到右括号就检查栈顶是不是对应的左括号是就弹出不是就匹配失败。全部处理完再检查栈是否为空空才说明所有括号成对且嵌套正确。这个思路用上栈的基本操作时你会发现之前学的InitStack、Push、Pop、StackEmpty全部派上用场。如果基本功不牢写括号匹配时就会卡在“怎么判断栈顶是不是跟自己匹配”这种问题上。反过来如果先把oj3335这道题嚼透了括号匹配就是套模板的事。6.3 表达式求值与单调栈后面还有大片江山中缀表达式转后缀表达式、后缀表达式求值用的都是栈。浏览器里的后退按钮也是靠两个栈实现来回跳转。更深一层单调栈还能在线性时间内解决“下一个更大元素”之类的问题那是算法竞赛里高频考点。这些东西现在不会没关系但你要知道栈这个基础结构有多大的延展性。它就像工具箱里的螺丝刀本身没什么花哨但几乎所有正经工具都离不开它。地基打得牢后面学什么都不会太费劲。我个人在实际写这些代码时最大的体会是栈的题目容错率非常低一个top初始化错误能潜伏很久直到某个极端数据才引爆。所以我会在写完每个函数后立刻用几个边界数据测一遍空栈出栈、栈满入栈、连续出入栈交错。这些测试看着简单却能提前拦下九成以上的逻辑错误。如果你现在被oj3335卡住别急着怀疑人生把top的语义理清楚把栈满栈空的判断写好再把输出格式对照题目刷一遍这道题基本就稳了。另外再送大家一个小经验写完代码以后把操作指令里最常见的PUSH、POP、TOP、EMPTY四种情况各测一遍宁可多敲几行也不要让OJ告诉你错了才回头找。