扫码获取 VIP 码
添加管理员微信获取 VIP 码
在数据结构这门课程里，栈被官方教材定义为一类操作受限的线性表，它只允许在同一端进行插入和删除操作，这一端称为栈顶，另一端则称为栈底。所谓操作受限，指的是栈的插入与删除不能像普通线性表那样在任意位置随意进行，而必须严格限制在栈顶一端完成。插入元素的操作在教材中被称作入栈，也叫压栈，对应的英文术语是Push；删除元素的操作被称作出栈，也叫弹栈，对应的英文术语是Pop。正是由于这种只在一端进出的约束，栈呈现出一种鲜明的行为特征，即后进先出，英文缩写为LIFO。后进先出的含义十分直观：最后进入栈的元素必然最先离开栈，最先进入栈的元素反而最后才能离开栈，这与现实生活中的一摞盘子高度相似，最晚放上去的盘子总是最先被取走。
栈与队列是数据结构中一对经典的对照结构，二者同为操作受限的线性表，但约束方向恰好相反。栈是后进先出，队列是先进先出，这一根本区别贯穿软考所有涉及进出顺序的题目。许多考生在初学时容易把两者混淆，其实只要抓住插入与删除发生的位置即可区分：栈的插入和删除都发生在同一端，队列的插入发生在队尾、删除发生在队头。理解栈与队列的这一层对照关系，不仅有助于答对概念题，更能为后续学习递归、函数调用、广度优先遍历等内容打下基础。
栈的定义虽然简洁，却蕴含着深刻的程序设计思想。从抽象数据类型视角观察，栈对外只暴露若干基本操作：初始化一个空栈、判断栈是否为空、判断栈是否已满、读取栈顶元素、入栈、出栈以及求栈中元素的个数。其中读取栈顶元素与出栈是两个容易混淆却又必须严格区分的操作，读取栈顶元素仅仅返回栈顶元素的值而不改变栈的结构，出栈则会在返回栈顶元素的同时把该元素从栈中移除。这个细节在软考选择题里反复出现，命题人常常用"读取栈顶元素之后栈是否发生改变"来设陷阱。
栈顶指针是理解栈结构的关键概念。无论是顺序存储的栈还是链式存储的栈，都需要一个专门的指示器来标记当前栈顶的位置，这个指示器被称为栈顶指针，通常记作top。栈顶指针的取值约定因教材版本而异，有的教材约定栈顶指针直接指向栈顶元素本身，有的教材则约定栈顶指针指向栈顶元素上方的空位置。这两种约定在判空和判满的条件表达上会产生截然不同的结果，考生务必在阅读题干时先辨认命题所采用的约定，否则极易在判断栈空栈满时出错。
顺序栈是用一组地址连续的存储单元依次存放栈中元素的实现方式，其底层本质是一个一维数组，再配合一个整型变量作为栈顶指针。顺序栈的实现逻辑非常直接：为数组分配固定大小的空间后，让栈底固定在数组下标为零的位置，栈顶指针随元素的进出而上下移动。当栈为空时，栈顶指针指向栈底位置；当有元素入栈时，先把栈顶指针上移，再把元素写入新的栈顶位置；当有元素出栈时，先取出栈顶元素，再把栈顶指针下移。
在具体的入栈与出栈操作上，顺序栈的每一步都必须严格按照指针与数据写入的先后顺序执行，否则会出现数据被覆盖或指针错位的错误。以栈顶指针指向栈顶元素这一约定为例，入栈操作应当先把栈顶指针加一，再把新元素写入指针所指向的位置；如果顺序颠倒，先写元素再加指针，就会在下次入栈时覆盖刚写入的数据。同理，出栈操作应当先取出指针所指向的元素，再把栈顶指针减一；如果先减指针再取元素，取出的就是已经过期的数据。这类操作顺序的细节虽然琐碎，却是理解栈实现机制的核心，也是软考考查底层原理时常设的陷阱。
顺序栈的边界判定是命题的重灾区。在采用"栈顶指针指向栈顶元素"这一约定时，通常令初始栈顶指针的值为负一，入栈时先让指针加一再存入元素，出栈时先取出元素再让指针减一，此时栈空的条件是栈顶指针等于负一，栈满的条件是栈顶指针等于数组最大下标。而在采用"栈顶指针指向栈顶上方空位"这一约定时，通常令初始栈顶指针的值为零，入栈时先存入元素再让指针加一，出栈时先让指针减一再取出元素，此时栈空的条件是栈顶指针等于零，栈满的条件是栈顶指针等于数组容量。两种约定都能正确实现栈，但判空判满表达式正好相反，这正是软考选择题最喜欢考查的区分点。
顺序栈还存在一个无法回避的固有缺陷，那就是栈的容量必须预先确定。由于数组空间是静态分配的，一旦分配的容量不足，就会出现上溢，也就是栈满之后还要继续入栈；反之，如果对空栈执行出栈操作，就会出现下溢。上溢通常属于程序设计的错误，需要扩容或调整算法；下溢则往往被用作算法结束的判定标志，例如在表达式求值过程中，当需要弹出操作数却发现栈为空时，就说明表达式存在语法错误。理解上溢与下溢的本质区别，有助于考生准确判断程序异常的原因。
链栈是用链表实现的栈，它彻底摆脱了顺序栈容量固定的限制，理论上可以容纳任意数量的元素。链栈通常采用单链表来实现，并且把链表的头部作为栈顶，这样入栈和出栈操作就都可以在链表头部完成，时间复杂度恒为常数级。链栈之所以选择链表头部作为栈顶，是因为在单链表中，头部插入和头部删除都不需要遍历整个链表，效率最高；如果反过来把链表尾部作为栈顶，那么每次出栈都要从头部遍历到尾部才能找到倒数第二个结点，效率会退化到线性级别。
链栈的结点结构与普通单链表结点相同，每个结点包含一个数据域和一个指向后继结点的指针域。入栈时，新建结点并让新结点的指针指向原来的栈顶结点，再把栈顶指针更新为指向新结点；出栈时，把栈顶指针指向的结点摘除，同时让栈顶指针后移指向下一个结点，并释放被摘除结点的内存。链栈判空的条件极为简单，只要栈顶指针为空指针，即表示栈中没有任何元素。由于链栈不存在容量上限，因此它天然不存在上溢问题，只有可能在空栈时误操作导致下溢。
顺序栈与链栈的选择体现了时间与空间的权衡。顺序栈实现简单，元素在内存中连续存放，具有较好的空间局部性，缓存命中率高，适合元素数量已知且变化不大的场景；链栈则胜在灵活，可以随用随增，但每个结点都要额外付出一个指针域的存储开销，且频繁的内存分配与释放会带来一定的性能损耗。软考选择题经常让考生判断在给定场景下应该优先选择顺序栈还是链栈，其判断依据正是元素数量的确定性与对内存开销的敏感程度。
顺序栈的容量固定带来的浪费问题，在实践中可以通过双栈共享空间的方式加以缓解。双栈共享空间的做法是，让两个栈共用同一个数组空间，一个栈的栈底设在数组的一端，另一个栈的栈底设在数组的另一端，两个栈的栈顶都向中间生长。这样一来，两个栈可以充分利用数组空间，只要两个栈顶尚未相遇，空间就还没有耗尽，从而避免了各自独立分配造成的空间浪费。两个栈共享空间的判满条件是两个栈顶指针相遇，即二者相邻，此时无论哪一个栈再入栈都会发生上溢。
双栈共享空间的巧妙之处在于把两个栈的冗余空间合并利用，它体现的是空间复用思想在数据结构中的具体应用。软考选择题偶尔会考查双栈共享空间的判满条件，考生只需记住判满的本质是两个栈顶指针相遇，就能准确作答。需要注意的是，双栈共享空间要求两个栈的容量之和不超过数组总容量，且两个栈的增长方向相反，这一前提一旦缺失，共享方案就无法成立。
栈在后进先出的特性之下，还有一个极为重要的应用，那就是支撑程序设计语言中的函数调用。每当一个函数被调用时，运行时系统都会在内存的调用栈中压入一个栈帧，这个栈帧记录了函数的局部变量、参数、返回地址以及保存的寄存器值等信息；当函数执行完毕返回时，对应的栈帧从调用栈中弹出，控制权重新回到调用者。正因为函数调用遵循后进先出的顺序，被调用的函数总是先于调用者结束，所以用栈来管理函数调用是天然契合的。
递归是栈在程序设计中最直观的体现。一个递归函数在执行过程中会反复调用自身，每一次调用都会在调用栈上压入新的栈帧，只有当递归达到终止条件后，这些栈帧才会依次弹出，函数逐层返回。如果递归缺少正确的终止条件，栈帧就会无限增长，最终导致栈溢出，这实际上就是顺序栈上溢在真实系统中的直接体现。理解了这一点，考生就能明白为什么递归程序在深度过大时会发生崩溃，以及为什么很多递归算法可以通过显式维护一个栈来改写成非递归版本。