题解：SP28306 ADAQUEUE - Ada and Queue

Lost_Umbrella · 2025-07-22 20:57:59 · 题解

SP28306 题解

分析

其实这道题算是一道简单的模板题，它需要我们写一个队列，且队列支持以下操作：

• push_back N 将元素 N 添加到底层。

• toFront N 将元素 N 置于最前面。

• back 从背面打印数字，然后擦除它。

• front 从前面打印数字，然后擦除它。

• reverse 反转队列中的所有元素。

我们可以先从前两个操作入手：从前方和后方插入元素。可以在队列的两端进行插入和删除操作,我们可以很快想到双端队列，即deque。再看后两个操作，从背面与前面打印擦除元素，这同样可以用双端队列解决。

问题在于最后一个操作——反转。反转是将队列中的元素顺序全部倒置，例如一个队列的元素有A B C，反转操作后队列便变为C B A。所以我们不难得出以下结论：

• 一个队列反转前在前后方添加的元素，在反转后出现在了相反的位置。
• 队列反转两次后，会重新复原。

  解决

  首先，我们可以用deque完成前四个操作。而对于第五个操作反转，我们只用判断反转次数的奇偶性，偶数则打印/插入要求位置，奇数则打印/插入要求位置的相反位置。

  代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,N,v; //v记录反转次数 
deque<ll>q; 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    string s;
    for(int i=1;i<=n;i++){
        cin>>s;
        if(s=="back"){//处理从后删除输出 
            if(v%2==0){//判断反转奇偶 
                if(!q.empty()){
                    cout<<q.back()<<'\n';
                    q.pop_back();
                }
                else cout<<"No job for Ada?"<<'\n';
            }
            else{
                if(!q.empty()){
                    cout<<q.front()<<'\n';
                    q.pop_front();
                }
                else cout<<"No job for Ada?"<<'\n';
            }
        }
        if(s=="front"){//处理从前删除输出
            if(v%2==0){
                if(!q.empty()){
                    cout<<q.front()<<'\n';
                    q.pop_front();
                }
                else cout<<"No job for Ada?"<<'\n';
            }
            else{
                if(!q.empty()){
                    cout<<q.back()<<'\n';
                    q.pop_back();
                }
                else cout<<"No job for Ada?"<<'\n';
            }
        }
        if(s=="reverse"){//计算反转次数 
            v++;
        }
        if(s=="push_back"){//处理从后插入 
            cin>>N;
            v%2==0 ? q.push_back(N) : q.push_front(N);
            /*
            三元运算符
            其实等同于：
            if(v%2==0) q.push_back(c);
            else q.push_front(c); 
            下同 
            */
        }
        if(s=="toFront"){//处理从前插入 
            cin>>N;
            v%2==0 ? q.push_front(N) : q.push_back(N);
        }
    }
    return 0;
}

代码虽然看起来些许冗长，其实不难理解的awa。