牛客NC272 栈的压入、弹出序列

描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

示例1

输入：

[1,2,3,4,5],[4,5,3,2,1]

返回值：

true

说明：

可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true

示例2

输入：

[1,2,3,4,5],[4,3,5,1,2]

返回值：

false

说明：

由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false

首先对这个问题进行分析，使用两个数组来表示栈的压入和弹出序列，对于示例1，有：

压入序列：

弹出序列：

由栈的后入先出（LIFO）特性和弹出序列可知，如果要使 4 这个元素第一个弹出，那么在弹出 4 时，这个元素一定在栈顶。又由栈的操作受限特性和压入序列可知，要使 元素4 在栈顶并且成为此次弹出元素，那么在元素4之前并且尚未入栈的元素一定要先入栈，并且在此过程中不能有出栈操作，否则4将不是本次弹出元素。所以，在4出栈之前，元素1，2，3，4都需要入栈，接着弹出栈顶元素，栈中剩余元素为1，2，3。经过上述过程，弹出序列中的第一个元素是合法的，下面依照上述过程讨论剩下的序列（用绿色表示栈中元素，红色表示已经合法的弹出序列）。

1，2，3，4入栈：

4出栈与弹出序列的第一个元素匹配（用紫色表示出栈）： 

这时栈中只剩元素1，2，3：

接下来要使元素5出栈，由于这时栈中本身已有元素，所以5可能位于栈顶，也可能还未入栈，如果5位于栈顶，则栈顶元素出栈与弹出序列中的5匹配，否则，根据刚才的分析，需要根据压入序列对尚未入栈的元素入栈，直到5入栈。如果发现栈顶元素不为5并且后续入栈的所有元素都不为5，那么说明这个弹出序列不是合法的栈的弹出序列。

所以，栈顶元素为3，不等于5，那么压入序列中的剩余元素依次入栈直到5入栈：

接下来，5出栈并与弹出序列匹配：

此时，栈中剩余元素为1，2，3

到此，压入序列中的所有元素已经入栈，所以接下来只有出栈操作，显然，栈的出栈顺序与弹出序列的剩余元素顺序相同，所以这个弹出序列是合法的。

根据上述分析过程就可以分析出示例2是一个非法序列，首先1，2，3，4入栈，接着4，3出栈；5入栈，5出栈；最后可以发现，如果1要比2先出栈，那么1必须在2后面入栈，这显然是不可能的。

下面给出这道题的代码：

typedef struct stack {int arr[1000];int topofstack;
} stack;int IsEmpty(stack* s) {return s->topofstack == -1;
}void push(stack* s, int k) {s->arr[++s->topofstack] = k;
}int top(stack* s) {return s->arr[s->topofstack];
}int pop(stack* s) {return s->arr[s->topofstack--];
}//此行以上均是栈的实现//pushV表示压入序列，popV表示弹出序列
bool IsPopOrder(int* pushV, int pushVLen, int* popV, int popVLen ) {// write code herestack* s = (stack*)malloc(sizeof(stack));//创建一个栈if (s == NULL) {printf("内存分配失败\\n");return false;}s->topofstack = -1;int tmp[1000];//为了方便理解，使用一个临时数组来存放在压入序列下的真实弹出序列int ptmp=-1;int ppush = 0; //用来记录当前对比的输入序列的位置int ppop = 0; //记录当前对比的输出序列的位置while (ppop < popVLen && ppush < pushVLen) {//如果有一个指针越界就停止循环if (IsEmpty(s)) {//当栈为空时，不需要考虑栈顶元素if (pushV[ppush] != popV[ppop]) {//压入序列中的元素不等于弹出序列中的元素push(s, pushV[ppush]);//就将压入序列中的这个元素入栈，并且压入序列的指针向后移动一位，直至找到与弹出序列此元素相同的元素ppush++;} else {//找到相同的元素tmp[++ptmp]=popV[ppop];//将其弹出并保存在临时数组中ppush++;//两个序列的指针均向后移动一位ppop++;continue;}} else {//当栈不为空时，需要考虑栈顶元素if (top(s) == popV[ppop]) {//当栈顶元素等于此次需要对比的弹出序列的元素tmp[++ptmp]=popV[ppop];//将其弹出，并保存在临时数组中ppop++;//弹出序列的指针向后移动一位pop(s);} else {//其余逻辑与上面相同if (pushV[ppush] != popV[ppop]) {push(s, pushV[ppush]);ppush++;} else {tmp[++ptmp]=popV[ppop];ppop++;ppush++;continue;}}}}//这里可以使用临时数组与弹出序列比较，如果相同则合法，否则非法//还可以不使用临时数组if(IsEmpty(s)){//当栈为空时，如果弹出序列对比完成，说明是合法的，因为只有两个序列中元素相同时才会进行出栈操作，所以实际上当栈为空时，序列一定合法，可以不需要判断ppopif(ppop==popVLen)return true;elsereturn false;}else{//当栈不为空时，根据代码的逻辑，ppop一定不会越界if(ppop==popVLen)//所以这层判断也可以删掉return false;else{while(!IsEmpty(s)){if(pop(s)!=popV[ppop++])return false;}}}return true;
}