P4387 【深基15.习9】验证栈序列
查看原帖
P4387 【深基15.习9】验证栈序列
313668
DoubleBean楼主2022/12/15 21:42

样例过了但测试点一个都没过,我不知道自己思路错在哪了,我的思路是检索B中的元素,如果B[i]不等于S栈顶的元素,则将A中元素压入S中,如果B[i]等于栈顶元素,则S.pop(),如果遍历完了A中元素,B中元素还没有遍历完则表示失败,我不知道我这个思路错哪了

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXNUM 100001
using namespace std;
int A[MAXNUM], B[MAXNUM];

typedef struct stack {
	int data[MAXNUM];
	int top;
}*Stack;

void init(Stack s)
{
	s->top = -1;
}

bool isempty(Stack s)
{
	return s->top == -1;
}

int top(Stack s)
{
	return s->data[s->top];
}

void Push(Stack s, int DATA)
{
	s->data[++s->top] = DATA;
}

int Pop(Stack s)
{
	return s->data[s->top--];
}

bool stackpermutation(Stack s, int len)
{
	init(s);
	int k = 0;
	for (int i = 0; i < len; i++) {
		while (isempty(s) || top(s) != B[i]) { // 记住这里是while循环,不是if判断
			if (k < len)
				Push(s, A[k++]);
			else
				return false;
		}
		Pop(s);
	}
	return isempty(s);
}


int main() {
	int q;
	scanf("%d", &q);
	Stack s = new stack;
	while (q--) {
		int n;
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			scanf("%d", &A[i]);
		for (int i = 0; i < n; i++)
			scanf("%d", &B[i]);
		if (stackpermutation(s, n))
			printf("YES");
		else
			printf("NO");
		if (q != 0)
			printf("\n");
	}
	return 0;
}
2022/12/15 21:42
加载中...