Ada the Ladybug has many things to do. She puts them into her queue. Anyway she is very indecisive, so sometime she uses the top, sometime the back and sometime she decides to reverses it.
Input
The first line consists of 1 ≤ Q ≤ 106, number of queries. Each of them contains one of following commands
back - Print number from back and then erase it
front - Print number from front and then erase it
reverse - Reverses all elements in queue
push_back N - Add element N to back
toFront N - Put element N to front
All numbers will be 0 ≤ N ≤ 100
Output
For each back/front query print appropriate number.
If you would get this type of query and the queue would be empty, print "No job for Ada?" instead.
Example Input
15
toFront 93
front
back
reverse
back
reverse
toFront 80
push_back 53
push_back 50
front
front
reverse
push_back 66
reverse
front
Example Output
93
No job for Ada?
No job for Ada?
80
53
66
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
#include<assert.h>
#include<queue>
const int INF=0x3f3f3f3f;
using namespace std;
int h[50005];
deque<int > v;
int main()
{
int n,x,flag=1;
char s[11];
scanf("%d",&n);
while(n--)
{
scanf("%s",s);
if(s[0]=='b')
{
if(v.size()==0)
printf("No job for Ada?\n");
else
{
if(flag)
{
printf("%d\n",v.back());
v.pop_back();
}
else
{
printf("%d\n",v.front());
v.pop_front();
}
}
}
else if(s[0]=='f')
{
if(v.size()==0)
{
printf("No job for Ada?\n");
}
else
{
if(flag)
{
printf("%d\n",v.front());
v.pop_front();
}
else
{
printf("%d\n",v.back());
v.pop_back();
}
}
}
else if(s[0]=='r')
{
flag=1-flag;
}
else if(s[0]=='p')
{
scanf("%d",&x);
if(flag)
{
v.push_back(x);
}
else
{
v.push_front(x);
}
}
else
{
scanf("%d",&x);
if(flag)
{
v.push_front(x);
}
else
v.push_back(x);
}
}
return 0;
}
才知道原来双端队列从前面插入也是插入到队列里面而不是覆盖前面的元素。
之前已为是覆盖了前面的元素就没有用双端队列，直接数组模拟的
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int inf=1<<29;
const int maxn=40;
const int maxm=(1<<15)+1000;
char str[1001];
int a[2000002];
int main()
{
int q;
scanf("%d",&q);
int i=2000002/2,j=2000002/2-1;
int haha=2,num;
getchar();
while(q--)
{
scanf("%s",str);
getchar();
// cout<<" q "<<q<<endl;
if(str[0]=='b')
{
if(haha%2==0)
{
if(i==j+1)
{
printf("No job for Ada?\n");
}
else
{
printf("%d\n",a[i-1]);
i--;
}
}
else
{
if(i==j+1)
{
printf("No job for Ada?\n");
}
else
{
printf("%d\n",a[j+1]);
j++;
}
}
}
if(str[0]=='f')
{
if(haha%2==0)
{
if(i==j+1)
{
printf("No job for Ada?\n");
}
else
{
printf("%d\n",a[j+1]);
j++;
}
}
else
{
if(i==j+1)
{
printf("No job for Ada?\n");
}
else
{
printf("%d\n",a[i-1]);
i--;
}
}
}
if(str[0]=='t')
{
scanf("%d",&num);
if(haha%2==0)
{
a[j]=num;
j--;
}
else
{
a[i]=num;
i++;
}
}
if(str[0]=='p')
{
scanf("%d",&num);
// getchar();
if(haha%2==0)
{
// getchar();
a[i]=num;
i++;
}
else
{
// scanf("%d",&num);
a[j]=num;
j--;
}
}
if(str[0]=='r')
{
haha++;
}
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-1618.html
