简答题
偏难
#7152
双端队列 定义一个双端队列,进队操作与普通队列一样,从队尾进入。出队操作既可以从队头,也可以从队尾。编程实现这个数据结构。 时间限制:1000 内存限制:655…
双端队列
定义一个双端队列,进队操作与普通队列一样,从队尾进入。出队操作既可以从队头,也可以从队尾。编程实现这个数据结构。
时间限制:1000
内存限制:65535
输入
第一行输入一个整数t,代表测试数据的组数。 每组数据的第一行输入一个整数n,表示操作的次数。 接着输入n行,每行对应一个操作,首先输入一个整数type。
当type=1,进队操作,接着输入一个整数x,表示进入队列的元素。
当type=2,出队操作,接着输入一个整数c,c=0代表从队头出队,c=1代表从队尾出队。
n <= 1000
输出
对于每组测试数据,输出执行完所有的操作后队列中剩余的元素,元素之间用空格隔开,按队头到队尾的顺序输出,占一行。如果队列中已经没有任何的元素,输出NULL。
样例输入
2 5 1 2 1 3 1 4 2 0 2 1 6 1 1 1 2 1 3 2 0 2 1 2 0
样例输出
3 NULL
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法1
//用deque模拟一下即可
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
int n,m,type,x;
cin>>n;
for(int i=1;i<=n;i++){
cin>>m;
deque<int> q;
for(int j=1;j<=m;j++){
cin>>type>>x;
if(type==1){
q.push_back(x);
}else {
if(x==0)q.pop_front();
else q.pop_back();
}
}
if(q.empty()){
cout<<"NULL";continue;
}
while(!q.empty()){
cout<<q.front()<<" ";
q.pop_front();
}
cout<<endl;
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//解法2
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
int n, t, type, c;
int a[1005] = {0};
int Top = 0, Back = 0;
int main() {
cin >> t;
while (t--) {
Top = 0;
Back = 0;
cin >> n;
while (n--) {
cin >> type >> c;
if (type == 1) {
a[Back++] = c;
} else {
if (c == 0) {
Top++;
} else {
Back--;
}
}
}
if (Top == Back) {
cout << "NULL" << endl;
} else {
for (int i = Top; i < Back; ++i) {
cout << a[i] << " ";
}
cout << endl;
}
}
return 0;
}</pre><p><br/></p>
这道题暂未补解析。