本文章原出处：chicago01.top，转载不需说明，随意转载

想象着我们在食堂排队，或者在超市，这里我们就假设在食堂吧。之所以要排队就是因为公平性，先来先得。所以数据结构中的队列也是这样，先来的先走。一端进入，一端出。

[HTML_REMOVED]

实现

通常用一个数组模拟一个队列，用两个指针：front 和 rear 分别表示队列头部和尾部。

在入队的时候将 rear 后移，在出队的时候将 front 后移。

STL queue

在c++中，已经封装好了的STL库中有队列。其操作如下：

#include<bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n=10,num;
    /*
    1. push 【入队插到队尾】

    2. pop 【队首元素出队】

    3. size 【返回队列中元素的个数】

    4. front 【返回队列中第一个元素】

    5. back 【返回队列中最后一个元素】

    6. empty 【判断队列是否为空】
    */
    //cout<<"队列:"<<endl;
    queue<int> a;
    for(int i=1;i<n;i++){
        num = rand()%233;
        a.push(num);
    }
    //数列长度
    cout<<a.size()<<endl;
    //数列头元素
    cout<<a.front()<<endl;
    //数列尾元素
    cout<<a.back()<<endl;
    //数列是否为空
    while(!a.empty()){
        cout<<a.front()<<ends;
        a.pop();
    }cout<<endl<<endl;

    return 0;
}

优先队列（priority_queue）

顾名思义就是，你排队买饭，正排着队，突然来了一个社会小霸王，很不讲理，非要插队，你又揍不过他，这时候他的优先级比你高，排在你的前面。但是还没有完！突然有一个人拿着军官证，为满足军人优先政策，他的优先级比所有人都高，于是，他排在你和小霸王的前面。

而这样每个元素具有一定优先级的队列就叫做优先队列（但是其本质是一个堆）。

STL priority_queue

同样的c++也很贴心的为你内置好了这样一个模块，可以直接声明使用它。

1. top() : 访问栈顶元素 常数复杂度
2. empty() : 检查底层的容器是否为空 常数复杂度
3. size() : 返回底层容器的元素数量 常数复杂度
4. push() : 插入元素，并对底层容器排序 最坏 $O(n)$ 均摊 $O(log(n))$
5. pop() : 删除第一个元素 最坏 $O(log(n))$

#include<bits/stdc++.h>
using namespace std;

struct student{
    int grade;
    string name;
};
struct cmp{
    bool operator() (student s1,student s2){
    return s1.grade < s2.grade;
    }
};

int main(int argc, char const *argv[])
{
    int n=10,num;

    priority_queue<int> pq_1;
    for(int i=1;i<n;i++){
        num = rand()%233;
        pq_1.push(num);
    }
    //默认情况下，数值大的在队首位置(降序)
    while(!pq_1.empty()){
        //注意这里的访问头元素为.top
        cout<<pq_1.top()<<ends;
        pq_1.pop();
    }cout<<endl;

    //以下情况下，数值小的在队首位置(升序)
    priority_queue<int,vector<int>,greater<int> > pq_2;
    for(int i=1;i<n;i++){
        num = rand()%233;
        pq_2.push(num);
    }

    while(!pq_2.empty()){
        //注意这里的访问头元素为.top
        cout<<pq_2.top()<<ends;
        pq_2.pop();
    }cout<<endl;cout<<endl;

    //运算符重载

    priority_queue<student,vector<student>,cmp> q;
    student s1,s2,s3;
    s1.grade = 90;
    s1.name = "Tom";

    s2.grade = 80;
    s2.name = "Jerry";

    s3.grade = 100;
    s3.name = "Kevin";

    q.push(s1);
    q.push(s2);
    q.push(s3);

    while(!q.empty()){
        cout<<q.top().name<<":"<<q.top().grade<<endl;
        q.pop();
    } 
    return 0;
}

例题 小组队列

有n个小组要排成一个队列，每个小组中有若干人。

当一个人来到队列时，如果队列中已经有了自己小组的成员，他就直接插队排在自己小组成员的后面，否则就站在队伍的最后面。

请你编写一个程序，模拟这种小组队列。

输入格式：

输入将包含一个或多个测试用例。

对于每个测试用例，第一行输入团队数量t。

接下来t行，每行输入一个团队描述，每个团队描述由属于团队的元素数量和元素本身组成。

元素是0到999999范围内的整数。

一个团队最多可包含1000个元素。

最后，命令列表如下。 有三种不同的命令：

1、ENQUEUE x - 将元素x输入团队队列

2、DEQUEUE - 处理第一个元素并将其从队列中删除

3、STOP - 测试用例结束

每个命令占一行。

当输入用例t=0时，代表停止输入。

需注意：测试用例最多可包含200000（20万）个命令，因此团队队列的实现应该是高效的：

元素的入队和出队都应该只占用O(1)时间。

输出样例

对于每个测试用例，首先输出一行“Scenario #k”，其中k是测试用例的编号。

然后，对于每个DEQUEUE命令，输出出列的那个元素，每个元素占一行。

在每个测试用例（包括最后一个测试用例）输出完成后，输出一个空行。

数据范围

$1≤t≤1000$

输入样例：

2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0

输出样例：

Scenario #1
101
102
103
201
202
203

Scenario #2
259001
259002
259003
259004
259005
260001

题解

这道题有两个坑的地方。

1. 输入输出很坑。
2. 语法很坑。

大致思路就是，我们使用一个队列+数组queue<int> team[1000]，用来存储各个小队列，其中里面的team[0]队列用来存储各个小队列的顺序。

代码

//官方代码
#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1000000, T = 1006;
int t, f[N], id = 0;
char s[10];
queue<int> q[T];

void Team_Queue() {
    q[0] = queue<int>();
    for (int i = 1; i <= t; i++) {
        int n;
        scanf("%d", &n);
        while (n--) {
            int x;
            scanf("%d", &x);
            f[x] = i;
        }
        q[i] = queue<int>();
    }
    cout << "Scenario #" << ++id << endl;
    while (scanf("%s", s) && s[0] != 'S') {
        if (s[0] == 'E') {
            int x;
            scanf("%d", &x);
            if (q[f[x]].empty()) q[0].push(f[x]);
            q[f[x]].push(x);
        } else {
            int x = q[0].front();
            printf("%d\n", q[x].front());
            q[x].pop();
            if (q[x].empty()) q[0].pop();
        }
    }
    cout << endl;
}

int main() {
    while (cin >> t && t) Team_Queue();
    return 0;
}

双端队列

对于普通的队列，我们只能从一端进，另一端出。现在我们又来了一种新的队列，是双端队列，这个队列两端都可以进行删除或插入操作，顾名思义“双端队列”。

STL deque

//a) 构造函数
deque<int> ideq
//b)增加函数
 ideq.push_front( x):双端队列头部增加一个元素X
 ideq.push_back(x):双端队列尾部增加一个元素x
//c)删除函数
ideq.pop_front():删除双端队列中最前一个元素
ideq.pop_back():删除双端队列中最后一个元素
ideq.clear():清空双端队列中元素
//d)判断函数
ideq.empty() :向量是否为空，若true,则向量中无元素
//e)大小函数
ideq.size():返回向量中元素的个数

#include <deque>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
    deque<int> ideq(20); //Create a deque ideq with 20 elements of default value 0
    deque<int>::iterator pos;
    int i;

    //使用assign()赋值  assign在计算机中就是赋值的意思
    for (i = 0; i < 20; ++i)
        ideq[i] = i;

    //输出deque
    printf("输出deque中数据:\n");
    for (i = 0; i < 20; ++i)
        printf("%d ", ideq[i]);
    putchar('\n');

    //在头尾加入新数据
    printf("\n在头尾加入新数据...\n");
    ideq.push_back(100);
    ideq.push_front(i);

    //输出deque
    printf("\n输出deque中数据:\n");
    for (pos = ideq.begin(); pos != ideq.end(); pos++)
        printf("%d ", *pos);
    putchar('\n');

    //查找
    const int FINDNUMBER = 19;
    printf("\n查找%d\n", FINDNUMBER);
    pos = find(ideq.begin(), ideq.end(), FINDNUMBER);
    if (pos != ideq.end())
        printf("find %d success\n", *pos);
    else
        printf("find failed\n");

    //在头尾删除数据
    printf("\n在头尾删除数据...\n");
    ideq.pop_back();
    ideq.pop_front();

    //输出deque
    printf("\n输出deque中数据:\n");
    for (pos = ideq.begin(); pos != ideq.end(); pos++)
        printf("%d ", *pos);
    putchar('\n');
    return 0;
}

单调队列

需要满足两个性质：

1. 队列内具有一定的单调性（优先队列）。
2. 满足普通队列性质，一端进，另一端出，不可以中间插队。

但是这样就会现矛盾了，例如一个单调增的队列：1,5,8,9，我们要插入4，这时如果只能从尾端进去的话就打破了其单调性，呢么这时的做法就是从队尾到队头，把大于4的全部T了，然后插入后的队列就变成了1,4。

应用

常用于优化动态规划（DP）问题。

例 最大子序和

输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得子序列中所有数的和最大。

输入格式

第一行输入两个整数n,m。

第二行输入n个数，代表长度为n的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

数据范围

$1≤n,m≤300000$

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

题解

先占个坑。

代码

//官方代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 300006, INF = 0x3f3f3f3f;
int n, m, s[N], q[N];

int main() {
    cin >> n >> m;
    s[0] = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        s[i] += s[i-1];
    }
    int l = 1, r = 1, ans = -INF;
    q[1] = 0;
    for (int i = 1; i <= n; i++) {
        while (l <= r && q[l] < i - m) l++;
        ans = max(ans, s[i] - s[q[l]]);
        while (l <= r && s[q[r]] >= s[i]) r--;
        q[++r] = i;
    }
    cout << ans << endl;
    return 0;
}