判断合法出栈序列（判断序列是否为正确的出栈序列）

本文实例为大家分享了C语言实现出栈序列合法性判定的具体代码，供大家参考，具体内容如下

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

输入格式
第一行一个整数n，表示输入序列的长度。(1<=n<=10000)
第二行n个整数，表示栈的压入顺序。
第三行n个整数，表示栈的出栈顺序。

输出格式
如果是弹出序列，输出yes，否则输出no。

输入样例
5
1 2 3 8 6
8 6 3 2 1

输出样例
yes

准备工作：

①定义一个栈，并且实现它的基本操作（出栈popStack()/压栈pushStack()/访问栈顶元素getTop()/判断栈是否为空isEmpty()等）
②定义两个长度为10000的整形数组的，分别表示要压入顺序的数字msg以及出栈顺序的数字target.。为了避免要书写两个for循环来输入，这里可以通过调用方法input(int *arr,int len)，每次输入msg/target的时候，只要调用这个方法即可，从而减少代码量。

解题思路：（主要是通过循环嵌套）

1、通过遍历msg，将遍历得到的数字压入到栈中。
2、每次压入数字之后，要获取栈顶元素ch，然后判断ch是否和当前target下标对应的数字相同，如果相同，那么就从栈中跳出一个元素，同时target的下标后移。这时候，我们依旧需要从栈中获取栈顶元素，那这个栈顶元素和当前target下标的数字进行比较，如果相等，那么继续重复上述的操作。
这里之所以需要这么做，是因为考虑到类似于压入一个元素之后，就跳出一个元素的可能，所以我们需要在target中找到相同的数字之后，不仅需要将target后移，同时需要将从栈中跳出原来的栈顶元素，然后拿新的栈顶元素和target当前下标的值进行比较，直到新的栈顶元素和target当前下标的值不相等。
3、如果不相等，那么这时候就将msg后移。重复1、2步骤。直到msg已经遍历完了。
4、这时候如果target已经遍历完了，那么就说明了target就是msg的一种出栈可能，否则，如果target没有遍历完，说明target不是msg的一种出栈可能。

图解:

判断合法出栈序列（判断序列是否为正确的出栈序列）

完整代码(C语言):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 #include<stdio.h> #define ERROR 0 #define OK 1 #define MAX_SIZE 10000 typedef struct NODE{ int arr[MAX_SIZE]; int top; }Node; void init(Node &s){ s.top = 0; } int pushElem(Node &s,int c){ if(s.top == MAX_SIZE) return ERROR; s.arr[s.top++] = c; return OK; } int popElem(Node &s,int &e){ if(s.top == 0) return ERROR; e = s.arr[--s.top]; return OK; } int getTop(Node &s,int &e){ if(s.top == 0) return ERROR; e = s.arr[s.top - 1]; return OK; } int isEmpty(Node &s){ return s.top == 0; } int testIsTrue(int *msg,int *target){ Node s; int ch; init(s); while(*msg != '\0'){ pushElem(s,*msg);//将压栈字符串中的字符压入栈中 //获取栈顶元素 getTop(s,ch); while(ch == *target){ //如果当前栈顶的字符和弹栈字符相同，那么就从栈中跳出 popElem(s,ch); target++;//弹栈字符串后移 /* //获取栈顶元素,这里之所以不用判断栈是否为空，是因为主要考虑ch是否等于target 而此时target已经后移了，所以并不会造成死循环 */ getTop(s,ch); } msg++;//当ch不等于弹栈字符串的字符的时候，那么就将后移 } if(*target != '\0') return 0; return 1; } void input(int *arr,int n){ int i; for(i = 0; i < n; i++) scanf("%d",&arr[i]); } int main(){ int msg[10000],target[10000]; int n,flag; printf("请输入栈的元素个数:"); scanf("%d",&n); input(msg,n);//调用input方法，从而输入n个数字 input(target,n); flag = testIsTrue(msg,target);//判断出栈顺序是否为压栈顺序的一种出栈可能 if(flag) printf("yes"); else printf("no"); return 0; }