数据结构实验之栈与队列七：出栈序列判定
Time Limit: 30 ms Memory Limit: 1000 KiB
Problem Description
给一个初始的入栈序列，其次序即为元素的入栈次序，栈顶元素可以随时出栈，每个元素只能入栈依次。输入一个入栈序列，后面依次输入多个序列，请判断这些序列是否为所给入栈序列合法的出栈序列。
例如序列1，2，3，4，5是某栈的压入顺序，序列4，5，3，2，1是该压栈序列对应的一个出栈序列，但4，3，5，1，2就不可能是该序列的出栈序列。假设压入栈的所有数字均不相等。
Input
第一行输入整数n(1<=n<=10000)，表示序列的长度。
第二行输入n个整数，表示栈的压入顺序。
第三行输入整数t（1<=t<=10）。
后面依次输入t行，每行n个整数，表示要判断的每一个出栈序列。
Output
对应每个测试案例输出一行，如果由初始入栈序列可以得到该出栈序列，则输出yes，否则输出no。
Sample Input
5
1 2 3 4 5
2
4 5 3 2 1
4 3 5 1 2
Sample Output
yes
no
将输入数组与原数组逐个比较，模拟入栈出栈即可。
分为三种情况
- 元素入栈后立即出栈
- 栈顶元素出栈
- 匹配失败
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next;
}Node;
typedef struct stack
{
Node *base,*top;
}Stack;
struct num
{
int data,next;
}s[100050];
Node *newnode()//建立节点
{
Node *t;
t = (Node *)malloc(sizeof(Node));
t->next = NULL;
return t;
};
Stack *Newstack()//建立新栈
{
Stack *t;
t = (Stack *)malloc(sizeof(Stack));
t->top = newnode();
t->base = t->top;
return t;
}
void push(Stack *t,int x)//入站
{
Node *p = newnode();
p->data = x;
p->next = t->top->next;
t->top->next = p;
t->base = p;
}
int top(Stack *t)//询问栈顶元素
{
return t->top->next->data;
}
void pop(Stack *t)//出栈
{
Node *p;
p = t->top->next;
t->top->next = t->top->next->next;
free(p);
}
int empty(Stack *t)//询问栈是否为空
{
if(t->top->next==NULL)
return 1;
return 0;
}
void del(Stack *t)//清空栈
{
while(!empty(t))
pop(t);
}
int main()
{
int n,i,t,j;
int a[10050],b[10050];
Stack *q;
q = Newstack();
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&t);
while(t--)
{
for(i=0;i<n;i++)
scanf("%d",&b[i]);
i = j = 0;
while(j<n)
{
if(i<n&&b[j]==a[i])//元素入栈后立即出栈
{
j++;
i++;
}
else
{
if(!empty(q)&&b[j]==top(q))//栈顶元素出栈
{
j++;
pop(q);
}
else if(i<n)//元素入栈
{
push(q,a[i]);
i++;
}
else//匹配失败
break;
}
}
if(empty(q))//如果栈不为空，则说明匹配失败。
printf("yes\n");
else
printf("no\n");
while(!empty(q))
pop(q);
}
return 0;
}顺序表
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Static
{
int *top,*base;
}Static;
Static newStatic()
{
Static t;
t.top = (int *)malloc(100050*sizeof(int));
t.base = t.top;
return t;
}
int top(Static t)
{
return *(t.top-1);
}
void pop(Static *t)
{
t->top--;
}
void push(Static *t,int x)
{
*(t->top++) = x;
}
int empty(Static t)
{
if(t.base==t.top)
return 1;
return 0;
}
void clear(Static *t)
{
while(!empty(*t))
pop(t);
}
int main()
{
Static k;
k = newStatic();
int n,i,a[10050],b[10050],j,t;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&t);
while(t--)
{
if(!empty(k))
clear(&k);
j = 0;
for(i=0;i<n;i++)
scanf("%d",&b[i]);
i = j = 0;
while(i<n)
{
if(j<n&&b[i]==a[j])
{
i++;
j++;
}
else if(!empty(k)&&top(k)==b[i])
{
i++;
pop(&k);
}
else if(j<n)
{
push(&k,a[j]);
j++;
}
else
break;
}
if(i!=n||!empty(k))
printf("no\n");
else
printf("yes\n");
}
return 0;
}