数据结构队列详解：JavaScript 实现与应用场景

什么是队列

• 一个先进先出的数据结构
• Js 中没有队列，但可以用 Array 实现队列的所有功能

先进先出常缩写成 FIFO。和栈的区别只有一处但很关键：栈的进出在同一端，队列的进出在两端——一端只负责入队，另一端只负责出队。就这一个差别，让两者适用的问题完全不同。

判断该用哪个，看问题要求的处理顺序：需要「最近的先处理」用栈，需要「按到达顺序处理」用队列。前者对应嵌套结构，后者对应排队等待。树的遍历里这个对应关系体现得最清楚，深度优先用栈，广度优先用队列，换一个容器就换一种遍历方式，其余逻辑几乎不用改。

第二条说 JS 没有队列，情况和栈一样，指的是没有专门类型。用数组实现的组合是 push 加 shift：末尾入队，头部出队。

这里有个性能问题必须提一下。shift 不是 O(1) 而是 O(n)——它删掉头部元素之后，后面所有元素都要往前挪一位，同时数组长度变化。数据量小的时候无所谓，但如果队列里有几万个元素还要反复出队，整体就退化成 O(n^2)，会明显卡住。

正规做法是不真的删除元素，而是用一个下标当作队首指针，出队时把指针往后移一格，元素留在原地不动。这样入队出队都是 O(1)，代价是数组不会缩短，占用的空间只增不减，需要在合适的时机做一次整理。要求更严格的场景会用双向链表或者环形缓冲区来实现，那才是真正的 O(1) 且空间不浪费。

js 模拟队列

如下代码，先 push 1 然后 push 2，然后执行两次 shift。由于 shift 是删除数组中第一个元素，所以 1 是先被删除的， 也就是说，1 是先被放进来的，也是最先被删掉的。 可以发现这是一个先进先出示例

const queue = [];
queue.push(1);
queue.push(2);
const item1 = queue.shift();
const item2 = queue.shift();

所以 item1 是 1，item2 是 2，跟放进去的顺序一致。这正是和栈的对比点：同样的入队序列，栈弹出的是 2、1，队列出队的是 1、2。代码上的差别仅仅是 pop 换成了 shift。

场景

• 食堂排队打粉

这是最直观的类比：先到的人先打到饭，后来的人只能排到队尾，不能插队也不能从中间取。队列的所有约束在这个场景里都很自然。

• JS 异步中的任务队列

这个是理解 JS 执行模型的关键。JS 是单线程的，异步回调不能立刻执行，需要先排队等主线程空出来，事件循环就是不断从队列里取任务执行的过程。用队列而不是栈的道理很实在：如果用栈，先注册的回调会被后注册的一直压在下面，可能永远等不到执行；用队列保证了按注册顺序依次执行，不会有任务被无限期饿死。

进一步说，这里其实有两个队列，宏任务队列和微任务队列。Promise 的回调进微任务队列，setTimeout 的回调进宏任务队列，每执行完一个宏任务，会把微任务队列整个清空再取下一个宏任务。这就是为什么同时写 setTimeout 和 Promise.then，then 总是先执行——两者各自在自己的队列里保持先进先出，但两个队列的优先级不同。

• 计算最近请求次数

这是队列的一个典型应用题，本质是维护一个滑动的时间窗口：新请求从队尾进来，过期的请求从队首出去，队列长度就是窗口内的请求数。之所以能这么做，是因为请求按时间先后到达，最早进来的必然最早过期，这个顺序和队列的先进先出天然吻合。限流器的实现思路也是这个。