编程题：One Way In, Two Ways Out

Consider a special queue which is a linear structure that allows insertions at one end, yet deletions at both ends. Your job is to check, for a given insertion sequence, if a deletion sequence is possible. For example, if we insert 1, 2, 3, 4, and 5 in order, then it is possible to obtain 1, 3, 2, 5, and 4 as an output, but impossible to obtain 5, 1, 3, 2, and 4.

### Input Specification:

Each input file contains one test case. For each case, the first line gives 2 positive integers $$N$$ and $$K$$ ($$\le 10$$), which are the number of insertions and the number of queries, respectively. Then $$N$$ distinct numbers are given in the next line, as the insertion sequence. Finally $$K$$ lines follow, each contains $$N$$ inserted numbers as the deletion sequence to be checked.

All the numbers in a line are separated by spaces.

### Output Specification:

For each deletion sequence, print in a line yes if it is indeed possible to be obtained, or no otherwise.

### Sample Input:
in
5 4
10 2 3 4 5
10 3 2 5 4
5 10 3 2 4
2 3 10 4 5
3 5 10 4 2



### Sample Output:
out
yes
no
yes
yes








答案：若无答案欢迎评论


#include <stdio.h>
#include <stdlib.h>

#define MAXN 10

typedef struct QNode* Queue;
struct QNode {
int A[MAXN];
int left, right;
};

Queue init()
{/* 初始化队列 */
Queue Q = (Queue)malloc(sizeof(struct QNode));
Q->left = 0; Q->right = -1;
return Q;
}

void enq ( int X, Queue Q )
{/* 从右端入队 */
Q->A[++Q->right] = X;
}

void deq( Queue Q, int side )
{/* 从 side 端出队，1代表左边，0代表右边 */
if (side) Q->left++;
else Q->right--;
}

int is_empty(Queue Q)
{/* 左右指针错位即为空 */
return (Q->left > Q->right)? 1:0;
}

int peek( Queue Q, int side )
{/* 返回 side 端的值，1代表左边，0代表右边 */
if (side) return Q->A[Q->left];
else return Q->A[Q->right];
}

int check (int in[], int out[], int n)
{
int i, j;
Queue Q = init();

for (i=0, j=0; i<n; i++) {
if (is_empty(Q)) { //先保证队列不为空
enq(in[j], Q); j++;
}
if (out[i]== peek(Q,1)) deq(Q,1);
else if (out[i]== peek(Q,0)) deq(Q,0);
else { //如果out[i]不在队列两端
while (out[i]!= in[j] && j<n) {
enq(in[j], Q); j++; //将in[]顺序入队，直到发现out[i]
}
if (j<n) j++; //跳过这个与out[i]相等的in[j]
else return 0; //所有剩下的in[]中都没找到out[i]，错误
}
}
return 1;
}

int main()
{
int in[MAXN], out[MAXN], N, K, i, j;

scanf("%d %d", &N, &K);
for (i=0; i<N; i++) scanf("%d", &in[i]);
for (i=0; i<K; i++) {
for (j=0; j<N; j++) scanf("%d", &out[j]);
if (check(in, out, N)) printf("yes\n");
else printf("no\n");
}
return 0;
}