双指针与 STL 队列
学习目标：掌握对撞双指针、双序列双指针的基本思路；熟悉 STL queue 的常用操作；能够完成简单的排序配对和队列模拟题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、双指针
1. 双指针的基本思想
双指针是用两个变量记录序列中的位置，并根据条件移动它们的一种算法技巧。这里的“指针”通常是数组下标，不是 C++ 的指针类型。
例如，数组 a 中有 5 个元素：
l 表示左指针，r 表示右指针。移动指针就是改变当前处理的位置。
双指针的关键：每次移动指针时，都要知道为什么可以舍弃原来的位置。
在合适的问题中，暴力枚举所有元素对需要 O(n2)O(n^2)O(n2) 时间；如果两个指针始终单向移动，扫描过程通常只需要 O(n)O(n)O(n) 时间。
2. 对撞双指针
对撞双指针从序列两端出发，向中间移动：
* 左指针 l 从左向右移动，即 l++。
* 右指针 r 从右向左移动，即 r--。
基本框架如下：
当题目要求处理两个不同位置的元素时，常用循环条件 l < r。每轮都必须推进指针，否则可能死循环。
模板题：A105166 朴实无华的瑟提
给定一个仅由 0、1 组成的字符串。每次可以同时删除最左端和最右端的字符，但要求这两个字符不同。求最后剩下的字符数。
思路
1. 用 l 和 r 分别指向当前字符串的两端。
2. 如果 s[l] != s[r]，说明两端可以一起删除，执行 l++、r--。
3. 如果两端相同，或者剩余字符不足两个，就停止。
4. 剩余字符数为 r - l + 1；全部删完时这个值恰好为 0。
参考代码
两个指针最多各移动 nnn 次，单组数据的时间复杂度为 O(n)O(n)O(n)。
3. 排序 + 对撞双指针
当题目需要从若干元素中选择两个组成一组时，常常可以先排序，再用双指针从两端考虑。
例如，数组已经从小到大排列，希望找到两个不同位置的数，使它们的和等于 target：
当前情况 下一步 原因 a[l] + a[r] == target 找到符合要求的数对 两数之和刚好满足条件 a[l] + a[r] < target l++ 和太小，需要尝试更大的左端元素 a[l] + a[r] > target r-- 和太大，需要尝试更小的右端元素
为什么和太小时可以直接移动 l？因为数组已经有序，固定 a[l] 后，右边换成任何更小的数，和只会更小，不可能等于目标值。因此当前左端元素可以排除。
先排序，才能利用元素的大小关系安全地移动指针。 排序需要 O(nlogn)O(n\log n)O(nlogn) 时间，之后的双指针扫描需要 O(n)O(n)O(n) 时间，因此总时间复杂度通常为 O(nlogn)O(n\log n)O(nlogn)。
课堂练习：A69 纪念品分组
每组最多放两件纪念品，且总价格不能超过上限 w，要求分组数量最少。
思考以下问题：
1. 排序后，为什么优先处理当前最贵的纪念品？
2. 如果最贵的纪念品与最便宜的纪念品放在一起仍然超出 w，它还能与其他纪念品配对吗？
3. 如果最贵和最便宜的纪念品能够组成一组，如何移动两个指针？
这道题的重点是将贪心选择转化为两端指针的移动规则。
4. 两个数组的双指针
两个指针也可以分别位于两个数组中。先将两个数组排序，再从各自的开头向后移动，常用于匹配两个有序序列。
i 表示数组 a 当前的位置，j 表示数组 b 当前的位置。任何一个数组遍历结束时，循环就应该停止。
课堂练习：A105168 表演配对
有两组动物，每只动物最多参与一次配对。只有体型差不超过 111 的一对动物才能成为搭档，求最多能组成多少对。
将两组动物的体型分别从小到大排序，使用 i 和 j 指向各组中当前尚未配对的最小值：
条件 操作 ∣ai−bj∣≤1\lvert a_i-b_j\rvert\le 1∣ai −bj ∣≤1 配成一对，答案加一，i++、j++ ai<bj−1a_i<b_j-1ai <bj −1 i++，跳过体型过小的动物 bj<ai−1b_j<a_i-1bj <ai −1 j++，跳过另一组中体型过小的动物
为什么可以跳过较小的一方？因为另一组后面的动物只会更大，当前这个过小的体型不可能再与它们成功配对。
5. 双指针的易错点
* 移动理由不明确。 不能仅凭“感觉需要变大或变小”就移动，必须结合有序性或题目的限制说明不会漏掉更优答案。
* 边界写错。 处理两个不同位置时通常使用 l < r；两个数组的指针则要分别检查自己的长度。
* 遗漏排序。 依赖大小顺序的双指针做法，必须先保证相关数组有序。
* 混淆扫描与总复杂度。 扫描可能是 O(n)O(n)O(n)，但如果先排序，总复杂度通常是 O(nlogn)O(n\log n)O(nlogn)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、STL 队列
1. 队列的基本概念
队列（Queue）是一种先进先出（FIFO）的数据结构：先进入队列的元素，先离开队列。
在这个队列中，10 是队首，40 是队尾。新元素从队尾加入，删除时只能从队首移除。
C++ STL 提供了 queue 容器，可以直接使用。
2. STL QUEUE 的基本操作
使用 queue 时，需要包含 <queue> 头文件：
常用操作如下：
操作 含义 是否改变队列 q.push(x) 将 x 加入队尾 是 q.pop() 删除队首元素 是 q.front() 读取队首元素 否 q.back() 读取队尾元素 否 q.empty() 判断队列是否为空 否 q.size() 获取队列中的元素个数 否
对于默认的 STL 队列，上述操作的时间复杂度均为 O(1)O(1)O(1)。
下面观察操作过程：
特别注意：
* front() 只读取队首，不会删除元素。
* pop() 只删除队首，不会返回被删除的值，不能写成 int x = q.pop();。
* 当队列为空时，不要调用 front()、back() 或 pop()。
* queue 不能像数组一样使用 q[0] 访问元素。
要获取并删除队首元素，可以这样写：
模板题：A670 模拟队列操作
初始队列为空，执行若干次 push x 或 pop 操作；如果执行 pop 时队列为空，则忽略该操作。最后按队首到队尾的顺序输出队列中的元素。
参考代码
queue 不支持直接遍历全部元素。这里通过不断读取、删除队首元素，按顺序输出整个队列。输出完成后，队列也变空了。
3. 循环队列模拟
有些题目中，一个元素处理完后还要重新排队。做法是：先取出队首，再将它放入队尾。
例如，队列依次包含 1 2 3 4，将队首移动到队尾后，顺序变成 2 3 4 1。
STL queue 本身不会自动循环。这里的“循环”指的是通过出队和入队操作，使元素重新排队。
课堂练习：A530 周末舞会
男士和女士分别排队，每首舞曲从两队的队首各选出一人组成舞伴。跳过舞的人重新排到自己队伍的末尾。
需要分别维护两个队列，按舞曲数量重复完成配对和重新入队。
课堂练习：A82880 约瑟夫问题
nnn 个人围成一圈，从第一个人开始报数，报到 mmm 的人出圈；下一个人重新从 111 开始报数，直到所有人都出圈。输出所有人的出圈顺序。
使用队列保存尚未出圈的人。每一轮：
1. 将前 m−1m-1m−1 个报数的人依次从队首移到队尾。
2. 此时队首就是报到 mmm 的人，输出其编号并删除。
3. 队列不为空时继续下一轮。
本题要求输出所有人的出圈顺序，不是只求最后剩下的人。
4. 队列与标记数组配合
普通队列能够快速维护队首和队尾，但不适合直接查询“某个指定元素是否在队列中”。如果需要频繁进行这种判断，可以额外使用标记数组。
* 队列：维护元素进入的先后顺序。
* 标记数组：记录某个元素当前是否在队列中。
常见应用是先进先出缓存：容量已满时，删除最早进入的元素，再存入新元素。访问已经存在的元素时，不改变它原来的进入顺序。
课后题 A237 机器翻译 就需要结合队列与标记数组。
5. 队列的易错点
* 把 front() 当成删除操作。 读取后如需删除，还要执行 pop()。
* 对空队列执行删除或读取。 应先用 empty() 判断。
* 把 pop() 的返回值当成队首元素。 它没有返回值。
* 循环模拟时忘记重新入队。 需要继续参与的元素必须使用 push() 放回队尾。
* 把队列理解成排序工具。 普通队列只维护先后顺序，并不会自动按大小排序。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、课堂练习
按学习顺序完成：
顺序 类型 题目 知识点 1 双指针模板 A105166 朴实无华的瑟提 对撞双指针 2 双指针课堂练习 A69 纪念品分组 排序、贪心与双指针 3 双指针课堂练习 A105168 表演配对 两个有序数组匹配 4 队列模板 A670 模拟队列操作 queue 基本操作 5 队列课堂练习 A530 周末舞会 两个队列循环模拟 6 队列课堂练习 A82880 约瑟夫问题 报数与队列轮转
四、课后作业
双指针
顺序 题目 要求 1 A105167 共享食物 必做 2 A105175 水瓶挑战 必做 3 A137130 能量搭档 提高 4 A46133 田忌赛马 选做
队列
顺序 题目 要求 1 A82883 发糖果 必做 2 A237 机器翻译 必做 3 A531 打印机 提高 4 A50005 公交换乘 选做 5 A532 团体队列 选做
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、学习检查
完成本节课后，应当能够解释：
1. 双指针为什么能够跳过一些位置而不漏掉答案？
2. 对撞双指针与两个数组的双指针有什么区别？
3. 为什么依赖大小关系的双指针题通常需要先排序？
4. front() 和 pop() 分别做什么？
5. 怎样用 queue 将队首元素移动到队尾？
6. 为什么队列适合模拟报数、轮流服务和先进先出缓存？
不仅要会写代码，还要能解释每次指针移动或队列操作的原因。
附：参考资料
* OI Wiki：双指针
* OI Wiki：队列
* cppreference：std::queue
* ACGO：双指针专题
