deque(双向队列)基本用法

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

简单介绍

就是可以两头插元素，两头删元素的数据结构

那么具体的STL操作（只写主要用的）

代码未经编译。。。不过我这样写肯定也过不了编译。。。

有错误、有补充、有希望楼主添加的都可以提出来吼

其实我知道就只讲操作有点不敢相信。。。

所以我下面还写了一个类型的题目，里面有用到它来实现，大概就行了吧。。。

seque<int> Q;

//定义一个双向队列 可以是任何类型的（同队列）

int main()

{

    Q.empty();//检查是否为空（同队列）

    Q.push_front();//从队头加元素（类比队列的Q.push()）

    Q.push_back(); //从队尾加元素（类比队列的Q.push()）

    Q.pop_front();//从队头删元素（类比队列的Q.pop()）

    Q.pop_back(); //从队尾删元素（类比队列的Q.pop()）

    Q.front();//返回队头元素（类比队列的Q.front()）

    Q.back(); //返回队尾元素（类比队列的Q.front()）

}

大概用的多的就这些吧

0/1最短路

用到双向队列的时候一般是在跑0/1最短路时（就是边权只有0和1的最短路）

会跑的很快，这里顺便讲一下吧

不证明

类似SPFA的跑法

只不过SPFA是每次更新后放到队尾

而我们跑0/1最短路时就是当前点被边权为0的边更新就放队头，被边权为1的边更新就放队尾

说了不证明，因为我不想

放个代码，跑以S为起点的单源0/1最短路

变量名不认识的就是建边的。。。\(ljl[\) \(]\)

void Short_Road()

{

	for(int i=0;i<=tot;++i)dis[i]=Inf;

	while(!Q.empty())Q.pop_front();

	Q.push_back(S),dis[S]=0;

	while(!Q.empty())

	{

		int now=Q.front();Q.pop_front();

		if(vis[now])continue;vis[now]=1;

		for(int i=hd[now];i;i=ljl[i].nxt)

		{

			int qw=ljl[i].to;

			if(vis[qw])continue;

			if(dis[qw]>dis[now]+ljl[i].v)

			{

				dis[qw]=dis[now]+ljl[i].v;

				if(ljl[i].v)Q.push_back(qw);

				else Q.push_front(qw);

			}

		}

	}

}