【牛客刷题专栏】0x29:JZ31 栈的压入、弹出序列(C语言编程题)

前言

个人推荐在牛客网刷题(点击可以跳转)，它登陆后会保存刷题记录进度，重新登录时写过的题目代码不会丢失。
个人刷题练习系列专栏：个人CSDN牛客刷题专栏。题目来自：牛客/题库 / 在线编程 / 剑指offer：

问题描述：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
1. 0<=pushV.length == popV.length <=1000
1. -1000<=pushV[i]<=1000
1. 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

解法思路：

建立一个辅助栈，开始时，指针分别指向入栈数组pushV和出栈数组popV第一个元素，再让与当前出栈数组元素对应的入栈数组元素前的所有数入栈。此时栈顶元素与出栈数组元素相等，让栈顶元素出栈、出栈数组指针后移，继续判断直到不等。重复上述过程，直到入栈数组和出栈数组访问完毕，判断此时栈内是否还有元素。时间复杂度O(n)，空间复杂度O(n)。

代码结果：

#include <stdbool.h>
bool IsPopOrder(int* pushV, int pushVLen, int* popV, int popVLen ) {
    // write code here
    int stack[pushVLen],top=-1,top_in=0,top_out=0;//建立辅助栈stack，top为栈顶指针，top_in为入栈数组pushV的指针,top_out为出栈数组popV的指针
    while(top_in<pushVLen && top_out<pushVLen){
        while(top_in<pushVLen && pushV[top_in]!=popV[top_out]){
            //与当前出栈数组元素对应的入栈数组元素前的所有数入栈
            stack[++top]=pushV[top_in++];
        }
        stack[++top]=pushV[top_in++];
        while(top>-1 && stack[top]==popV[top_out]){
            //栈顶元素若与出栈数组元素相等就出栈
            top--;
            top_out++;
        }
    }
    if(top!=-1){//栈不为空匹配失败
        return false;
    }
    return true;
}