SP28306 题解

分析

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

push_back N 将元素 N 添加到底层。
toFront N 将元素 N 置于最前面。
back 从背面打印数字，然后擦除它。
front 从前面打印数字，然后擦除它。
reverse 反转队列中的所有元素。

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

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

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

解决

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

代码

CPP

#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。

题解：SP28306 ADAQUEUE - Ada and Queue

文章操作

SP28306 题解

分析

解决

代码

相关推荐

评论

题解：SP28306 ADAQUEUE - Ada and Queue