jz31.栈的压入,弹出序列

题目描述

题解

辅助栈

需要使用一个辅助栈来完成这道题目

1. *初试化: *新建一个栈, 弹出序列的指针i=0
2. *过程: * 将入栈队列中的元素按顺序压入栈中, 一旦出现栈顶元素与当前的弹出序列的元素相等, 就循环出栈
   • 循环出栈: 只要满足当前栈顶元素与当前的弹出元素相等就将该元素弹出
3. *判断结果: * 如果是合法的弹出序列, 那么此时的栈为空, 因为都已经弹出了

public boolean validateStackSequences(int[] pushed, int[] popped) {
    if (pushed.length != popped.length) {
        return false;
    }

    LinkedList<Integer> stack = new LinkedList<>();
    int j = 0;

    for (int num : pushed) {
        stack.addLast(num);
        while (!stack.isEmpty() && stack.getLast() == popped[j]) {
            stack.pollLast();
            j++;
        }
    }
    return stack.isEmpty();
}