队列

贡献者： 有机物

　　 队列是一种 “先进先出” 的数据结构。队列在左端（队头）弹出元素，在右端（队尾）插入元素。C++ STL 中的 queue 实现了队列。队列通常是实现广度优先搜索（BFS）的数据结构。队列还有多种变体，如两端都能插入和弹出元素的双端队列（C++ STL deuqe），还有给元素赋予优先级，具有最高优先级的元素最先弹出，等价于一个堆的优先队列（C++ STL priority_queue）。

　　 队列通常有四种基本操作：

1. 向队尾插入一个数 $x$；
2. 从队头弹出一个数；
3. 判断队列是否为空；
4. 查询队头元素。

　　 C++ STL：

queue<int> q;
int hh = 0, tt = -1;  // hh 为队头，tt 为队尾

q.push(x);  // 在队尾插入新元素
q.pop();    // 删除队头元素但不返回其值
q.empty();  // 如果队列为空返回 true，否则返回 false
q.front();  // 返回队头元素的值，但不删除该元素

// 还有如下几个操作
q.back();   // 返回队列尾元素的值，但不删除该元素
q.size();   // 返回队列中元素的个数

　　 我们这里也是着重讲一下如何用数组实现队列。

　　 定义一个数组 $q$ 用于模拟队列，定义 $\mathtt{hh}$ 为队头，初始化为 $0$，$\mathtt{tt}$ 为队尾，初始化为 $-1$。

string op;
cin >> op;
if (op == "push") 
{
    int x;
    cin >> x;
    q[ ++ tt] = x;
} 
// 如果 hh <= tt 说明队列不为空
else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;
else if (op == "query") cout << q[hh] << endl;
else if (op == "pop") hh ++ ;

　　 以上就是队列的基本操作。