题解 | 栈的压入、弹出序列

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pushV int整型一维数组
 * @param pushVLen int pushV数组长度
 * @param popV int整型一维数组
 * @param popVLen int popV数组长度
 * @return bool布尔型
 */
#include <stdbool.h>
bool IsPopOrder(int* pushV, int pushVLen, int* popV, int popVLen ) {
    // write code here
    int top_push = 0;
    int top_pop = 0;
    int buffer[1000] = {1001};
    buffer[0] = pushV[0];
    int i = 0;

    while (top_pop < popVLen) {     
        if (buffer[top_push] != popV[top_pop]||top_push==-1) {
            top_push++;
            if(top_push>pushVLen){
           		return false;
        	}
            i++;
            buffer[top_push] = pushV[i];
        }
        if (buffer[top_push] == popV[top_pop]) {
            top_push--;
            top_pop++;
        }
    }
    if (top_push < 0) {
            return true;
        }
    return false;
}

本题借助一个辅助栈buffer，定义入栈栈顶指针top_push和出站栈顶指针top_pop及用来表示入栈元素下标的i。

遵循的原则为：栈为空时将一个元素入栈，并将pushV[top_push]与popV[top_pop]进行比较，相同则出栈（top_push--）,并将top_pop指针上移，不相同则继续入栈，如果直到top_push溢出都未匹配完成则判定该顺序为不能实现，最后当所有出栈元素都实现时（top_pop==popVlen）,判断入栈是否已空。