队列

贡献者：有机物

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

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

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

　　 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$ 用于模拟队列，定义 $hh$ 为队头，初始化为 $0$ ， $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 ++ ;

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

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。