栈与队列是数据结构科目里最基础也最常考的两类线性结构。在软考官方教材中，栈被定义为一种限定仅在表尾进行插入和删除操作的线性表，允许插入与删除的那一端称为栈顶，另一端则固定不动，称为栈底。栈的插入操作通常称作入栈或压栈，删除操作称作出栈或弹栈。由于数据只能从栈顶进出，先进入的元素反而后离开，因此栈具有后进先出的特性，英文缩写为 LIFO，即 Last In First Out。这个特性是栈所有应用场景和所有命题陷阱的根源，读者务必先把这个约束刻进记忆里，后面几乎每道题的解法都能回到这个特性上来。
队列的定义与栈形成对称。队列是只允许在表的一端进行插入、在另一端进行删除的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。队列的插入通常称为入队，删除称为出队。由于数据只能从队头离开、从队尾进入，先进入的元素先离开，因此队列具有先进先出的特性，英文缩写为 FIFO，即 First In First Out。栈与队列本质上都属于线性表的特例，它们的区别不在存储方式，而在于操作规则被人为加了限制，正因为加了这个限制，才能用它们来精确刻画现实世界中按顺序推进的处理过程。
理解这两个结构，关键在于把握三点。第一，它们都是线性结构，逻辑上元素之间存在一对一的前驱后继关系，与树、图这类非线性结构有本质区别。第二，它们的受限性是人为规定的操作约束，而不是存储物理上的限制，同样的数据放在内存里，既可以按栈的方式访问，也可以按队列的方式访问。第三，栈强调后进先出，队列强调先进先出，这两个顺序特征是解题时判断输出序列是否合法的唯一标尺。把这三层含义吃透，栈与队列就不再是死记硬背的名词，而是一套可以推导的规则体系。
顺序栈是用一片连续的内存空间实现的栈，通常用一个数组来存储数据元素，同时用一个整型变量作为栈顶指针，指示栈顶元素所在的位置。在软考的题目里，栈顶指针有两种约定方式，这一点是考生最容易混淆的地方。第一种约定是栈顶指针指向栈顶元素本身，此时初始化时栈为空，指针通常置为负一，入栈时先将指针加一再存入元素，出栈时先取出元素再将指针减一。第二种约定是栈顶指针指向栈顶元素的下一个空位，此时初始化时指针置为零，入栈时先在指针位置存元素再将指针加一，出栈时先将指针减一再取出元素。两种约定的差别在于指针指向的对象不同，导致加一减一的先后顺序恰好相反，考生在做计算题和看代码题时必须先判断题目采用哪种约定，否则很容易在边界处算错。
顺序栈的入栈和出栈操作在时间上都是常数级的，也就是 O(1) 的时间复杂度，因为无论是压入还是弹出，都只是对栈顶指针做一次加减并访问一个数组元素。这种高效是顺序栈最大的优势，也是它被广泛用于表达式求值、函数调用等场景的原因。但顺序栈也有天然的短板，那就是容量固定，一旦入栈的数据超过了预先分配的数组大小，就会发生上溢，栈满后继续入栈属于非法操作；反过来，当栈为空时继续出栈，就会发生下溢，同样属于非法操作。软考命题人很喜欢在栈满和栈空这两个边界条件上设置陷阱，考生要养成先判断边界再操作的习惯。
判断顺序栈是否满、是否空，同样依赖栈顶指针的约定。以栈顶指针指向栈顶元素本身的约定为例，假设栈的最大容量为 n，那么当栈顶指针等于 n 减一时，栈处于满的状态；当栈顶指针等于负一时，栈处于空的状态。若采用栈顶指针指向下一空位的约定，栈满时指针等于 n，栈空时指针等于零。两套公式不能混用，这是顺序栈这一节里最容易在选择题里失分的细节。
链栈是用链表实现的栈，其逻辑结构与单链表几乎一致，只不过插入和删除都被限定在链表头这一端进行。链栈通常不设头结点，直接用头指针指向栈顶结点，入栈操作相当于在链表头部插入一个新结点，出栈操作相当于删除链表头部的结点。由于操作始终集中在头部，链栈的入栈和出栈时间复杂度同样都是 O(1)，并且它不受固定容量的限制，只要内存允许，理论上可以一直入栈，不会出现顺序栈那种因数组耗尽而产生的上溢。
链栈与顺序栈的取舍，本质上是在空间利用率和操作灵活性之间的权衡。顺序栈的优点是存储密度高，不需要额外的指针域，且入栈出栈操作简单、速度快；缺点是容量固定，存在上溢问题，而且当栈的元素数量变化很大时，预先分配的空间可能造成浪费。链栈的优点是不存在上溢问题，容量可动态扩展，且多个栈可以灵活共享内存空间；缺点是每个结点都要额外占用一个指针域，存储密度低于顺序栈，同时访问栈顶之外的元素不够方便。软考在选择题里常让考生辨析这两者的优缺点，答案的关键就在于抓住顺序栈的定容与链栈的指针开销这两条主线。
队列如果用顺序存储来实现，会面临一个经典的问题：普通的顺序队列在反复入队出队之后，队头前面的空间虽然空出来了，却无法再被利用，形成所谓的假溢出。假溢出的本质是队头指针不断后移，而队尾指针已到达数组末尾，此时数组前面明明有空位，却无法继续入队。为了解决假溢出，人们把顺序队列的存储空间在逻辑上首尾相接，形成一个环形，这就是循环队列。在循环队列中，队尾指针到达数组末尾后，通过取模运算回绕到数组开头，从而让空出来的空间得到复用。
循环队列的核心机制是取模运算。设队列的存储空间容量为 M，那么无论是队头指针还是队尾指针，在移动时都要用加一后对 M 取模的方式来处理，即指针等于（指针加一）对 M 取余。这样做可以让指针在到达末尾后自动回到起点，实现环形回绕。取模运算贯穿循环队列的所有计算题，无论是求队列当前长度、判断队空还是判断队满，都要回到取模这个机制上来，考生必须把这条公式彻底吃透。
循环队列里队头指针和队尾指针同样存在指向元素本身与指向下一空位两种约定，软考题目中常见的是队头指针指向队头元素、队尾指针指向队尾元素的下一个位置。在这一约定下，队列的长度可以用（队尾指针减队头指针加容量）再对容量取模的公式求得，这个公式把负数和正数两种情况统一起来，是计算队列元素个数的标准解法。考生务必记住，长度计算离不开取模，直接做减法而不取模，在指针回绕之后就会得到错误的结果。
栈的后进先出特性，恰好与计算机系统中许多天然具有后进先出语义的过程相吻合，因此栈拥有极为广泛的应用。第一个经典应用是函数调用与递归。当程序调用一个函数时，系统会把返回地址、局部变量、参数等信息压入调用栈，函数执行完毕后，再按相反的顺序弹出，从而正确地返回到调用点。递归之所以能工作，正是因为在每一层递归调用时都会把当前状态压栈，逐层深入，再逐层返回，这个压栈与弹栈的过程天然符合后进先出的顺序，因此递归可以用栈来模拟，栈也可以用递归来等价实现。
第二个经典应用是表达式求值。中缀表达式对人友好但难以直接被计算机按优先级计算，通常的做法是借助两个栈，一个操作数栈、一个运算符栈，通过比较运算符的优先级来决定是压栈还是弹栈计算，从而把中缀表达式转换为后缀表达式再求值，或者直接在后缀表达式的求值过程中只用一个栈来完成。后缀表达式也叫逆波兰表达式，它的运算符出现在操作数之后，求值时遇到操作数就压栈，遇到运算符就弹出所需的操作数进行计算，再把结果压回栈，整个过程无需考虑括号和优先级，这是栈应用中最能体现后进先出价值的地方。
第三个经典应用是括号匹配。检查一段代码或表达式中左右括号是否配对，可以借助栈来完成，遇到左括号就入栈，遇到右括号就检查栈顶是否是对应的左括号，是则弹出，否则匹配失败，最后栈为空才说明全部匹配成功。这个应用直观地展示了栈在成对出现、嵌套结构校验中的不可替代性。第四个经典应用是进制转换与回溯。把一个十进制数转换成二进制，采用除二取余法，余数从低位到高位产生，但输出需要从高位到低位，正好用栈来反转顺序；回溯算法在试探某条路径失败后，需要回退到上一个状态，也天然依赖栈来保存历史状态。这四个应用场景是软考选择题和简答题反复出现的高频素材。
队列的先进先出特性，决定了它适合处理需要按到达顺序依次处理的任务。第一个典型应用是操作系统中各种等待队列，例如进程就绪队列、打印任务队列、消息队列等，先到达的任务先被服务，这正是 FIFO 的直观体
本篇完！