扫码获取 VIP 码
添加管理员微信获取 VIP 码
栈（Stack）是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶（Top），另一端称为栈底（Bottom）。不含任何元素的栈称为空栈。栈的插入操作称为入栈或压栈（Push），删除操作称为出栈或弹栈（Pop）。
栈最核心的特性是后进先出（Last In First Out，LIFO）。后进先出意味着最后入栈的元素最先出栈，最先入栈的元素最后出栈。这一特性与日常生活中的子弹夹、摞在一起的盘子、浏览器后退按钮的行为完全一致，但栈在计算机科学中的地位远不止一个先进后出的容器这么简单，它是函数调用、表达式求值、递归、编译器语法分析等一系列底层机制得以运转的基石。
从数据结构分类的角度看，栈属于线性结构的一种。线性结构包括线性表、栈、队列、数组、串等，它们的共同特征是数据元素之间存在一对一的线性关系。栈区别于普通线性表的关键在于运算受限四个字：普通线性表可以在任意位置插入和删除，而栈只允许在栈顶这一端进行插入和删除。正是这种限制，换来了操作的简单性和后进先出语义的确定性。
在教材和软考考纲中，栈通常以抽象数据类型（Abstract Data Type，ADT）的形式给出规范。一个完整的栈抽象数据类型包含数据对象和数据关系，以及一组基本操作。
初始化操作（InitStack）负责构造一个空栈，将栈顶指针置于空栈状态。判空操作（StackEmpty）判断栈是否为空，若为空返回真。入栈操作（Push）在栈顶插入一个元素，入栈前必须判断栈是否已满。出栈操作（Pop）删除栈顶元素并返回其值，出栈前必须判断栈是否为空。取栈顶元素操作（GetTop）只读取栈顶元素的值而不删除它，这一操作在考试中常与出栈操作混淆。此外还有求栈长（StackLength）、清空栈（ClearStack）等辅助操作。
需要特别强调的是取栈顶与出栈的区别。取栈顶操作 GetTop 返回栈顶元素的值，但栈顶指针不移动，元素仍然保留在栈中；出栈操作 Pop 则同时完成读取值和删除元素两件事，栈顶指针向下移动一个位置。软考命题人经常在取栈顶元素和弹出栈顶元素之间做文章，考生稍不留意就会把 GetTop 和 Pop 混为一谈。
顺序栈是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设置一个栈顶指针 top 指示栈顶元素在顺序栈中的位置。顺序栈可以用一维数组来实现，数组下标从零开始，栈底元素固定存放在下标为零的位置。
栈顶指针 top 的取值约定是顺序栈最容易出错的细节，存在两种主流约定。第一种约定是 top 指向栈顶元素本身，此时空栈的标志是 top 等于负一，入栈时先令 top 加一再把元素存入，出栈时先取出元素再令 top 减一。第二种约定是 top 指向栈顶元素的下一个空闲位置，此时空栈的标志是 top 等于零，入栈时先把元素存入 top 所指位置再令 top 加一，出栈时先令 top 减一再取出元素。
这两种约定在功能上完全等价，但入栈出栈的先后顺序正好相反。考生在做题时首先要判断题目采用的是哪一种约定，否则极易在 top 指针初始值、入栈出栈顺序这类细节上丢分。软考中更常见的是第一种约定，即 top 指向栈顶元素、空栈时 top 等于负一。
入栈操作的核心流程是先判断栈是否已满。设栈的最大容量为 maxsize，若采用 top 指向栈顶元素的约定，则当 top 等于 maxsize 减一时栈已满，此时再入栈就会发生上溢（Overflow）。出栈操作的核心流程是先判断栈是否为空，若 top 等于负一则栈空，此时再出栈就会发生下溢（Underflow）。上溢是错误状态，需要避免；而下溢在算法设计中常常被当作某种终止条件来利用，例如表达式求值结束、括号匹配完成时的自然退出。
链栈是用链表实现的栈。由于栈的操作都集中在栈顶，而链表的表头插入和删除操作时间复杂度都是常数级别，因此链栈通常把链表的表头作为栈顶，这样入栈等价于在表头插入一个结点，出栈等价于删除表头结点。
链栈不需要预先分配固定大小的存储空间，理论上只要内存充足就不会发生上溢，这是链栈相对于顺序栈的最大优势。链栈的入栈操作需要动态申请新结点，将新结点的指针域指向原栈顶结点，再让栈顶指针指向新结点；出栈操作则需要先保存栈顶结点的值，将栈顶指针移动到下一个结点，然后释放原栈顶结点的内存空间。
链栈与顺序栈的选择体现了软考中时间与空间权衡的经典命题。顺序栈空间利用率高、访问速度快，但容量固定，存在上溢风险；链栈容量灵活，但每个结点都要额外占用一个指针域的存储空间，且动态内存的申请释放带来一定的时间开销。在软考选择题中，凡是涉及栈是否需要预先确定容量、是否可能上溢的判断，都可以从这一对比出发得出答案。
从时间复杂度的角度看，栈的基本操作入栈和出栈在顺序栈和链栈中都是常数时间。无论栈中已经存放了多少元素，入栈只需要移动栈顶指针并写入一个元素，出栈只需要读取栈顶元素并移动指针，运算量与栈的长度无关。栈顶元素的读取同样可以在常数时间内完成。这一点使栈成为各种算法中频繁使用的临时存储结构，正是因为它的每次操作都足够廉价，函数调用、表达式求值、深度优先搜索才能以可接受的效率运行。
共享栈是顺序栈的一个巧妙变体，值得单独理解。共享栈用一个一维数组的两端分别作为两个栈的栈底，两个栈的栈顶指针向数组中间生长，当两个栈顶指针相遇时数组空间耗尽。这种设计让两个栈共享同一片存储，可以互相调剂空闲容量，特别适合两个栈的元素数量此消彼长的场景，例如表达式求值中操作数栈和运算符栈往往一个涨一个落，使用共享栈能显著提高空间利用率。软考对共享栈的考察通常落在栈空栈满的判断条件上，即两个栈顶指针的相对位置，考生需要记住相遇即满这一核心判据。
栈最深刻的底层应用是函数调用的栈帧（Stack Frame）机制。当程序调用一个函数时，系统会在栈上为这次调用分配一段连续的存储空间，这段空间称为活动记录或栈帧。栈帧中通常保存函数的形参变量、局部变量、返回地址，以及被调用者需要保存的寄存器值。
每当发生一次函数调用，系统就压入一个新的栈帧；每当函数返回，系统就弹出对应的栈帧。这样，函数调用和返回天然地满足后进先出的次序，最后调用的函数最先返回，这与栈的后进先出特性精确吻合。正是栈帧机制让递归成为可能：递归函数的每一次调用都会在栈上压入一个新的栈帧，保存各自的局部变量副本，从而避免各层递归之间的变量互相干扰。栈帧保存的是形参、局部变量、返回地址等本次调用相关的数据，而全局变量存放在静态存储区，不属于栈帧的一部分。真题曾以栈帧中不包括全局变量作为正确选项，考察的正是考生对栈帧内容边界的理解。此外，递归深度过大时会导致栈帧无限增长，最终引发栈溢出，这也是递归为什么可能耗尽内存的底层原因。
从存储实现的角度，栈可以分为顺序栈和链栈两大类，前文已经从存储结构和指针操作两个层面进行了对比。此外还有一种变体——共享栈。共享栈利用一个一维数组的两端分别作为两个栈的栈底，两个栈的栈顶向中间生长。当两个栈的栈顶指针相遇时，说明整个数组空间被耗尽。共享栈的巧妙之处在于，两个栈共享同一块存储空间，可以互相调剂空闲容量，比两个独立栈更能提高空间利用率，适用于两个栈元素数量此消彼长的场景。
从栈的用途角度，还可以划分出一些特殊栈，例如在表达式求值中同时使用操作数栈和运算符栈的双栈结构，以及编译器实现中用于符号表管理、语法分析的状态栈。软考对共享栈的考察较少，但对双栈结构在表达式求值中的应用考察频繁，考生应重点掌握。
栈最经典的应用之一是算术表达式求值。表达式通常有中缀、前缀、后缀三种表示形式。中缀表达式即人们日常书写的形式，运算符位于两个操作数中间，例如十乘以（四十减三十除以五）再加二十。中缀表达式对人类直观，但对计算机不友好，因为需要考虑运算符优先级和括号。后缀表达式（逆波兰表示法）把运算符写在操作数之后，如十 四十 三十 五 除 减 乘 二十 加，计算机用栈可以线性扫描一遍完成求值，无需考虑优先级。
后缀表达式求值的算法是软考计算题的核心：从左到右扫描后缀表达式，遇到操作数就入栈；遇到运算符就从栈中弹出所需的操作数，先弹出的是右操作数，后弹出的是左操作数，执行运算后将结果压回栈中；扫描结束后，栈中唯一剩下的元素就是整个表达式的值。这一过程中栈的最大深度就是操作数栈所需的最小容量。
中缀转后缀则通常借助运算符栈完成：扫描中缀表达式，操作数直接输出，运算符入栈前要与栈顶运算符比较优先级，优先级高则入栈，优先级低则先将栈顶高优先级运算符弹出输出再入栈，左括号直接入栈，右括号则不断弹出运算符直到遇到左括号为止。软考命题人常把中缀转后缀、后缀求值、栈容量计算三件事串成一道综合题，考生需要完整掌握。