STL课程第五课《魔法双开门——认识Deque双端队列》本课目标理解什么是双端队列Deque。理解 Queue 与 Deque 的区别。熟练掌握push_front()、push_back()、pop_front()、pop_back()等常用操作。知道什么时候使用 Deque。为以后学习单调队列、滑动窗口等算法打基础。第一幕 奇怪的公交车程序王国来了一个奇怪的公交车。普通公交车。大家只能后门上车。前门下车。画图上车 下车 →→老师问这像什么学生回答Queue完全正确。可是。今天来了一个魔法公交车。不仅后门可以上车。前门也可以上车。甚至。前门。后门。都可以下车。画图 ← → ↑ ↑ 两边都可以操作今天认识的新朋友。叫Deque读作Deck德克中文名字双端队列为什么叫双端因为两端都可以操作。第二幕 Queue为什么不够用了请问Queue可以push()从哪里加入同学们回答队尾。请问pop()从哪里删除同学们回答队首。继续问如果今天。我们想从队首加入一个人。怎么办Queue做不到。所以。发明了Deque。第三幕 请出Deque首先。请头文件。#includeiostream #includedeque using namespace std;创建Deque。dequeint dq;解释deque表示双端队列。int保存整数。dq变量名字。第四幕 后门加入——push_back()先放10dq.push_back(10);队伍10继续。dq.push_back(20);变成10 20继续。dq.push_back(30);变成10 20 30是不是和Queue一样完全一样。第五幕 前门加入——push_front()汉克老师笑着说Queue不会。Deque会。例如加入5dq.push_front(5);结果5 10 20 30画图前 后 5 10 20 30 ↑ ↑是不是很神奇第六幕 前门出去——pop_front()删除dq.pop_front();结果10 20 30和Queue一样。第七幕 后门出去——pop_back()老师继续。删除最后一个。dq.pop_back();结果10 20Queue能做到吗不能。Deque可以。第八幕 看看两端是谁最前面dq.front()最后面dq.back()例如coutdq.front()endl; coutdq.back()endl;输出10 20第九幕 有多少个元素dq.size()判断是否为空dq.empty()和Vector完全一样。第十幕 Deque还能像Vector一样访问吗请问Vectora[3]Deque呢答案可以例如coutdq[0];老师告诉学生。Deque虽然叫双端队列。但是。它还能随机访问。这点。比Queue厉害。第十一幕 遍历Deque例如for(int x:dq) { coutx ; }输出10 20是不是和Vector一样。第十二幕 演示程序#includeiostream #includedeque using namespace std; int main() { dequeint dq; dq.push_back(20); dq.push_back(30); dq.push_front(10); dq.push_front(5); cout现在队列endl; for(int x:dq) { coutx ; } coutendl; dq.pop_back(); dq.pop_front(); cout删除后endl; for(int x:dq) { coutx ; } return 0; }输出现在队列 5 10 20 30 删除后 10 20第十三幕 课堂小游戏我们依次执行push_back(3) push_back(5) push_front(2) push_front(1) pop_back() push_back(8)请同学们画图。最后1 2 3 8第十四幕 课堂实践一——火车车厢今天。有一列火车。既可以前面挂车厢。也可以后面挂车厢。例如输入back 10 back 20 front 5 back 30输出5 10 20 30孩子自己完成。第十五幕 课堂实践二——魔法数字列要求依次输入数字。奇数。放前面。偶数。放后面。例如输入1 2 5 6 7最后Deque7 5 1 2 6参考程序#includeiostream #includedeque using namespace std; int main() { dequeint dq; int n; cinn; for(int i0;in;i) { int x; cinx; if(x%21) dq.push_front(x); else dq.push_back(x); } for(int x:dq) coutx ; return 0; }第十六幕 Queue与Deque有什么区别画表格。功能QueueDeque前面加入❌✅后面加入✅✅前面删除✅✅后面删除❌✅下标访问❌✅遍历❌✅总结Queue只有两种操作。Deque有四种。所以。Deque更灵活。第十七幕 Deque真正的大本领汉克老师告诉学生。今天只是认识Deque。以后。学习单调队列。滑动窗口最大值。最小值。很多省选题。NOIP。CSP-J/S。都会用到Deque。所以。今天打好基础。以后轻松很多。本课总结今天我们认识了Deque双端队列。它最大的特点是两端都可以加入也两端都可以删除。掌握了八个常用成员函数成员函数作用生活中的理解push_front(x)从前面加入前门上车push_back(x)从后面加入后门上车pop_front()删除最前面前门下车pop_back()删除最后面后门下车front()查看最前面看队首back()查看最后面看队尾size()元素个数数人数empty()是否为空队伍是否没人一句话口诀双端队列本领强前后两端都能忙前可进后可进前可出后可出Queue 做不到Deque 全做到Vector 与 Deque 怎么选的课堂讨论很多孩子学完 Deque 后会问既然 Deque 功能更多是不是以后都用 Deque不用 Vector 了这正是培养数据结构选择能力的好机会。我们可以总结成下面这张表场景推荐容器原因主要在尾部添加、随机访问vector连续存储通常更快、更省空间需要频繁在前后两端插入、删除deque两端操作都很高效只需要先进先出queue接口简单不容易误用最后告诉大家一句重要的话容器没有最好只有最适合。这也是学习 STL 最重要的思想之一。
