题目描述

实现一个队列，队列初始为空，支持四种操作：

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

现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。

输入格式
第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式
对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。

数据范围
$1≤M≤100000$
$1≤x≤10^9$
所有操作保证合法。

样例

输入样例：

10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

输出样例：

NO
6
YES
4

算法1

(正常队列) $复杂度不做分析$

就是用一维数组的正常做法

两个变量分别储存队列的头坐标和尾坐标加一，进行模拟

C++ 代码

#include<iostream>
using namespace std;
int que[100005],l,r;
int main(){
    int m;
    scanf("%d",&m);
    while(m--){
        char now[5];
        scanf("%s",now);
        if(now[0]=='e') //判断条件思考一下就能理解
            puts(l==r?"YES":"NO");
        else if(now[0]=='q')
            printf("%d\n",que[l]);
        else if(now[1]=='o')
            l++;
        else
            scanf("%d",&que[r++]);
    }
    return 0;
}

算法2

(环形队列) $同上$

其实就是一个小小的优化啦~

仔细思考的人会发现：

当上一个正常的队列运行相当长一段时间后……

l和r都越来越往右。。。

如果r超过了c++整型数组的最大上限………………

所以,解决办法就是：

让l和r回到前面！

这样做的好处就是，

数组的位数不再代表一次运行总共可以插入几个元素

而是代表队列里可以同时存在几个元素！

这样前面的空间问题就得到了部分解决

（没完全解决的原因是如果一直插入………………）

也就是一种用时间换空间的方法啦~

其实优化方式也很简单。

就是把 r+1 变成 r=(r==100009?0:r+1) ,

把 l+1 变成 l=(l==100009?0:l+1)

（r==100009 的原因是数组的位数是100010）

C++ 代码

#include<iostream>
using namespace std;
int A[100010],l,r,n;
string nstr;
int main(){
    scanf("%d",&n);
    while(n--){
        cin>>nstr;
        if(nstr=="push"){
            scanf("%d",&A[r]);      //输入队尾元素
            r=(r==100009?0:r+1);    //更新队尾指针
        }
        else if(nstr=="pop")
            l=(l==100009?0:l+1);    //更新队头指针
        else if(nstr=="empty")
            puts(l==r?"YES":"NO");
        else
            printf("%d\n",A[l]);
    }
    return 0;
}

算法3

(偷懒做法) $同上$

c++里有一种模拟队列的东西~

当然了，真正用队列去做题的时候不可能有时间自己去模拟一个

所以就用到了《queue》

queue是c++外接库”queue”中现成的模拟队列

（”queue”中还有priority_queue模拟优先队列
以及deque模拟双端队列
以及……反正是各种各样的队列
只不过操作函数不太一样）

C++ 代码

#include<iostream>
#include<queue>
using namespace std;
queue<int>A;
int n,x;
string nstr;
int main(){
    scanf("%d",&n);
    while(n--){
        cin>>nstr;
        if(nstr=="push"){
            scanf("%d",&x);
            A.push(x);
        }
        else if(nstr=="pop")
            A.pop();
        else if(nstr=="empty")
            puts(A.empry()?"YES":"NO");
        else
            printf("%d\n",A.front());
    }
    return 0;
}