看到w11必做题1买房必做2队列这个标题估计不少人第一反应是买房这也能当编程题等翻到题目原文就明白了这根本不是让你真的去研究房价和购房政策而是让你用队列这个最基础的数据结构去模拟一场排队买房的过程。必做2更直接让你亲手实现一个队列。两道题一前一后放在同一周的作业里就像是老师精心安排的先给你造轮子再让你用轮子跑一趟路。说实话这个组合在数据结构的作业里是经典中的经典但每年照样有一批同学在同一个地方翻车。翻车的原因不是不会写代码而是没有把队列到底在模拟什么这件事想清楚。这篇文章就把这两道题从读题、建模、编码、调试到提交检查一条线完整拆开来讲。正在写这周作业的同学可以照着一步步操作已经写完但想优化一下的同学也能在里面找到不少细节上的启发。1. 先看懂出题人把两道题放在一起的意图1.1 必做2的队列考的是基本功队列这个东西定义三句话就能说完先进先出只允许在队尾插入只允许在队首删除。很多同学一看到定义这么简单心里就放松了觉得这周作业肯定是送分题。但真正动手写队列的时候才发现事情没那么简单。队列的底层实现主要有两条路一条是用数组把逻辑上的环形结构落在连续的物理空间上另一条是用链表每个元素动态分配一个结点。数组实现最大的坑是假溢出——你明明把元素出队了数组前面的空间空着队尾指针却已经跑到数组末尾再往后就写不进去了。解决这个问题课堂上通常会提到循环队列的思路让队尾指针在到达末尾之后取模回绕到开头。而回绕这个动作恰恰是好多人第一次写代码时最容易漏掉的地方。链式队列相对数组队列来说不需要考虑取模回绕但它的坑在于指针操作的顺序。先改头结点还是先改尾结点什么时候要把头尾都置空出队到最后一个元素时如果只把头指针往后挪、不把尾指针清掉后面一定会出问题。这些细节不亲手写一遍光看课本是体会不到的。所以必做2虽然叫实现一个队列但它真正考查的是你对存储结构的理解、对边界条件的敏感程度以及最基本的代码组织能力。这三样东西恰恰是后面所有复杂数据结构的学习地基。1.2 必做1的买房考的是建模能力再来看必做题1的买房问题。抛开题目里那些业务包装核心场景其实是这样一个售楼处一队购房者在排队每个人来了之后要办一段时间业务才能离开你要把一个购房者的完整过程用程序模拟出来。这个场景里天然就存在着一个队列队伍里先来的人站在前面后来的人排在后面办完业务的人从队首离开新到的购屋者从队尾加入。整个过程中没有人插队没有人中途跑掉也没有人从队伍中间被拽出来——这正好是先进先出这个约束的完美体现。拿栈来对比一下就懂了。如果这个场景用的是栈那就意味着最后到达的购房者反而最先办理业务这既不符合现实也不是题目想要你做的。出题人把场景设计成买房排队就是希望你一眼能识别出这是一个队列场景然后能把这个场景抽象成数据结构里的操作。抽象能力是上机作业里最核心的东西你写的那些变量、类、循环本质上都是对现实世界的一种映射。1.3 两题合在一起的目的把两道题放在同一周并不是巧合。先实现一个队列再用这个队列或者直接用标准库里的队列去解决买房排队问题这是一个完整的从造轮到用车的闭环。先写实现你知道了队列内部是怎么转的再写应用你知道了队列在真实场景里是怎么被调用的。很多同学做完第一道题就急着交结果第二道题直接用了标准库的队列类写完自己也说不出队列空、队列满的时候到底发生了什么。我的建议是哪怕必做2已经提交了也最好把两道题当作一个整体来复盘。自己实现一遍队列然后在买房问题里亲手调用自己写的队列再跑一遍你会对队列的接口设计有完全不同的感受。为什么标准库里的方法名要叫offer和poll而不是add和remove为什么判空的方法叫isEmpty这些名字不是随便取的它们都在暗示队列在使用时的语义边界。2. 必做题1买房排队模拟的完整拆解2.1 先把题目边界读明白不同学校里这道题的描述不完全一样但核心要素基本一致输入若干个购房者的到达时间和办理时间模拟一个服务窗口的排队过程输出每个购房者的等待时间再算一下平均等待时间。有些版本还会加一个房源数量有限卖完为止的条件那就需要额外统计谁买到了、谁没买到。读题阶段最容易犯的错误是把到达时间和开始办理时间混为一谈。到达时间是输入数据开始办理时间是模拟过程中由队列的空闲情况决定的。第一个人可能到了就能立刻办理等待时间为零第二个人如果到达时第一个人还没办完就必须排在后面等。这部分逻辑搞清楚了后面的代码才不会写歪。还有一个容易被忽略的点购房者到达时间的输入顺序。题目一般会保证按到达时间升序给出但如果题目没有明说你最好自己做一个排序预处理。我在批改作业时见过不少同学因为默认输入有序结果测试数据里出现乱序到达就直接出错。稳妥的做法是读入所有购房者之后统一按到达时间排一次序再开始模拟这样无论测试数据长什么样都不会翻车。2.2 建模三个关键角色这个模拟程序的骨架其实就三个东西队列、时钟、待入队的购房者数组。队列负责存储已经到了但还没开始办理的购房者。这里有一个很多人想不通的点为什么要用队列装而不是直接按数组顺序一个一个处理原因在于办理时间是变动的一个办理时间很长的购房者会挡住后面所有人。后面的购房者可能在他办理期间陆陆续续到达他们到达后只能排在队伍里。如果不用队列记录这些积压的人你就没法知道下一个该轮到谁。时钟是模拟的灵魂。它不需要真的每秒走一次而是采用事件驱动的方式每当一个购房者办理完毕时钟就跳到结束时间每当队列空了时钟就跳到下一个到达时间。这种跳跃式推进比逐秒仿真高效得多也符合实际排队场景的逻辑。购房者数组则需要按到达时间顺序存放所有输入数据并且在模拟过程中维护一个索引标明当前已经处理到第几个人了。索引每走一步要么入队一个人要么触发时钟快进不能乱跳。2.3 完整代码与逐段讲解我用Java写一个可以直接运行的版本模拟场景取最简单的情况一个售楼窗口若干购房者每个人只有到达时间和办理时间两个参数。import java.util.LinkedList; import java.util.Queue; public class HouseSaleSimulation { static class Buyer { int id; int arriveTime; int handleTime; int waitTime; Buyer(int id, int arriveTime, int handleTime) { this.id id; this.arriveTime arriveTime; this.handleTime handleTime; } } public static void main(String[] args) { // 测试数据编号、到达时间、办理时间 Buyer[] buyers { new Buyer(1, 0, 4), new Buyer(2, 1, 3), new Buyer(3, 2, 2), new Buyer(4, 5, 1), new Buyer(5, 6, 5) }; QueueBuyer queue new LinkedList(); int index 0; int clock 0; int totalWait 0; System.out.println( 买房排队模拟开始 ); while (index buyers.length || !queue.isEmpty()) { // 第一步把当前时刻以及之前到达的购房者全部入队 while (index buyers.length buyers[index].arriveTime clock) { queue.offer(buyers[index]); index; } // 第二步如果队列为空说明没有等待办理的人 // 时钟直接快进到下一个购房者到达的时刻 if (queue.isEmpty()) { clock buyers[index].arriveTime; continue; } // 第三步队首购房者出队开始办理 Buyer current queue.poll(); current.waitTime clock - current.arriveTime; totalWait current.waitTime; System.out.printf(购房者%d到达时刻%d开始办理时刻%d等待%d分钟%n, current.id, current.arriveTime, clock, current.waitTime); // 第四步时钟前进办理占用这段时间 clock current.handleTime; } System.out.printf(全部办理完成总用时%d分钟平均等待%.2f分钟%n, clock, totalWait / (double) buyers.length); } }这段代码的执行过程我用中间状态演示一下方便你对照理解。初始时clock为0buyers数组中第一个人到达时间为0所以它先入队。队列不为空poll出买家1waitTime 0 - 0 0clock变成4。接着循环回到第一步到达时间小于等于4的买家2和买家3都入队。poll出买家2waitTime 4 - 1 3clock变成7。此时到达时间小于等于7的买家4和买家5入队。之后依次poll出买家3、买家4、买家5。整个过程一共服务5个人最后一个购房者办完时clock是15平均等待时间是(03524)/5也就是2.8分钟。这个逻辑核心就一句话每次进入循环先收割当前时刻之前到达的人再派出队首的人。收割和派出之间的顺序不能颠倒也不能合并。有人会想为什么不在一个循环里同时入队和出队因为同一时刻可能有多个到达者必须先把它们全部放进队列才能保证队首永远是当前时刻最早到达且尚未办理的人。如果上一轮服务结束前就急着出队后到达的人可能抢到前面FIFO就被破坏了。2.4 题目变化限购和多窗口要怎么改如果题目加了只有m套房卖完即止的条件只需要在每次poll之后判断一下已卖出数量是否达到m。达到就停止循环剩下队列里的人标记为未买到。核心逻辑不用动队列本身依然负责维护顺序。如果是多窗口场景比如两个售楼窗口队列就要拆成入口等待队列加多个窗口的完成时间来管理。每次不是简单poll一个然后直接推进clock而是要从多个窗口里选一个最早空闲的窗口处理。这种变体本质上从单队列单服务台变成了单队列多服务台在排队论里对应M/M/c模型作业里一般不要求算那么深但理解多窗口的思路对后面学操作系统里的进程调度有帮助。还有一类变体是购房者可能中途放弃排队比如题目说如果等待时间超过某个阈值就离开。这时需要遍历队列删除指定元素单纯用标准队列就不方便了得用LinkedList直接操作结点或者用懒删除标记该元素作废出队时跳过。遇到这种题别慌先想清楚删除操作对顺序的影响再决定要不要换数据结构。3. 必做2队列实现的核心细节3.1 循环队列必须想清楚的两个决策数组实现队列时最忌讳的就是队尾指针一直增加队首指针也一直增加数组前面的空间被浪费。教科书上的循环队列就是针对这个问题的标准解法。写循环队列前有两件事必须提前想明白。第一件事空队和满队怎么区分。假设数组容量为capacityfront指向队首元素rear指向队尾元素的下一个位置。如果只用frontrear判断空那么队列满的时候rear绕一圈也回到front就会出现既是空又是满的矛盾。常见方案有两种一是牺牲一个存储单元让rear1front作为满队条件这样队列最多存capacity-1个元素二是额外用一个size变量记录当前元素个数入队加一、出队减一用size0判空sizecapacity判满。我强烈推荐第二种代码更直观也不容易在边界时搞混。第二件事指针移动必须取模。入队时写rear (rear 1) % capacity出队时写front (front 1) % capacity。很多人第一次写循环队列时把这一步漏掉结果出队几个元素后再入队就数组越界或者出现稀奇古怪的乱序。取模就是循环队列循环两字的精髓同时也是最容易在考试时被扣分的细节。3.2 数组循环队列的完整实现public class CircularQueueT { private Object[] data; private int front; private int rear; private int size; private int capacity; public CircularQueue(int capacity) { this.capacity capacity; data new Object[capacity]; front 0; rear 0; size 0; } public boolean enqueue(T item) { if (size capacity) { return false; // 队列已满 } data[rear] item; rear (rear 1) % capacity; size; return true; } public T dequeue() { if (size 0) { return null; // 队列为空 } T item (T) data[front]; data[front] null; // 释放引用避免内存泄漏 front (front 1) % capacity; size--; return item; } public T peek() { if (size 0) { return null; } return (T) data[front]; } public boolean isEmpty() { return size 0; } public int size() { return size; } }写完这个类有一个小细节值得留意dequeue时我特意把原位置置成null。在Java里如果不做这一步那些被出队的对象依然被数组引用着JVM的垃圾回收没法及时回收如果队列长时间运行且频繁出入队就可能导致内存压力。这个细节在你的代码里也许不会立刻引发问题但养成习惯后后面写缓存区、连接池之类的组件时就会受益。3.3 链式队列的实现与要点链式队列的每个结点包含数据域和指向下一个结点的指针域。队列内部维护头指针和尾指针头指针指向队首结点尾指针指向队尾结点。public class LinkedQueueT { private static class NodeT { T data; NodeT next; Node(T data) { this.data data; } } private NodeT head; private NodeT tail; private int size; public void enqueue(T item) { NodeT newNode new Node(item); if (tail ! null) { tail.next newNode; } tail newNode; if (head null) { head tail; // 队列从空到非空头尾同时指向新结点 } size; } public T dequeue() { if (head null) { return null; } T data head.data; head head.next; if (head null) { tail null; // 队列变空尾指针也要清空 } size--; return data; } public T peek() { return head null ? null : head.data; } public boolean isEmpty() { return head null; } public int size() { return size; } }链式队列的三个坑基本上都藏在指针操作里。第一第一次入队时不要忘记让head也指向新结点否则头指针永远是null。第二出队最后一个元素后head变成null此时tail还指着一个已经被移除的结点必须同时把tail也置为null不然下一次入队时tail.next会空指针异常。第三Node类一定要用泛型或独立定义不要想当然地把数据直接存在Object里而不做类型安全处理。3.4 数组队列和链式队列怎么选这个选择题在作业里可能不会直接问但面试和笔试里经常出现。我整理了一个对照方便你一眼看清各自的优势。对比维度数组循环队列链式队列空间占用固定容量预先分配可能浪费按需分配但有结点指针开销入队出队时间复杂度O(1)O(1)访问中间元素O(n)且不方便O(n)但可操作性强容量限制有需要扩容逻辑无理论可无限增长内存局部性好连续存储差结点分散实现复杂度取模和判满容易写错指针顺序容易写错实际工程里Java标准库的ArrayDeque和LinkedList都提供了队列功能ArrayDeque基于循环数组实现性能更好也是推荐优先选用的队列实现。作业里自己实现队列时建议数组循环队列和链式队列都写一遍不要只挑一个。因为每种实现里的坑不一样真正动手走一遍比背十遍书都有用。4. 调试实录与常见问题速查4.1 编译和运行期的高频报错我把这几年在作业批改和答疑过程中遇到的典型问题整理成了表格。你要是调试时遇到同样的现象直接对着这个表找原因就行。现象真正原因解决思路程序死循环控制台不停刷行时钟快进逻辑缺失queue为空时没有跳到下一个到达时间在while循环里加空队快进分支printf输出内容错位格式化字符串里占位符数量与参数数量不一致逐个核对%n、%d、%f的对应关系dequeue后出现null输出队空时仍然继续出队没有判空每次dequeue前先调用isEmpty判断数组越界异常rear或front没有取模把所有rear和front改成取模形式平均等待时间全是0.00先一次性把所有购房者入队再统一出队导致clock永远是0按到达时间增量入队让服务完一个再继续入队链式队列运行时报NullPointerException出队到最后一个元素后tail没有置空或首次入队没有维护head检查头尾指针的所有赋值路径使用自己写的队列在买房问题上结果异常队列的size或isEmpty状态管理有误比如重复减一单独给队列类写一个简单测试不依赖买房主程序去测4.2 逻辑错误的排查套路编译能通过、运行不报错但结果就是不对这种问题最磨人。我的经验是别盯着主流程一直看先把数据量缩小到手算能算出来的程度。比如只拿两三个购房者到达时间分别为0、1办理时间分别为2、5手工把每一步的clock、队列内容、等待时间算出来再运行代码对比。如果中途对不上就在关键位置打印中间状态。我写这种模拟题时习惯打印三个值当前clock、当前队列里的所有元素编号、下一个即将到达的购房者编号。三行打印一出来到底是入队时机错了、还是出队时机错了、还是时钟推进错了一眼就能定位。很多人不习惯打印调试觉得不如断点调试高级但在这种时序模拟的程序里打印日志反而是最高效的手段。另外一定不要忽略输入顺序。如果题目给的数据不是按到达时间排序的你的模拟会在某个点上突然把一个早该到达的人漏掉。稳妥办法是读入后排序或者在读入时直接把到达时间作为数组排序关键字排一次序。这个防御性操作不会损失任何性能还能防住测试数据里的小陷阱。4.3 自测用例怎么设计交作业之前建议手写几组边界用例来测。我通常用四类一是所有购房者同时到达此时队列会瞬间堆满考验的是入队处理二是每个人都是办完一个、下一个才刚好到此时队列大部分时间只有一个元素考验的是空队快进分支三是最后一个人到达极晚中间有很长一段空档考验时钟跳跃是否正常四是只有一个购房者最容易被忽略的最小规模用例。这四组用例覆盖了模拟类程序百分之八九十的边界问题。尤其是队列为空要快进这个分支很多同学在处理普通密集到达时根本没机会走到结果真正遇到稀疏到达的数据就卡死了。写完代码先不说功能对不对把这四组数据跑一遍只要结果和你手算的一致基本就可以放心提交了。5. 一点实战经验5.1 关于命名和代码结构做这种作业别把变量名写成a、b、c这种一个字母的形式。队列对象叫queue时钟叫clock等待总时长叫totalWait比用字母缩写强太多。命名清晰的好处不只是让老师看得舒服更重要的是你自己排查问题时能少费很多劲。我见过有同学把变量名全用拼音缩写两周后再看自己的代码完全认不出来最后只能重写。还有一个被很多人忽略的点能把模拟逻辑和队列实现分开就尽量分开。必做2自己实现的队列应该作为一个独立的类文件存在而不是把main方法和队列实现塞在同一个类里。这样你在提交时会发现自己代码的可读性高出一个档次后面复用这个队列类时也方便。5.2 关于时间复杂度和进一步思考这道题的模拟主流程复杂度很简单每个购房者最多入队一次、出队一次所以整体是O(n)队列操作本身都是O(1)。这个复杂度很优秀但如果你用的是数组队列且没有扩容逻辑就会受限于初始容量。实际应用里数据规模不确定时要么用链式队列要么给数组队列加上动态扩容。知道了这些你才算真正掌握了这个知识点而不只是应付作业。我自己的做法是每做完一个数据结构的作业都回头想想这个结构还能用在哪些地方。队列的典型应用远不止买房排队消息队列、线程池的任务调度、树的层序遍历、广度优先搜索、操作系统的进程就绪队列全都是队列的天下。你把课堂上这两道题做透了后面碰到这些场景时会有一种原来我早就会了的熟悉感。5.3 最后分享一个小提醒完成提交前务必用正常语法检查一遍自己的代码尤其是括号是否配平、类名和文件名是否一致、main方法签名是否写对。作业环境里统一使用的JDK版本如果能跑这样一个模拟程序那就不会有太大的兼容性问题。但千万别去依赖某个环境特有的写法比如某些老版本编译器的语法糖一旦换台机器就编译不过了。这周的两道题难度其实都不大但它们把队列这个知识点从理论到应用完整地串了一遍。认真做好必做2的实现仔细跑通必做1的模拟你收获的绝对不只是作业做完了这一个结果更重要的是对先进先出这四个字背后行为逻辑的真正理解。这一点值得你在今后的每一次程序设计里都记住。