queue队列

一、queue的基本概念

queue的中文名字叫做队列。队列是什么呢？

队列是一种特殊的线性表，是一种先进先出(FIFO)的数据结构。它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

假设小红球，小黄球，小蓝球和小绿球这四个球去买票。小红球先排队，然后黄蓝绿依次站在后面。那么，谁会先买到票？（只要不插队的话）肯定先进去的先出来。（当然有可能出口太小出不来）

这就是queue的策略：先进先出策略（First In First Out,简称FIFO）。

所以说，说白了，queue就是一个遵守FIFO策略的链表。

队列的相关概念：

队头与队尾： 允许元素插入的一端称为队尾，允许元素删除的一端称为队头。
入队：队列的插入操作。
出队：队列的删除操作。
例如我们有一个存储整型元素的队列，我们依次入队：{1，2，3}

添加元素时，元素只能从队尾一端进入队列，也即是2只能跟在1后面，3只能跟在2后面。
如果队列中的元素要出队：

元素只能从队首出队列，出队列的顺序为：1、2、3，与入队时的顺序一致，这就是所谓的“先进先出”。

二、queue的头文件

queue需要以下两个头文件：

#include<queue>

using namespace std;

三、queue的声明与构造函数

queue声明的基本结构是这样的：

queue<数据结构>队列名;

比如：

queue<int> i;

queue<double> d;

queue<node> n;//node是一个结构体

四、queue的基本操作

queue<int> q;

q.size();//返回q里元素个数

q.empty();//返回q是否为空，空则返回1，否则返回0

q.push(k);//在q的末尾插入k

q.pop();//删掉q的第一个元素

q.front();//返回q的第一个元素

q.back();//返回q的末尾元素