用java写出如何判断出栈顺序是否合理
时间: 2023-05-29 19:01:19 浏览: 107
思路:利用一个栈和一个指向入栈序列元素的指针,模拟出栈、入栈过程,并判断出栈序列是否合法。
1. 定义一个栈,一个入栈指针,初始化指针为0;
2. 遍历出栈序列元素:
- 若栈顶元素与当前出栈元素相同,则出栈,并继续遍历下一个出栈元素;
- 若栈顶元素与当前出栈元素不同,则从入栈序列中遍历指针后的元素,将其逐个入栈,直到入栈元素等于当前出栈元素,然后将其出栈;
3. 判断栈是否为空,若为空,则出栈序列合法,反之则不合法。
示例代码如下:
```
public boolean isSequenceValid(int[] pushSeq, int[] popSeq) {
if (pushSeq == null || popSeq == null || pushSeq.length != popSeq.length) {
return false;
}
Stack<Integer> stack = new Stack<>();
int pushIndex = 0;
for (int i = 0; i < popSeq.length; i++) {
int popValue = popSeq[i];
if (!stack.isEmpty() && stack.peek() == popValue) {
stack.pop();
} else {
while (pushIndex < pushSeq.length && pushSeq[pushIndex] != popValue) {
stack.push(pushSeq[pushIndex]);
pushIndex++;
}
if (pushIndex >= pushSeq.length) {
return false;
}
pushIndex++;
}
}
return stack.isEmpty();
}
```