栈的压入弹出序列 介绍 在学习编程的过程中，我们经常会遇到栈这个数据结构。栈是一种“先进后出”的数据结构，类似于我们日常生活中的一个现象，就是一摞盘子，我们只能从最
栈的压入弹出序列
介绍
在学习编程的过程中，我们经常会遇到栈这个数据结构。栈是一种“先进后出”的数据结构，类似于我们日常生活中的一个现象，就是一摞盘子，我们只能从最上面取出或放入盘子。
在编程中，栈的压入弹出序列是一个常见的问题。给定一个栈的压入序列和一个弹出序列，我们需要判断这个弹出序列是否是合法的。
在本文中，我将会告诉你如何实现栈的压入弹出序列的算法，并提供相应的示例代码。
算法流程
下面是栈的压入弹出序列的算法流程。我们会使用一个辅助栈来模拟实际的栈操作。
graph TD
A[初始化栈和辅助栈] --> B[遍历压入序列]
B --> C{辅助栈为空或栈顶元素不等于当前弹出元素}
C -->|是| D[将当前元素压入辅助栈]
D --> E[更新弹出序列索引]
C -->|否| F[将栈顶元素弹出辅助栈]
F --> G[更新弹出序列索引]
B --> H[返回是否合法]
代码实现
下面是实现栈的压入弹出序列的示例代码：
import java.util.Stack;
public class StackSequence {
public boolean isPopOrder(int[] pushSequence, int[] popSequence) {
// 初始化栈和辅助栈
Stack<Integer> stack = new Stack<>();
int pushIndex = 0;
int popIndex = 0;
// 遍历压入序列
while (pushIndex < pushSequence.length) {
// 辅助栈为空或栈顶元素不等于当前弹出元素
if (stack.isEmpty() || stack.peek() != popSequence[popIndex]) {
// 将当前元素压入辅助栈
stack.push(pushSequence[pushIndex]);
// 更新弹出序列索引
pushIndex++;
} else {
// 将栈顶元素弹出辅助栈
stack.pop();
// 更新弹出序列索引
popIndex++;
}
}
// 返回是否合法
while (!stack.isEmpty() && popIndex < popSequence.length) {
if (stack.pop() != popSequence[popIndex]) {
return false;
}
popIndex++;
}
return true;
}
}
代码解释：
- 首先，我们需要初始化一个栈和一个辅助栈，以及两个索引变量
pushIndex和popIndex，分别用于遍历压入序列和弹出序列。 - 然后，我们使用一个循环来遍历压入序列，判断辅助栈是否为空或栈顶元素是否等于当前弹出元素。如果是，将当前元素压入辅助栈，并更新弹出序列的索引；如果不是，将栈顶元素弹出辅助栈，并更新弹出序列的索引。
- 接着，我们使用另一个循环来判断辅助栈中剩余的元素是否与弹出序列中剩余的元素相等。
- 最后，返回判断结果。
测试用例
下面是一些测试用例，用于验证我们的算法是否正确。