扫码获取 VIP 码
添加管理员微信获取 VIP 码
队列是一种操作受限的线性表，它的核心存取规则可以概括为"先进先出"四个字。与栈"后进先出"的存取规则相反，队列只允许在表的一端进行插入操作，在另一端进行删除操作。允许插入的一端称为队尾，通常用指针rear来标识；允许删除的一端称为队头，通常用指针front来标识。教材和标准文档中对队列给出的正式定义是：队列是只允许在一端进行插入、在另一端进行删除的线性表，插入元素的操作称为入队，删除元素的操作称为出队。
理解队列的关键在于把握它"操作受限"这一本质。线性表本身支持在任意位置进行插入和删除操作，而队列通过人为规定"只能队尾进、队头出"，把一个灵活的通用结构约束成了一种具有特定存取顺序的专用结构。这种约束不是为了增加学习难度，而是为了准确模拟现实世界中广泛存在的一种现象，那就是先到先服务。操作系统中的作业排队、打印机的任务队列、进程的就绪队列、消息中间件的消息队列，本质上都是队列结构在发挥作用。
从数据结构的角度看，队列的基本操作只有有限的几种：初始化一个空队列、判断队列是否为空、将元素插入队尾、将队头元素删除、读取队头元素的值但不删除。正是这五种操作构成了队列的全部对外接口。软考对队列的考查，绝大多数都落在顺序存储结构下的循环队列计算题上，因为这里藏着最多的公式推导和最容易出错的计算细节。从时间复杂度的角度看，这五种基本操作的理想实现都是常数级别的，即每次入队、出队、判空、取队头都在常数时间内完成。这一常数时间的特性是队列区别于某些需要线性时间的结构的根本优势，也是它在操作系统调度、网络报文缓存等对时延敏感的场景中被广泛采用的原因。命题人之所以偏爱队列的计算题，恰恰是因为队列的常数时间操作背后隐藏着front与rear两个指针的位置关系，这种位置关系又能在取模运算下演变出多种需要精确计算的状态。
把栈和队列放在一起对比，是理解队列最有效的方式。栈是后进先出的结构，只允许在栈顶一端进行插入和删除，因此它只有一个操作端；队列是先进先出的结构，插入在队尾、删除在队头，因此它有两个操作端。这一端的差异直接导致了二者指针管理方式的不同：栈只需要一个栈顶指针top，而队列需要front和rear两个指针。
在存储实现上，栈的顺序存储不会产生"假溢出"问题，因为栈顶指针在元素出栈时是向前回退的，空闲空间可以被立即复用；而队列的顺序存储则因为rear指针只能单向向前移动，必然产生假溢出的隐患。正是这一差异，催生了循环队列这种特殊结构。理解栈和队列的这一演化关系，就能理解为什么循环队列会专门引入取模运算这一看似多余的机制。
队列有两种基本的存储实现方式：顺序存储结构和链式存储结构。顺序存储结构使用一段连续的存储空间（即数组）来存放队列中的元素，并用front和rear两个指针来标识队头和队尾的位置；链式存储结构则用链表节点来表示队列元素，队头指针指向首节点，队尾指针指向末节点。软考计算题主要集中在顺序存储这一实现上。
顺序存储的队列在实际使用中会暴露出一个著名的问题，那就是假溢出。所谓假溢出，是指队列在数组空间中"看似已满、实则未满"的异常状态。假设我们用一个长度为六的数组来存储队列，初始时front和rear都指向下标零的位置。当元素一个接一个入队时，rear不断向后移动，直到rear移动到数组的末尾下标五。此时如果front前面（下标零、一等位置）已经因为出队而空出了位置，但rear却已经无路可走，新的入队操作就会因为数组越界而被拒绝。然而此时数组中明明还有空闲位置，队列并没有真正装满，这就是假溢出。
假溢出的本质在于：顺序队列的rear指针只能单向移动，它把"数组末尾"错误地当成了"队列末尾"。解决假溢出的思路有两种：第一种是每出队一个元素就把剩余元素整体向前移动一位，这种方案虽然直观但效率极低，每次出队的时间复杂度会退化为线性级别；第二种更优雅的方案就是引入循环队列，把数组在逻辑上首尾相接，让rear指针在到达数组末尾后可以绕回到数组开头继续使用空闲空间。循环队列正是为解决假溢出而生的。
循环队列的核心思想是打破顺序存储"一维线性"的思维定式，把存储队列的数组在逻辑上首尾相接，构造出一个环形的存储空间。实现这一逻辑环的关键工具是取模运算。假设数组的容量为maxSize，那么rear指针和front指针在移动时不再简单地执行加一操作，而是执行"加一后对maxSize取模"的操作。
具体而言，入队操作把新元素放入rear指向的位置，然后rear执行加一后再对maxSize取余的操作；出队操作取出front指向的元素，然后front执行同样的取模移动。这样一来，当rear指向数组最后一个位置并再次移动时，取模运算会让它自动回到下标零的位置，从而实现指针的循环移动。这个绕回的动作用一行公式就可以表达清楚，也正是循环队列区别于普通顺序队列的根本所在。
取模运算在这里扮演的是"边界回卷器"的角色。可以把它理解为把一条直线的两端粘起来形成一个圆环，指针在这个圆环上不停地转圈，永远不会越界。理解了这一点，循环队列的种种公式就不再是需要死记硬背的咒语，而是有着清晰几何直觉的必然结论。
循环队列的计算题能否做对，第一步取决于是否清楚front和rear两个指针的语义约定。软考中约定最普遍的一种方案是：front指向队头元素本身，rear指向队尾元素的下一个空位置。在这种约定下，front和rear的初始值都为零，入队时先把元素存入rear位置再移动rear，出队时先取出front位置的元素再移动front。
这里有一个极其容易被忽略的细节：因为rear指向的是队尾元素的下一个空位置，所以当front等于rear时，队列中实际上没有元素，队列为空。这一约定直接决定了后面判空、判满和计算元素个数三套公式的推导，任何一套公式都建立在这套指针语义之上。如果题目换了一种约定（比如规定rear直接指向队尾元素本身），那么对应的公式也要随之改变，考生必须根据题干给出的约定来套用公式，而不能死记硬背某一种默认结论。
在牺牲一个存储单元的经典方案下，入队和出队的完整算法步骤可以精确描述如下。入队操作首先要判断队列是否已满，判满条件是rear加一再对maxSize取模后等于front；若未满，则把新元素存入rear指向的位置，然后执行rear等于rear加一再对maxSize取模的移动操作。出队操作首先要判断队列是否为空，判空条件是front等于rear；若未空，则取出front指向的元素，然后执行front等于front加一再对maxSize取模的移动操作。
这两组步骤高度对称，理解一次即可同时掌握入队和出队。需要特别注意的是操作顺序：入队是先存元素再移动指针，出队是先取元素再移动指针。如果颠倒顺序，就会导致元素被覆盖或者指针指向错误。软考真题中出现的"模拟入队出队序列"类题目，本质上就是在考查考生能否严格按照这两组步骤逐步推演指针的变化。
这里可以进一步说明取模运算在指针移动中的精确含义。假设数组容量maxSize为六，rear当前等于五，此时若发生入队，新元素存入下标五的位置后，rear执行五加一再对六取模，结果为零，指针绕回到数组开头。这个从五跳到零的过程就是取模运算发挥边界回卷作用的典型时刻。如果考生在此处漏掉了取模而只做加一，rear就会变成六，指向一个并不存在的下标，后续的所有计算随之全部出错。因此可以毫不夸张地说，取模运算是循环队列全部计算题的命门，抓住了取模就抓住了这类题目的解题主线。
循环队列最经典的实现方案是牺牲一个存储单元来区分队空和队满。在这种方案下，队列的最大可用元素个数是maxSize减一，即数组容量为六的循环队列最多只能存放五个元素，永远保留一个空位不用。之所以要牺牲一个单元，是因为如果不牺牲，队空和队满都会表现为front等于rear，二者无法区分。
在牺牲一个单元的方案下，队空的判定条件是front等于rear；队满的判定条件是rear加一再对maxSize取模的结果等于front。用更直观的语言表达就是：当rear的下一个位置就是front时，队列已满。这个"下一个位置"正是通过取模运算来判定的，它保证了rear在数组末尾时也能正确判断出"下一个位置"其实是下标零。
另一种实现方案不牺牲存储单元，而是额外引入一个计数变量count或者一个标志位flag来区分队空和队满。设置计数变量的方案最为直观：每次入队时count加一，每次出队时count减一，队空的条件是count等于零，队满的条件是count等于maxSize。这种方案能让循环队列的可用空间达到满额，但代价是多维护了一个计数变量，入队和出队时都要额外更新它。
设置标志位flag的方案则是用
本篇完！