数据结构基础之队列

数据结构之队列结构：

1. 队列的特点：

和栈一样，队列也是在数组的基础上进行出入限制，普通的队列，想排队一样，控制在队尾插入元素，队头删除元素。

2. 队列的用途：

在广度优先搜索（BFS）中会用到，比如现在有一个图如下：

现在从A点出发，把A入队，然后再A出队，首先访问到与A相邻的B、D，也就是B、D入队，A的相邻结点访问完毕，继续出队B，现在访问B的邻点，C入队，然后D出队，访问E，然后C出队，E出队。

访问顺序为：A(入)->A(出)->B(入)->D(入)->B(出)->C(入)->D(出)->E(入)->C(出)->E(出) （大致如此）

在这个搜索中，队列的作用便可以很清晰的看到。

在程序设计中，广度优先搜索是很重要的一种算法，也很常见，经典的迷宫找最短出路问题就要用到它。

3. 队列的写法：

如果自己手写队列的模板的话，可以封装成一个结构体或者类，首先要有元素本体、入队操作、出队操作，这三个是最基本的。比如我要建一个int类型的队列的话，那么可以封装如下：

（值得一提的是，队列是在队头出队，队尾入队，所以如果直接这样写的话会浪费很多的空间，比如但题目要求的是100个元素不断进行出队入队元素，而你在不断进行出队过程中有可能队头就跑到了99，那么如果只申请100个空间的话，明显是不够的，所以入队的时候，如果r已经等于MAX-1了，可以判断队头是否为0，如果不为0，表示还有空间，那么下一个元素便可以放到0的位置，继续地0、1、2、3存放，循环利用）

 1 typedef struct
 2 {
 3   int data[MAX];
 4   int l,r;      //l 指向队头 r 指向队尾的下一个
 5   bool pop(int &x)    //出队
 6   {
 7     if(l==r)    return 0;   //l==r 表示队列里没有东西
 8     x=data[l];
 9     l=(l+1)%MAX;
10     return 1;
11   }
12   bool push(int x)    //入队
13   {
14     if((r+1)%MAX==l) return 0; //(r+1)%MAX==l 表示队满
15     r=(r+1)%MAX;
16     data[r]=x;
17     return 1;
18   }
19   //上面出队入队的操作等于留了一个空位，这个空位是浪费掉的，大家可以找找！
20 }Queue;

如果在一些程序设计比赛，比如acm中，一般不会进行队列的封装，直接用C++封装好的queue就可以了。如下：

1 #include<queue>
2 using namespace std;
3 queue<type> q;
4 //出队 q.pop();
5 //入队 q.push();
6 //显示队头元素 q.front();

4. 对于队列的说明

与栈一样，都是数据结构最最基础的一块，要熟练掌握，同时了解一下他的特殊用法，比如单调队列、优先队列等。