常见算法题型之STL基础：deque。附例题

STL deque 双端队列详解与例题实战一、deque 基础介绍dequedouble-ended queue双端队列是 C 标准模板库STL中的容器它支持在队列头部和尾部进行 O(1) 时间复杂度的插入与删除操作同时也支持随机访问。它可以看作是vector和queue的结合体既保留了数组的随机访问能力又具备队列的两端高效增删特性。deque 的核心特点底层采用分段连续空间实现逻辑上整体连续因此支持下标随机访问。头部、尾部插入/删除元素都是 O(1) 时间复杂度中间插入删除为 O(n)。没有capacity容量概念扩容时不会像vector一样复制全部元素。非常适合频繁在两端操作元素的场景比如滑动窗口、模拟类队列问题。二、deque 常用操作汇总使用前需要引入头文件#includedequeusingnamespacestd;1. 构造与初始化dequeintdq;// 创建空的双端队列dequeintdq(5);// 包含5个默认初始化的元素dequeintdq(5,10);// 包含5个值为10的元素dequeintdq(arr.begin(),arr.end());// 通过迭代器区间初始化2. 元素访问操作说明dq.front()返回队首元素的引用dq.back()返回队尾元素的引用dq[i]下标随机访问O(1)无边界检查dq.at(i)下标访问带边界检查越界会抛出异常3. 插入元素操作说明时间复杂度dq.push_front(x)在队头插入元素 xO(1)dq.push_back(x)在队尾插入元素 xO(1)dq.insert(pos, x)在迭代器 pos 位置插入元素 xO(n)4. 删除元素操作说明时间复杂度dq.pop_front()删除队首元素O(1)dq.pop_back()删除队尾元素O(1)dq.erase(pos)删除迭代器 pos 位置的元素O(n)dq.clear()清空队列中所有元素O(n)5. 容量与状态判断操作说明dq.empty()判断队列是否为空返回 bool 值dq.size()返回队列中元素的个数dq.resize(n)调整队列大小为 n多出部分删除不足补默认值6. 迭代器dq.begin();// 正向迭代器指向队首元素dq.end();// 正向迭代器指向队尾元素的下一个位置dq.rbegin();// 反向迭代器指向队尾元素dq.rend();// 反向迭代器指向队首元素的前一个位置三、例题实战擂台轮转https://ac.nowcoder.com/acm/contest/130222/E题目描述有 n 位选手排成一列队首为擂台。每回合前两名选手比拼战力更高者留在队首失败者排到队伍末尾。求经过 k 回合后最终的选手队列。数据范围1≤T≤1051\le T\le 10^51≤T≤1052≤n≤3×1052\le n\le 3\times10^52≤n≤3×1050≤k≤1090\le k\le 10^90≤k≤109所有测试用例 n 之和不超过3×1053\times10^53×105战力为 1~n 的排列。思路提取与分析1. 暴力模拟的局限性如果直接逐轮模拟比拼过程当 k 达到10910^9109时O(k) 的时间复杂度会严重超时必须通过规律优化模拟次数。2. 核心规律最大值的周期性由于所有战力互不相同队列中存在全局唯一的最大值最多经过n-1轮比拼最大值一定会一路获胜最终来到队首每一轮胜者留在队首最大值永远不会输。当最大值成为队首后后续每一轮都是最大值获胜第二个元素会被移到队尾。此时队列变化进入周期为 n-1 的循环每 n-1 轮队列会回到完全相同的状态。3. 优化方案我们只需要模拟最多2*(n-1)轮即可得到正确结果前 n-1 轮内最大值必然到达队首进入稳定周期。超出 n-1 的部分对 n-1 取模等价于只需要模拟余数轮。最终将模拟轮数控制在 O(n) 级别完美适配数据范围。正解代码#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intt;cint;while(t--){intn,k;cinnk;dequeintdq;// 读入初始战力存入双端队列for(inti0;in;i){intx;cinx;dq.push_back(x);}// 核心优化利用周期性减少模拟轮数if(k2*(n-1)){k(n-1)k%(n-1);}// 模拟k轮比拼while(k--){// 取出队首两个元素intadq.front();dq.pop_front();intbdq.front();dq.pop_front();if(ab){// a获胜放回队首b失败放到队尾dq.push_front(a);dq.push_back(b);}else{// b获胜放回队首a失败放到队尾dq.push_front(b);dq.push_back(a);}}// 输出最终队列while(!dq.empty()){coutdq.front() ;dq.pop_front();}cout\n;}return0;}关键说明deque 的核心作用每一轮需要取出队首两个元素、把胜者放回队首、败者放到队尾deque的push_front/pop_front/push_back完美适配这个操作流程所有操作都是 O(1) 时间复杂度。k 的优化逻辑当k 2*(n-1)时令k (n-1) k % (n-1)n-1保证最大值已经到达队首进入稳定的循环周期。k % (n-1)计算周期内的剩余轮数跳过无意义的完整周期循环。最终模拟轮数不会超过2n总时间复杂度为 O(n)可以轻松通过10910^9109级别的 k。样例验证以样例第三组n5, k3, 数组[3,4,1,5,2]为例初始队列[3, 4, 1, 5, 2]第1轮3 vs 4 → 4胜队列变为[4, 1, 5, 2, 3]第2轮4 vs 1 → 4胜队列变为[4, 5, 2, 3, 1]第3轮4 vs 5 → 5胜队列变为[5, 2, 3, 1, 4]与样例输出完全一致。四、总结deque是处理双端增删场景的利器在模拟类、滑动窗口类问题中非常常用。本题的核心是用 deque 高效模拟比拼过程 利用最大值的周期性优化大 k 情况将暴力 O(k) 复杂度优化为 O(n)是经典的“模拟找规律”题型。