扫码获取 VIP 码
添加管理员微信获取 VIP 码
栈是计算机科学中最基础、最经典，同时也是软考软件设计师与系统分析师考试中年年必考的数据结构。很多考生对栈的理解停留在"后进先出"四个字上，以为背住这句口诀就能应付考试，结果一遇到"给定入栈序列判断出栈序列是否合法"这类题目就屡屡丢分。究其原因，在于考生只记住了结论，却没有真正理解栈的底层存储机制、栈顶指针的移动规律，以及栈在表达式求值、递归调用、括号匹配这些真实场景中的运行逻辑。本文将从栈的抽象定义出发，深入顺序栈与链栈的存储结构，剖析入栈出栈序列合法性的判断方法，最后结合历年真题讲清命题人的挖坑套路，帮助读者把栈这个考点彻底吃透。
从数据结构的严格定义来看，栈是一种限定仅在表尾进行插入和删除操作的线性表。这句话里每个字都值得拆开理解。所谓"线性表"，是指栈中元素之间依然保持前驱与后继的线性关系，元素在逻辑上排成一列；所谓"限定仅在表尾"，是指栈对插入和删除操作的位置做了严格限制，它们只能发生在同一个端点。这个允许插入和删除的一端被称为栈顶，相应地，另一端固定不动，被称为栈底。当栈中没有元素时，称为空栈；当栈空间已被占满、无法再插入时，称为上溢；反过来，当栈为空却还要删除时，则发生下溢。
栈的插入操作通常被称为入栈或压栈，对应英文术语 push；删除操作被称为出栈或弹栈，对应英文术语 pop。这两个术语源自一叠盘子的形象比喻：盘子一个接一个叠放上去，取用时只能从最上面取，最先放进去的盘子被压在最下面，必须等上面的全部取走之后才能轮到它。这个比喻直观揭示了栈的核心特性——后进先出，英文表述为 Last In First Out，简称 LIFO，即最后进入栈的元素最先离开。与之对照的是队列，队列遵循先进先出原则，即 First In First Out，简称 FIFO。栈与队列的这一根本区别，是软考选择题中最基础的送分点，也是后续一切推理的逻辑起点。
需要强调的是，栈是一种逻辑结构，而不是某种特定的物理实现。逻辑结构描述的是数据元素之间的抽象关系，它不关心这些元素在内存中如何存放。同一个栈，既可以用一段连续的内存空间来实现，也可以用一组通过指针链接起来的结点来实现。前者称为顺序栈，后者称为链栈。考生复习时必须明确区分逻辑结构与存储结构这两个层次，否则很容易在"栈的存储结构是什么"这类判断题上出错。
理解栈顶与栈底的关系，是掌握一切栈操作的前提。不妨把栈想象成一个开口朝上的竖直容器，栈底在底部，栈顶在开口处。元素只能从开口进出，因此每次入栈、出栈都发生在栈顶。这个"单一开口"的特性，决定了栈中元素的相对顺序在出栈时必然发生反转：入栈时先进先到栈底、后进后到栈顶，出栈时则后进先出、先进后出。
栈顶指针是顺序栈实现中最关键的概念。它本质上是一个整数下标或内存地址，始终指向当前栈顶元素所在的位置。栈空时，栈顶指针通常指向约定的初始值；每次入栈，栈顶指针先加一再写入新元素；每次出栈，先取出指针所指元素再将栈顶指针减一。整个入栈出栈过程，核心动作就是栈顶指针的上下移动。理解这一点，对后续计算栈容量、判断出栈序列合法性都至关重要。
顺序栈是用一段连续的存储空间来存放栈中元素的一种实现方式。在顺序栈中，通常需要三个要素：一个用于存放元素的数组、一个用于指示栈顶位置的栈顶指针、以及一个用于记录数组最大容量的常量。由于数组的下标从零开始，栈顶指针的取值既可以是当前栈顶元素的下标，也可以约定为栈顶元素的下一位置。这两种约定在软考教材和不同教材中都有出现，考生必须看清题目所采用的约定，否则在做计算题时会差一个位置。
顺序栈的入栈操作可以分解为两步：第一步，判断栈是否已满，若栈顶指针已经等于最大容量减一，说明栈空间耗尽，此时入栈会发生上溢；第二步，将栈顶指针加一，然后把新元素存入数组在该指针所指的位置。出栈操作同样分为两步：第一步，判断栈是否为空，若栈顶指针已经指向空栈的约定位置，说明无元素可出，此时出栈会发生下溢；第二步，取出栈顶指针所指的元素作为返回值，然后将栈顶指针减一。值得注意的是，出栈操作并不需要真正地把数组中的那个元素从内存里清除掉，它只是移动了栈顶指针，使那个位置在逻辑上变成了"不可见"的区域。这个细节在理解栈的空间复用时很有意义。
顺序栈的优点是实现简单、存取效率高，由于元素在内存中连续存放，借助数组的随机访问特性，栈顶元素的定位可在常数时间内完成。它的缺点同样明显：数组容量必须在创建时预先确定，定小了容易上溢，定大了又浪费内存。为解决这个问题，教材中引入了动态扩容的顺序栈，即当栈满时重新分配一块更大的连续空间，把原有元素整体复制过去。但考生要注意，动态扩容意味着扩容时刻栈中所有元素的内存地址都可能发生改变，这与链栈中结点地址始终稳定的特性形成对比。
链栈是用链表来实现栈的一种方式，它不要求元素在内存中连续存放，而是通过指针把各个结点串联起来。链栈通常采用单链表的结构，并且把头结点之后的第一个结点作为栈顶。这样设计的原因在于，链表的头部插入和删除操作最为高效，在常数时间内即可完成，恰好满足栈在栈顶频繁插入删除的需求。如果反过来把链表尾部当作栈顶，那么每次入栈出栈都需要遍历整个链表，效率会退化到线性时间。
链栈的入栈操作相当于在链表头部插入一个结点：先为新元素分配一个结点，让新结点的指针域指向当前的栈顶结点，再让栈顶指针指向这个新结点。出栈操作相当于删除链表头部的结点：先记录当前栈顶结点的元素值，然后让栈顶指针指向该结点的下一个结点，最后释放被删除结点的内存。由于链栈的结点是按需动态分配的，理论上只要内存充足，链栈就不会发生上溢，这一点是链栈相对于顺序栈的显著优势。软考选择题中常有"链栈不会上溢"或"链栈入栈无需判满"之类的说法，考生需要结合链栈的动态分配特性来理解其正确性。
链栈的缺点是需要额外的指针域来存储地址，产生了额外的空间开销，同时结点的动态分配和释放也带来一定的时间开销。此外，链栈由于元素不连续存放，无法像顺序栈那样利用随机访问直接定位任意位置，只能从栈顶开始逐个遍历。不过在栈这个场景下，我们本来就不需要随机访问，只需要在栈顶操作，因此链栈的这些缺点在实际使用中通常可以接受。
栈顶指针的移动规律是软考计算题的核心考察点。以最常见的约定——栈顶指针指向当前栈顶元素为例，设栈的容量为 n，栈顶指针初始值为负一表示空栈。那么每入栈一个元素，栈顶指针从负一增加到零、再到一，依次类推，最多到 n 减一；每出栈一个元素，栈顶指针递减一。当栈顶指针等于 n 减一时，栈满；等于负一时，栈空。若换用"栈顶指针指向栈顶元素下一位置"的约定，那么空栈时栈顶指针为零，栈满时等于 n。
理解栈顶指针的移动规律后，计算"栈的容量至少为多少"这类题目就变得清晰起来。这类题目通常给出一个包含连续运算的中缀表达式，要求求出用栈对其求值时，操作数栈所需的最小容量。解题的关键是模拟整个求值过程，跟踪每个时刻栈中实际存放了多少个操作数，然后取这个数量在全程中的最大值。这类题目的正确解法永远是老老实实地模拟过程，而不是靠猜测或背答案。
表达式求值是栈最经典也最常考的应用之一。人们在日常书写中使用中缀表达式，即运算符位于两个操作数之间，例如 a 加 b。但计算机直接处理中缀表达式并不方便，因为运算符的优先级和括号会带来复杂的扫描顺序问题。因此，计算机通常先把中缀表达式转换成后缀表达式，也就是逆波兰表达式，再对后缀表达式求值。后缀表达式的特点是运算符位于其两个操作数之后，天然不含括号，运算顺序完全由运算符出现的先后决定，非常适合用栈来求值。
中缀转后缀的过程要用到一个运算符栈。扫描中缀表达式时，遇到操作数就直接输出；遇到运算符时，将其与运算符栈顶的运算符比较优先级，若栈顶运算符优先级不低于当前运算符，则不断弹出栈顶运算符并输出，直到栈顶运算符优先级更低或栈为空，再把当前运算符入栈；遇到左括号时直接入栈；遇到右括号时不断弹出栈顶运算符并输出，直到遇到左括号并将其弹出丢弃。这个过程中，栈充当了"暂存运算符、按优先级调整输出顺序"的角色。
对后缀表达式求值的过程则要用到操作数栈。从左到右扫描后缀表达式，遇到操作数就入栈；遇到运算符时，从操作数栈中弹出所需的若干个操作数，通常是两个，按运算符进行计算，再
本篇完！