形式陈述

队列支持在尾部 enqueue(x)、在头部 dequeue()，满足先进先出：若依次入队 $x_1,\dots ,x_k$ 且无其他元素，则出队顺序为 $x_1,\dots ,x_k$。空队列操作的结果由接口约定。

直觉

队列保留到达顺序，最早等待的对象最先被服务。头尾职责分离是它与栈的根本区别。

例子与边界

广度优先搜索用队列按距离层次展开顶点。环形缓冲区可在固定数组中复用头部空间，避免每次出队整体移动。优先队列按键而非到达时间删除，因此不是 FIFO 队列。

推论与应用

任务调度、消息缓冲、网络包处理和 BFS 都依赖队列。并发队列还需额外规定线性化点、进展条件与内存可见性。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, §10.1。
• Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., Addison-Wesley, 2011, §1.3。