插队

题目

排队的时候最讨厌插队的人！

小J和小R加入了队伍之中排队，发现走廊的杂物被搬走了，而且出现了有人插队！插队的人直接出现在队头，同时也有同学从队尾离开。他们想知道当前排在队头的是谁。

现在一共有这样的几种情况：

• 1 x：编号为 x 的同学在队尾开始排队；
• 2 x：编号为 x 的同学在队头插队；
• 3：队头的同学离开；
• 4：队尾的同学离开；
• 5：查询队头是编号为多少的同学。

输入：第一行一个整数 q，询问次数。接下来 q 个操作，操作编号为 a，若 a 为 1 或 2，则紧接着输入编号 x。
输出：对于每个操作 5 输出一行，表示队头同学的编号。

样例1：

5
1 1
1 2
5
3
5

1
2

样例2：

7
1 1
1 2
5
2 3
5
3
5

1
3
1

思路

使用双端队列 deque 模拟：队尾入队用 push_back，队头插队用 push_front，队头离开用 pop_front，队尾离开用 pop_back，查询队头用 front。逐条读入操作编号，按编号分支处理即可。

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

int main(){
    int q;
    cin>>q;
    deque<int> dq;
    for(int c=0;c<q;c++){
        int a;
        cin>>a;
        if(a==1){
            int x;
            cin>>x;
            dq.push_back(x);
        }else if(a==2){
            int y;
            cin>>y;
            dq.push_front(y);
        }else if(a==3){
            dq.pop_front();
        }else if(a==4){
            dq.pop_back();
        }else if(a==5){
            cout<<dq.front()<<endl;
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(q)，每次操作均为 O(1)。
• 空间复杂度：O(q)，deque 最多存 q 个元素。

← 返回菜鸟的coding