【问题描述】
- 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。
- 假设压入栈的所有数字均不相等。
- 无序列表内容
- 例如序列 1,2,3,4,5 是某栈的压入顺序,序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列,
- 但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。
【解题思路】
- 假设有模拟栈:demoStack,输入序列:pushSequence,输出序列:popSequence
- 使用demoStack来进行压入弹出操作,将pushSequence作为入栈元素,每次压入一个元素,
- 每次demoStack入栈一个元素都要判断一下栈顶元素是否等于pushSequence的第一个元素,
- 如果是的话对demoStack执行出栈操作,并将pushSequence向后移动一位,继续进行判断
【代码实现】
public boolean isPopOrder(int[] pushSequence, int[] popSequence) { int n = popSequence.length; Stack<Integer> demoStack = new Stack<>(); for (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) { demoStack.push(pushSequence[pushIndex]); while (popIndex < n && !demoStack.isEmpty() && demoStack.peek() == popSequence[popIndex]) { demoStack.pop(); popIndex++; } } return demoStack.isEmpty(); }