[数据结构与算法]queue单调队列

STL上次介绍了一个struct（结构体），接下来就来介绍queue单调队列

队列的定义：
队列是一种特殊的线性表，对这种线性表，删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)进行。队列的修改是按先进先出的原则进行的，所以队列又称为先进先出(First In First Out)表，简称FIFO表。
队列的数学性质：
假设队列从头到尾依次为a1,a2,…,an，那么a1就是队头元素，an为队尾元素。队列中的元素是按a1,a2,…,an的顺序进入的，退出队列也只能按照这个次序依次退出。也就是说，只有在a1离开队列之后，a2才能退出队列，只有在a1,a2,…,an-1都离开队列之后，an才能退出队列。
举个生活中的例子，比如食堂打饭排队，先来的排在队伍前面，后来的在队后；队头的人先打饭，打完饭就离队（删除操作）；如果还有人过来，就排在队尾（插入操作）；
在程序实现上，队列是用数组来存放的，需要两个数组下标变量head和tail，tail变量负责存数据（插入数据操作）时控制存入的位置，head变量负责取数据（取出队头元素）的读取位置。
由于C++ 的STL 本身提供了队列这种数据结构，所以我们就不用自己去实现队列，你只要学会使用STL的队列操作就行了。
队列是学习广搜需要用到的数据结构，所以务必要掌握。其实很简单。
queue
queue 模板类的定义在头文件中。
与stack 模板类很相似，queue 模板类也需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque 类型。
定义queue 对象的示例代码如下：
queue q;
queue q1;
queue 的基本操作有：
入队，如例：q.push(x); 将x 接到队列的末端。
出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
访问队首元素，如例：q.front()，即最早被压入队列的元素。
访问队尾元素，如例：q.back()，即最后被压入队列的元素。
判断队列空，如例：q.empty()，当队列空时，返回true。
访问队列中的元素个数，如例：q.size()
一、普通声明：就是普通队列，入队的都是单一的数据类型

#include <iostream>
#include <queue> // 使用队列需要 的头文件 
using namespace std;
int e,n,m,x;
queue<int> q1; //定义一个整数类型的队列 
int main()
{
    for(int i=0;i<10;i++) { //读入十个数据，并依次入队 
        cin>>x;
        q1.push(x);
    }
 if(!q1.empty()) //判断队列是否已空的方法 
cout<<"队列还有数据\n";
    n=q1.size();  // 求出队列里有多少个数据 
    cout<<n<<endl;
    m=q1.back();  //访问队尾元素 
    cout<<m<<endl;
    for(int j=0;j<n;j++)
    {
         e=q1.front(); //取出当前的队头数据 
	    cout<<e<<" ";
        q1.pop(); //弹出队头数据，就是删除队头数据的意思 
    }
    cout<<endl;
    if(q1.empty())  //判断队列是否已空的方法 
        cout<<"队列已空\n";

    return 0;

}

但是今天的重点并不是普通的单调队列，而是要着重介绍广度优先搜索所要用到的队列

广度优先搜索很明显重点是广度，何为广度？

广度优先搜索(BFS)，也称为宽度搜索。它的过程类似树的按层遍历
很明显深度优先搜索（DFS），它的过程类似从根节点出发一直遍历到最后一个子节点

广搜的理解：假设你在湖边，附近湖面上有一些皮球，散落在水面上。你想知道其中哪个球距离你最近？ 这时，你可以在靠近你的湖面扔块石头，于是水面上就会有一圈一圈的波纹由近向远扩散，你只要观察波纹最先碰到哪个球，哪个球就是最近的。 这个过程就像广搜。 你的位置就是搜索的起点，波纹的扩散过程就像广搜的过程，波纹到达最近的皮球的时间就是答案。 从广搜的原理可以看出：广搜解决的问题是求最小值（最短距离）这类的问题。

之前发过的迷宫（3）的题解就有涉及到广度优先搜索，很明显 我们用到了队列先进先出的性质，先进后出也正对应了波纹扩散，我们先将起点入队，再从起点扩散出其他方向，不断的循环下去，知道有一个点的坐标与目标的坐标相同为止，而从起点到这个点的步数就是从起点到终点的最近距离。

上题目：

【题目部分】
有一个mn格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用0表示可以走，1表示不可走，文件读入这mn个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的的行号和列号）。现在要你编程找出从起点到终点的最少步数，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出“No Answer! ”。
Input
第一行是两个数 m、n，接下来是m行n列由10组成的数据，最后两行是起始点（X1，X2）和结束点（Y1，Y2）。
数据范围：0 < M，N <= 2000。0〈 X1，X2〈= N，0〈 Y1，Y2〈= M。
Output
一个数，表示最少要走的步数。如果走不到，则输出“No Answer! ”
Sample Input 1
5 5
1 1 1 1 1
1 1 1 0 0
1 0 0 0 1
0 0 1 0 0
1 1 1 0 1
4 1
5 4
Sample Output 1
6

上代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
bool walk[2011][2011]={0};
int dx[]={0,0,1,-1},dy[]={-1,1,0,0};
struct node{
	ll x,y,step;
};
queue<node> q;
node temp,s,e,x,t;
ll n,m;
int main(){
	memset(walk,1,sizeof(walk));
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>walk[i][j];
		}
	}
	cin>>s.x>>s.y>>e.x>>e.y;
	s.step=0;
	q.push(s);
	while(!q.empty()){
		t=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			temp.x=t.x+dx[i];
			temp.y=t.y+dy[i];
			temp.step=t.step+1;
			if(walk[temp.x][temp.y]==0){
				walk[temp.x][temp.y]=1;
				if(temp.x==e.x&&temp.y==e.y){
					cout<<temp.step;
					return 0;
				}
				else
					q.push(temp);
			}
		}
	}
	cout<<"No Answer!";
	return 0;
}

																			拜拜┏(＾0＾)┛