数据结构实验之栈与队列七：出栈序列判定

朱雀 2022-11-27 08:49 123阅读 0赞

## 数据结构实验之栈与队列七：出栈序列判定 ##

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  
Output  
yes  
no  
*这题先上代码，然后再解释*

#include <stdio.h>
    #include <stdlib.h>
    int main()
    {
        
    	int i, n, t, a[10010], stacks[10010],p,q,x;
    	scanf("%d", &n);
    	for (i = 0; i < n; i++)
    	{
        
    		scanf("%d", &a[i]);
    	}
    	scanf("%d", &t);
    	while (t--)
    	{
        
    		q = p = 0;
    		for (i = 0; i < n; i++)
    		{
        
    			scanf("%d", &x);
    			while (p == 0 || stacks[p - 1] != x)//p==0是栈空时将出栈的元素入栈，判断条件的后者是判断栈顶元素是否和出栈元素是否相同
    			{
        
    				if (p == n)
    				{
        
    					break;
    				}
    				else
    				{
        
    					stacks[p++] = a[q++];
    				}
    			}
    			if (stacks[p - 1] == x)
    			{
        
    				p--;
    			}
    		}
    		if (p == 0)
    		{
        
    			printf("yes\n");
    		}
    		else
    		{
        
    			printf("no\n");
    		}
    	}
    }

*首先要知道的是栈的出栈顺序是先进后出，后进先出，比如五个元素的入栈顺序是a,b,c,d,e.那么这五个元素的出栈顺序可以是e,d,c,b,a.也可以是d,e,c,b,a.这种情况下d先出栈（即d为第一个出栈），也就是说在d入栈时，a,b,c这三个元素已经入栈，并且在d出栈后，a,b,c仍在栈中，然后此时e再入栈，再按照e,c,b,a的顺序出栈。*

*此题思路：先将1,2,3,4,5存入一个数组中，然后将数组中的元素依次存入栈中，与此同时，我们需要判断栈顶元素是否与要出栈的元素相等，如果相等，就将栈顶元素出栈，若不相等，（如果4先于1,2,3要出栈，那么1,2,3一定都在栈中）则继续将数组中的元素存入栈中，直到找到相同的元素。开始的时候我们设p=0，如果按照这个思路（出栈一个，p- -；）并且所有的元素都能够按照系统给的出栈顺序出栈，最后p仍为0，即可输出yes，反之输出no*