就是让你判断输入受限的双端队列的输出的正确性。
其实就是模拟双端队列出队的过程,要不左边出队,要不右边出队,而入队已经一定了。
用一个数组模拟输入受限的双端队列就行了。
但是写这题可太难受了,写了我大概2个半小时,各种各种小错误,没考虑周全的地方。
#include<iostream>
using namespace std;
struct node{
int head;
int tail;
int size;
int queue[1000];
};
typedef struct node dqueue;
void lpop(dqueue& q){
if(q.size==0) return;
if(q.size==1){
q.head=-1;
q.tail=-1;
}else{
q.head++;
}
q.size--;
}
void rpop(dqueue& q){
if(q.size==0 ) return;
if(q.size==1){
q.head=-1;
q.tail=-1;
}else{
q.tail--;
}
q.size--;
}
int ltop(dqueue q){
if(q.size==0) return -1;
return q.queue[q.head];
}
int rtop(dqueue q){
if(q.size==0) return -1;
return q.queue[q.tail];
}
void push(dqueue& q,int x){
if(q.size==0){
q.head=0;
q.tail=0;
q.queue[q.head]=x;
}else{
if(q.head==0){
for(int i=q.tail;i>=q.head;i--){
q.queue[i+1]=q.queue[i];
}
q.queue[q.head]=x;
q.tail++;
}else{
q.queue[--q.head]=x;
}
}
q.size++;
}
void print(dqueue q){
for(int i=0;i<10;i++){
cout << q.queue[i] <<' ';
}
cout <<'\n';
}
int main(){
/* 测试dqueue功能正确性
int x;
while(cin >>x){
if(x==-1) break;
if(x==1) lpop(q);
if(x==2) rpop(q);
if(x==3||x==4||x==5) push(q,x);
for(int i=0;i<=10;i++){
cout <<q.queue[i]<<' ';
}
cout <<'\n';
cout << ltop(q) <<' ' <<rtop(q) <<'\n';
}
*/
int n,k;
cin >> n >>k;
int a[10]={0};
for(int i=0;i<n;i++){
cin >> a[i];
}
while(k>0){
dqueue q;
q.size=0;
q.head=0;
q.tail=0;
int output[10]={0};
for(int i=0;i<n;i++){
cin >> output[i];
}
int x=0;
int tag=0;
for(int i=0;i<n;i++){
if(q.size==0){
push(q,a[x++]);
//print(q);
}
while(ltop(q)!=output[i]&&rtop(q)!=output[i]){
if(x<n){
push(q,a[x++]);
}else{
tag=1;
break;
}
}
//print(q);
if(tag==1){
break;
}else{
if(ltop(q)==output[i]){
lpop(q);
}else if(rtop(q)==output[i]){
rpop(q);
}
//print(q);
}
}
if(tag==1){
cout <<"no" <<'\n';
}else{
cout <<"yes" <<'\n';
}
k--;
}
return 0;
}
结果: