很多人在刷Acwing算法基础课的数据结构章节时看到829模拟队列这道题第一反应多半是STL里不就有queue吗为什么还要让我手写一个我当时也是这么想的。直到后来在各种笔试、竞赛和项目里反复吃这个“笨办法”的甜头才真正理解了这道模板题的价值——它不是让你重复造轮子而是逼着你把队列的存储方式和操作逻辑彻底想清楚。这篇文章就把数组模拟队列的完整思路、代码模板、易错点和进阶方向一次讲透适合刚开始刷数据结构的同学也适合想回头巩固基础的选手。1. 为什么算法题里手写队列而不是直接用STL的queue1.1 模板题的定位不是为了“实现一个队列”而是为了“用熟这个数据结构”Acwing算法基础课的模板题都带着一个共同目的把常用的数据结构和算法练到“肌肉记忆”的程度。用STL的queue当然可以AC这道题但你要是真的只调一个queue就交上去等于把最该练的东西跳过了。我举一个很实际的场景。后面学到图的BFS也就是广度优先搜索时你会发现几乎所有BFS模板都会用数组模拟队列而不是std::queue。为什么因为BFS需要记录每个节点在队列中的状态有时候还要对队列里的元素做某些定位操作数组模拟的队列天然支持随机访问你可以随时通过下标qc[head]拿到队头元素甚至直接访问队列中间的元素。STL的queue没这个能力它只暴露了front、back、push、pop四个接口。还有一个更实在的理由学会数组模拟队列之后你能知道队列占用多少内存、队头和队尾指针是怎么移动的、元素到底还在不在数组里。这些细节在调试时非常重要。刷题时最怕的不是思路不对而是程序行为像黑盒一样不可控。数组模拟的队列每一行代码都明明白白出问题了打印一下hh和tt你马上就知道队列处在什么状态。1.2 什么时候应该用数组模拟队列先说结论在算法竞赛、机试和面试手写代码中我几乎不用STL队列而是直接用数组模拟。STL的queue底层默认是deque也就是双端队列。deque为了支持两端插入删除内部实现是一段段的缓冲区不是连续内存。功能很强大但调试时不直观也不方便在队列中间做操作。而数组模拟队列本质就是在连续数组上维护两个指针逻辑极其简单性能也更好没有动态扩容开销。另外STL容器还需要include头文件。竞赛中如果你忘了#include 编译器报错那一瞬间心态很容易崩。而手写数组只需要一个全局数组加两个int变量永远不怕缺头文件。这听起来是很小的事但赛场上一两分钟的慌乱代价可能很大。当然如果是在平时的工程代码里我完全不反对用std::queue那是它的正确使用场景。这里说的“手写队列”是算法训练和竞赛语境下的选择。你需要在两种场景之间切换自如平时工程用STL提升效率刷题训练手写数据结构的底层逻辑。2. 数组模拟队列队头指针和队尾指针是怎么把FIFO撑起来的2.1 思路起点用一个数组加两个下标队列的特点是先进先出英文缩写叫FIFOFirst In First Out。用生活语言说就是排队打饭先来的人排在前面也先打到饭走人。用数组模拟队列核心只需要三样东西一个一维数组int q[N]用来存队列里的元素一个队头下标hh指向当前队头元素在数组中的位置一个队尾下标tt指向当前队尾元素在数组中的位置。初始状态下队列是空的。关键约定是int hh 0; // 队头指向下标0 int tt -1; // 队尾指向下标-1表示队列里没有任何元素为什么队尾初始值是-1而不是0因为数组下标从0开始。如果tt初始为0那就意味着数组下标0处已经有一个元素了但实际上还没有。让tt从-1开始然后入队时先执行tt第一个元素就正好放到q[0]这个位置整个逻辑非常顺。2.2 四种操作的完整语义829模拟队列这道题要求支持四种操作对应队列的核心行为操作含义数组模拟实现时间复杂度push x向队尾插入一个数xq[tt] x;O(1)pop从队头弹出一个数hh;O(1)empty判断队列是否为空hh tt时为空O(1)query查询队头元素输出q[hh]O(1)push操作的核心是tt。每次新元素来队尾下标先向后移动一位然后把新元素写到新位置上。这个过程可以理解成食堂队伍末尾来了个新人他站在了队伍最后面。pop操作则极其简单hh就完了。原因是队列只允许从队头删除元素我们不需要真正清掉那个位置上的数据只要把队头指针向后移动一位逻辑上就相当于把队头元素“放走”了。这就是所谓的“逻辑删除”——数据还在数组里但我们已经不把它当作队列的一部分。empty判断为什么是hh tt因为队列非空时队头下标一定小于等于队尾下标。如果队头跑到队尾右边去了说明队列中间一个元素都不剩了。query操作输出q[hh]也就是当前队头元素。这里不需要移动任何指针只是查看。2.3 为什么说这是一个“逻辑删除”的队列很多初学者会疑惑pop之后那个元素真的没了吗答案是物理上它还在数组里逻辑上它已经“出队”了。举个例子。执行push 1、push 2、push 3后数组状态是下标: 0 1 2 值: 1 2 3 hh0 tt2执行一次pop也就是hh后下标: 0 1 2 值: 1 2 3 hh1 tt2注意q[0]里存的1还在但队列的逻辑内容变成了q[1]2和q[2]3。队头元素是2不是1。所以你查询队头输出的是2符合队列先进先出的语义。这种“逻辑删除”的好处是O(1)复杂度和代码简洁。代价是被pop掉的位置不会被再利用除非你以后实现循环队列。这个问题在第6章会展开。理解了这个机制你会明白为什么数组模拟队列不需要像链表那样写delete节点、释放内存。在算法题里我们用的是静态数组数据规模有限逻辑删除是完全可以接受的。3. 829模拟队列逐行拆解从读入到输出3.1 完整代码模板直接给出一份可以在Acwing上AC的完整代码#include iostream using namespace std; const int N 100010; int q[N]; int hh 0; int tt -1; int main() { int m; cin m; while (m--) { string op; cin op; if (op push) { int x; cin x; q[tt] x; } else if (op pop) { hh; } else if (op empty) { if (hh tt) { cout YES endl; } else { cout NO endl; } } else if (op query) { cout q[hh] endl; } } return 0; }这份代码可以直接提交。我这里用的是cin和cout因为M最大是100000操作量不大关闭同步的cin/cout完全够用。如果你追求极限性能或者你处在竞赛环境里也可以改成scanf和printf逻辑完全一样。3.2 逐段解读从全局变量到操作分发先看全局部分const int N 100010; int q[N]; int hh 0; int tt -1;N取100010是因为题目给出的操作次数最多是100000。由于每次push最多让tt加1整个过程中tt的最大值不会超过100000所以数组大小为100010足够多出的几个位置是安全余量。hh和tt定义成全局变量好处是整个main函数里都能直接访问也免去了传入形参的麻烦。题目保证所有操作合法也就是说不会出现对空队列执行pop或query的情况。在训练阶段其实可以不加防御性判断但在实际工程里最好还是加上队列是否为空的检查。再看main函数里的操作分发string op; cin op;用string接收操作命令然后通过一系列if-else判断。这里要注意的是读取操作命令时的顺序cin op在遇到空格或换行时会自动跳过空白字符所以不用担心换行符残留的问题。判断顺序设为push、pop、empty、query和题目给出的操作顺序一致不容易漏判。其中push操作后面还要跟着一个整数x所以需要额外用cin x读取。3.3 用题目样例完整跑一遍题目样例输入10 push 6 empty query pop empty push 3 push 4 pop query push 6我们用上面的代码手工走一遍把所有中间状态列出来这一步很重要能帮你确认自己是否真正理解了指针的含义。操作hhtt逻辑队列内容输出初始0-1空-push 600[6]-empty00[6]NOquery00[6]6pop10空-empty10空YESpush 311[3]-push 412[3,4]-pop22[4]-query22[4]4push 623[4,6]-最终输出就是NO 6 YES 4对照题目样例输出完全一致。注意一个容易被忽略的细节执行第一次pop之后hh变成1此时队列逻辑上为空后面再push 3和push 4时tt从1继续增加到2q[1]和q[2]被写入。此时hh1tt2逻辑队头是q[1]3。再执行一次pop后hh变成2队头变成q[2]4。整个过程中数组里的旧值其实都还在但指针决定了哪些位置属于队列。如果你自己运行结果不对最好的排查方式就是在每个操作后打印hh和tt。看到两个指针的值基本一眼就能定位问题。3.4 时间复杂度分析四种操作都是O(1)整个程序的复杂度就是O(M)M是操作次数。空间上只开了一个长度为N的数组所以空间复杂度O(N)。这个复杂度已经是最优的了因为每个操作无论怎么设计都必须至少O(1)时间来完成最基本的入队和出队。要知道很多看似复杂的数据结构核心操作如果能做到O(1)就能支撑很大的数据规模。M最多100000O(M)的复杂度在各类在线评测系统中都是秒过。4. 模拟队列最容易踩的坑初始化、判空和输入解析4.1 hh和tt的初始值到底怎么定这是新手最容易搞混的地方。我见过太多代码初始化写成int hh 0, tt 0;结果第一个元素存到q[1]而不是q[0]后面判空逻辑也跟着错。830模拟栈的模板里栈顶指针通常初始化为0而829模拟队列的队尾指针初始化为-1。为什么同样是数组模拟一个从0开始一个从-1开始原因在于栈的操作集中在同一端用stk[tt] x和tt--tt从0开始判空条件是tt 0非常自然。队列有两个指针队头的0有实际含义——它指向第一个元素应存放的位置。如果队尾也从0开始就需要额外的标志位来区分空队列和有元素的状态反而麻烦。所以记住一组固定的约定hh 0, tt -1。这一组约定里push用q[tt]pop用hh判空用hh ttquery用q[hh]。四个操作互相配套不要随意改动其中任何一个。4.2 empty判定为什么是hh tt而不是hh tt这个坑非常典型。假设队列里只有一个元素此时hh2tt2。如果你用hh tt判空会错误地认为队列为空但实际上q[2]这个位置上还有元素。正确的判空条件是hh tt也就是队头指针越过了队尾指针才能说明队列中一个元素都没有。总结成一句话当队列内至少有一个元素时队头下标一定小于等于队尾下标。所以只要hh tt队列就一定非空只有hh tt时才是空队列。如果你调代码时发现empty输出结果总是刚好相反先检查这个条件是不是写成了等号。4.3 读入操作的细节字符串比较与输入缓冲区我再分享一个很多人踩过的坑如果用scanf(%s, op)读取操作名op是一个char数组那么判断时一定要用strcmp(op, push) 0不能用op push。因为后者比较的是两个地址永远不可能相等。用string类型就完全没有这个问题op push直接比较内容。所以我的建议是用C就老老实实string op; cin op;判断方便也不容易出错。用C语言风格读char数组也可以但一定要记得用strcmp。这两种写法在829这道题里都能AC差别不大主要看你自己习惯了哪种风格。还有一个细节如果操作命令不是push就不用读取后面的整数x。代码里我把cin x放在op push分支内这样其他操作不会错误地吞掉后续的输入。4.4 数组大小与空间估算N的定义要保证足够大。操作次数最多是100000每次push最多让tt增加1所以tt最多到99999或者100000左右。数组开100010是稳妥的。如果你开成100000整理论上也够但加上一个很小的安全余量能避免一些边界问题。养成数组多开几个的好习惯后面写邻接表、并查集等结构时也是这样。这里多提一句。数组模拟队列的代码里q[tt] x这条语句是不检查数组是否越界的。虽然题目保证操作合法但如果你在调试时自己造了超范围的数据可能会访问越界产生难以预料的结果。所以自己测试时要先估算好数据规模或者临时加一个if判断打印提示调试完再删掉。5. 与模拟栈对照着学数据结构基础才稳5.1 数组模拟栈的标准模板数据结构里栈和队列总是成对出现。把这两个模板放在一起对比你会发现很多规律。数组模拟栈的标准代码是const int N 100010; int stk[N]; int tt 0; // 注意栈顶指针从0开始 // push stk[tt] x; // pop tt--; // empty if (tt 0) { // 栈空 } else { // 栈非空 } // query 栈顶 cout stk[tt] endl;栈的特点是后进先出LIFO操作只在一端进行所以只需要一个栈顶指针tt。5.2 队列和栈的核心差异两个指针与一个指针的区别我把两个模板放在一起对比项目数组模拟栈数组模拟队列指针栈顶指针tt队头指针hh、队尾指针tt初始状态tt 0hh 0, tt -1pushstk[tt] xq[tt] xpoptt--hh判空tt 0hh tt查询stk[tt]q[hh]特性LIFOFIFO从表格里能清楚看到队列比栈多了一个队头指针所以需要两个下标来维护区间[hh, tt]。这个区间范围内的元素就是当前队列中的有效元素。而栈只需要一个指针因为操作始终围绕栈顶进行。很多初学者会混淆这两者原因在于push语句非常相似。记忆的方法是队列的push操作q[tt]动的是队尾查询操作q[hh]动的是队头而pop操作hh动的是队头栈的所有操作都动同一个栈顶指针tt。理解了这一点就不会写混。5.3 用随机数据验证你的队列模板这里分享一个我很推荐的训练方法。写完队列模板后不要只提交到在线评测系统还可以自己写一个对拍程序验证。步骤如下写一个测试程序随机生成M个操作操作在push、pop、empty、query中随机选择把你用数组模拟队列的代码和STL的std::queue同时跑一遍两个程序输出的结果逐行比对如果不同说明你的模板有隐藏bug。对拍是竞赛选手非常熟悉的调试手段。平时练模板题时养成对拍的习惯后面写复杂算法时遇到莫名其妙的bug就能用这个思路快速定位。6. 从模拟队列延伸开循环队列与单调队列6.1 假溢出问题怎么治前面提到数组模拟队列有个明显的局限性随着pop操作的进行队头指针hh不断后移队头前面被释放的位置永远无法再使用。如果队列是一侧不断增加、另一侧不断出队数组空间会越来越紧张即使队列里实际元素很少。这被称为“假溢出”。解决办法是循环队列。假设数组长度为N当队尾指针到达数组末尾时让它回到开头继续使用。代码层面只需要在指针移动时取模// 入队 tt (tt 1) % N; q[tt] x; // 出队 hh (hh 1) % N;循环队列有两个关键判断判空hh tt判满(tt 1) % N hh。为什么判满要用(tt 1) % N而不是tt hh因为如果队尾和队头指向同一个位置既可以表示空也可以表示满会出现二义性。常用做法是牺牲一个存储单元当队尾的下一个位置是队头时就认为队列已满。这样判空和判满就区分开了。不过在829这道题以及绝大多数算法题里我们不需要循环队列。只要数组足够大每次操作都会在有限范围内移动指针假溢出不会导致错误。循环队列更多用在固定缓冲区等工程场景里。作为数据结构的学习者你要知道这个知识点但现阶段不用过度深挖。6.2 单调队列是一个更值得关注的进阶方向和模拟队列最相关的进阶知识是单调队列。Acwing基础课里紧接着就会遇到154滑动窗口这道题用单调队列求窗口内的最大值和最小值。单调队列的核心思想是在入队时把破坏单调性的队尾元素弹出从而保证队列中的元素按某种顺序单调排列。因为每个元素最多入队一次、出队一次整体时间复杂度仍然是O(n)。以数组模拟的写法为例用双端队列的思路int a[N], q[N]; // a存原数组q存下标 int hh 0, tt -1; for (int i 0; i n; i) { // 队头元素如果已经滑出窗口出队 if (hh tt q[hh] i - k 1) hh; // 保持单调性队尾元素比当前值小时出队以维护递增队列为例 while (hh tt a[q[tt]] a[i]) tt--; q[tt] i; // 窗口满k个元素后队头就是最小值 if (i k - 1) cout a[q[hh]] ; }这段代码看起来复杂但它里面用到的hh、tt、q[tt]、hh全部是从829模拟队列中来的。你如果把829的模板吃透了到这里会感觉非常亲切几乎是无缝衔接。这也是为什么基础课的顺序要先把模拟队列放前面的原因。刷题这件事最怕的就是贪多嚼不烂。829模拟队列这种模板题看着简单但它的价值不在题目本身而在于为后续的BFS、单调队列、以及各种以队列为底层结构的高级算法打地基。我个人带新人时总让他们把这段模板默写三遍第一遍对照着抄第二遍合上书自己写第三遍直接盲写并且把四种操作的原因讲清楚。三遍过去后面碰到任何需要队列的题基本不会卡壳。最后分享一个小习惯每次刷到新的数据结构模板我都把它的初始值、关键操作、判空条件记在一张表格里攒到一起反复看。等你看熟了这些模板就不再是死代码而是能随手拿出来用的工具了。