jz31.栈的压入,弹出序列

题目描述

题解

辅助栈

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

  1. *初试化: *新建一个栈, 弹出序列的指针i=0
  2. *过程: * 将入栈队列中的元素按顺序压入栈中, 一旦出现栈顶元素与当前的弹出序列的元素相等, 就循环出栈
    • 循环出栈: 只要满足当前栈顶元素与当前的弹出元素相等就将该元素弹出
  3. *判断结果: * 如果是合法的弹出序列, 那么此时的栈为空, 因为都已经弹出了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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();
}
-------------本文结束感谢您的阅读-------------
可以请我喝杯奶茶吗