扫码获取 VIP 码
添加管理员微信获取 VIP 码
在软考软件设计师、软件评测师等科目的数据结构选择题中，栈与队列是出现频率最高、却最容易被考生轻敌的一类知识点。很多人觉得栈就是后进先出、队列就是先进先出，两句话就背完了，结果一到考场上，面对"下列哪个出栈序列不可能出现"和"循环队列队满时牺牲了一个存储单元"这类题目，照样频频出错。本文不从生活类比讲起，而是回到数据结构的本质定义，把栈与队列的存储实现、关键判定公式、应用场景和命题人挖坑的套路一次性讲透，让你把这部分送分题稳稳拿到手。
在数据结构教材中，栈与队列的定义有着严格的学术表述，而这两句话恰恰是后续所有计算题和判断题的出发点。栈是限定仅在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底，不含任何元素的空表称为空栈。队列则是只允许在一端进行插入操作、在另一端进行删除操作的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。
这里需要强调的是，栈和队列都不是独立于线性表之外的另一种数据结构，而是对线性表施加了操作限制后得到的特殊形态。线性表本身允许在任意位置插入和删除，而栈把插入和删除都约束在同一端，队列则把插入约束在队尾、删除约束在队头。正是这种操作约束，催生了后进先出和先进先出这两种截然不同的逻辑特性。后进先出通常记作 LIFO，即最后进栈的元素最先出栈；先进先出通常记作 FIFO，即最早进入队列的元素最先离开队列。
理解这一定义的关键在于，栈和队列的"逻辑特性"与"存储实现"是两回事。后进先出、先进先出描述的是元素的操作次序，属于逻辑层面的规则；而究竟是采用顺序存储还是链式存储来落地这个规则，属于物理层面的实现选择。许多考生混淆了这两个层次，一提到栈就条件反射地想到数组，一提到队列就想到循环数组，实际上链栈和链队列同样存在，而且同样满足后进先出和先进先出的逻辑约束。把逻辑与物理两层剥离开来，是攻克这一知识点的第一道关卡。
从抽象数据类型的角度看，栈提供了一组标准操作，软考常直接考查这些操作的名称与语义。初始化栈建立一个空栈，判栈空判断栈中是否没有元素，判栈满判断栈的存储空间是否已被占满，入栈在栈顶插入一个新元素，出栈删除栈顶元素并返回其值，读取栈顶元素则只返回栈顶值而不删除。其中"出栈"与"读取栈顶元素"的区别是选择题的经典考点，前者会改变栈的状态，后者不改变栈的状态。队列的抽象数据类型与之类似，包括初始化、判队空、判队满、入队、出队和取队头元素等操作，取队头元素同样不改变队列状态。命题人常把"删除并返回"与"仅返回不删除"混在一起来考，考生必须分清这两个操作对结构状态的影响。
初学者常疑惑，线性表功能明明更强大，为何还要研究栈和队列这两种受限结构。答案是约束本身带来了可预测性和安全性。当操作被限制在特定端点时，数据被处理的次序就变得确定且可控，这恰恰是程序正确性的基础。后进先出保证函数调用能正确返回，先进先出保证任务能公平按序处理。这种"以牺牲灵活性换取确定性"的设计思想，贯穿了计算机科学的许多领域，理解这一点，才能真正理解栈与队列存在的意义，而不只是机械记忆两句口诀。
栈与队列的原理机制，核心在于"指针如何移动"以及"空间如何复用"这两个问题。只有把指针的初始值、移动方向、判定条件彻底弄清楚，才能真正理解那些看似简单的公式背后的含义。
顺序栈用一段连续的存储空间存放栈元素，同时用一个栈顶指针指示当前栈顶的位置。对于数组下标从零开始的顺序栈，若栈底固定在下标为零的位置，栈顶指针初始值通常设为负一，表示空栈。元素入栈时，指针先加一再放入元素；元素出栈时，先取出指针所指元素，指针再减一。这个"先加一再入、先出再减一"的顺序一旦记反，就会在入栈出栈的模拟题上栽跟头。当栈顶指针的值等于存储空间长度减一时，表示栈已满，此时再入栈就会发生上溢；当栈顶指针为负一时表示栈空，再出栈就发生下溢。
栈的上溢与下溢在考试中有明确的区分。上溢是由于栈的存储空间已经用完、仍然试图入栈所造成的溢出，属于存储空间不足的问题；而下溢则是空栈时仍执行出栈操作，属于逻辑错误。软考命题人经常利用这一点设置陷阱，把"入栈时栈满"和"出栈时栈空"两种异常的性质混在一起考。判断时只需抓住一个原则：上溢关乎空间，下溢关乎逻辑。
还有一种值得注意的形态是多栈共享空间。两个栈共享同一段存储空间时，通常采用"栈底相向、栈顶相对"的布局，即两个栈的栈底分别位于存储空间的两端，栈顶向中间增长。这种布局能充分利用空间，避免某个栈已满而另一个栈仍有大量空闲的浪费。软考偶有考查双栈共享空间的题目，判断某个栈是否满时，依据是两个栈顶指针是否相邻。理解这种布局，有助于深化对顺序栈指针机制的认识。
顺序队列如果采用"队尾入、队头出"的朴素实现，出队后队头空间被闲置，而队尾指针不断后移，会出现"假溢出"现象，即队尾指针到达数组末尾但队头前面仍有空闲空间。为解决假溢出，循环队列把存储空间在逻辑上首尾相连，使队头和队尾指针可以循环移动。循环队列的队空和队满判定是整个数据结构的难点，也是选择题的高频考点。
循环队列通常有两种判定策略。第一种是牺牲一个存储单元，约定队尾指针加一后若与队头指针重合即视为队满，此时队空条件是队头指针等于队尾指针，队满条件是队尾指针加一后对队列长度取模等于队头指针。第二种是设置一个计数器记录队列中的元素个数，队空时计数器为零，队满时计数器等于队列容量。两种策略各有优劣，前者省去计数器但浪费一个存储单元，后者充分利用空间但每次操作都要额外维护计数变量。考试中牺牲一个存储单元的策略出现频率更高，考生务必记清"队空队满判定公式中取模"这一关键步骤。
循环队列中元素个数的计算是另一个常考点。其通用公式为：队尾指针减队头指针加容量，再对容量取模。之所以要加容量再取模，是为了处理队尾指针在数值上小于队头指针的情况。举个例子，容量为十的循环队列，队头指针指向下标二、队尾指针指向下标七，元素个数为七减二等于五；若队头指针指向下标七、队尾指针指向下标二，则元素个数为二减七加十等于五。两种情况都套用同一公式，加容量再取模这一步保证了结果的非负性，是考生最容易省略的一步。
链栈以链表方式实现，栈顶即链表的表头，入栈相当于在表头插入结点，出栈相当于删除表头结点，因此链栈不存在栈满的问题，除非系统内存耗尽。链队列则通常需要同时维护队头指针和队尾指针，入队操作在队尾指针处插入结点并更新队尾指针，出队操作删除队头结点并更新队头指针。链队列需要特别留意的一点是，当队列中仅剩一个元素且执行出队后，队尾指针会悬空，必须将队尾指针也重置为空，否则后续入队会出现指针错误。这一细节是链队列操作题中的经典陷阱。
栈与队列的应用场景极其广泛，软考不仅考它们的定义和计算，还经常结合具体应用场景考查考生的理解深度。掌握这些应用，既能帮助考生记忆特性，又能应对应用题型的变体。
栈最经典的应用是表达式求值。中缀表达式如"三加四乘五"由于存在运算符优先级，直接计算困难，编译器和计算器通常将其转换为后缀表达式，也就是逆波兰表达式，再利用栈进行求值。转换过程用到一个运算符栈，遇到操作数直接输出，遇到运算符则与栈顶运算符比较优先级，优先级不高于栈顶时弹出栈顶输出，最终得到后缀表达式。求值过程用一个操作数栈，遇到操作数入栈，遇到运算符则弹出两个操作数运算后再入栈。整个流程充分体现了栈后进先出的特性，是软考下午算法题和上午概念题都喜欢考查的内容。
递归调用同样依赖栈。程序在执行递归函数时，每一次递归调用都会在系统栈中压入一个栈帧，保存该次调用的局部变量、参数和返回地址，递归返回时依次弹出。正因为递归本质上是栈的运用，任何递归算法都可以改写为显式使用栈的迭代算法。软考
本篇完！