[关闭]
@Junlier 2018-09-29T02:59:56.000000Z 字数 1043 阅读 2143

deque(双向队列)基本用法

STL
阅读体验:https://zybuluo.com/Junlier/note/1297030

简单介绍

就是可以两头插元素,两头删元素的数据结构
那么具体的STL操作(只写主要用的)
代码未经编译。。。不过我这样写肯定也过不了编译。。。
有错误、有补充、有希望楼主添加的都可以提出来吼
其实我知道就只讲操作有点不敢相信。。。
所以我下面还写了一个类型的题目,里面有用到它来实现,大概就行了吧。。。

  1. seque<int> Q;
  2. //定义一个双向队列 可以是任何类型的(同队列)
  3. int main()
  4. {
  5. Q.empty();//检查是否为空(同队列)
  6. Q.push_front();//从队头加元素(类比队列的Q.push())
  7. Q.push_back(); //从队尾加元素(类比队列的Q.push())
  8. Q.pop_front();//从队头删元素(类比队列的Q.pop())
  9. Q.pop_back(); //从队尾删元素(类比队列的Q.pop())
  10. Q.front();//返回队头元素(类比队列的Q.front())
  11. Q.back(); //返回队尾元素(类比队列的Q.front())
  12. }

大概用的多的就这些吧

0/1最短路

用到双向队列的时候一般是在跑0/1最短路时(就是边权只有0和1的最短路)
会跑的很快,这里顺便讲一下吧
不证明
类似SPFA的跑法
只不过SPFA是每次更新后放到队尾
而我们跑0/1最短路时就是当前点被边权为0的边更新就放队头,被边权为1的边更新就放队尾
说了不证明,因为我不想
放个代码,跑以S为起点的单源0/1最短路
变量名不认识的就是建边的。。。

  1. void Short_Road()
  2. {
  3. for(int i=0;i<=tot;++i)dis[i]=Inf;
  4. while(!Q.empty())Q.pop_front();
  5. Q.push_back(S),dis[S]=0;
  6. while(!Q.empty())
  7. {
  8. int now=Q.front();Q.pop_front();
  9. if(vis[now])continue;vis[now]=1;
  10. for(int i=hd[now];i;i=ljl[i].nxt)
  11. {
  12. int qw=ljl[i].to;
  13. if(vis[qw])continue;
  14. if(dis[qw]>dis[now]+ljl[i].v)
  15. {
  16. dis[qw]=dis[now]+ljl[i].v;
  17. if(ljl[i].v)Q.push_back(qw);
  18. else Q.push_front(qw);
  19. }
  20. }
  21. }
  22. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注