C / C++ / 系统课时
队列为什么从两端操作
队列为什么从两端操作
当任务按到达顺序等待处理时,新任务不能插到最前面,已经等待最久的任务又应优先离开。队列把这两个动作分开放在两端:队尾负责接收新元素,队头负责取出旧元素,由此稳定地实现先进先出。
学习目标
- 理解队头删除、队尾插入为什么能保证先进先出
- 能根据
front和rear判断一次入队或出队发生在哪一端 - 区分普通队列与可以从两端任意插入、删除的双端队列
从任务排队看两端职责
假设任务 A、B、C 按这个顺序到达。如果系统要求先来的任务先处理,那么 A 必须先于 B,B 必须先于 C。此时最自然的做法是让新任务持续排在已有任务之后,而处理程序始终从最早到达的一端取任务。
因此,队列通常约定两个位置:front 表示队头,也就是下一次出队的位置;rear 表示队尾附近,用来确定下一次入队的位置。不同实现对 rear 究竟指向最后一个元素还是下一个可写位置可能有不同约定,但先进先出的规则不变。

为什么不能在同一端完成两个动作
如果新元素和旧元素都从队头操作,新到达的任务会直接挡在旧任务前面,行为就更接近栈的后进先出。反过来,如果始终只在队尾插入和删除,那么刚刚插入的元素也会最先被删除,同样不能保持到达顺序。
把插入和删除固定在相反的两端后,队列中的相对顺序不会被新元素打乱。假设当前内容是 A、B、C,执行一次入队 D 后得到 A、B、C、D;随后出队,只能移除 A,剩余 B、C、D。
| 操作 | 发生位置 | 队列变化 |
|---|---|---|
| D 入队 | 队尾 | A、B、C → A、B、C、D |
| 一次出队 | 队头 | A、B、C、D → B、C、D |
队列限制换来了什么
队列故意限制访问方式,是为了让处理顺序可预测。打印任务、消息消费、请求排队和广度优先搜索等场景,都经常需要“先进入等待区的对象先被处理”。调用者不应绕过队头直接删除中间元素,否则队列维护的顺序语义就会失效。
判断一次操作是否符合队列规则
面对一个排队场景,可以先问两个问题:新对象应该排到谁后面,下一次应该优先处理谁。如果答案分别是“当前所有等待对象之后”和“等待时间最长的对象”,那么使用队尾入队、队头出队就是自然选择。
这种受限访问方式正是队列的核心:两端承担不同职责,从而在不断插入和删除的过程中仍然保持先进先出的顺序。
按自己的节奏,确认真正理解。