### 思路
1. 使用一个辅助栈来模拟压入和弹出操作。
2. 遍历出栈序列,依次检查每个元素是否可以通过当前的栈顶元素弹出。
3. 如果当前栈顶元素与出栈序列的当前元素不匹配,则继续从压入序列中压入元素到栈中,直到匹配为止。
4. 如果所有元素都能匹配,则出栈序列是合法的,否则不是。
### 伪代码
1. 初始化一个空栈 `stack` 和一个指针 `push_index` 指向压入序列的起始位置。
2. 遍历出栈序列的每个元素 `pop_value`:
- 如果 `stack` 不为空且 `stack` 的栈顶元素等于 `pop_value`,则弹出栈顶元素。
- 否则,从 `push_index` 开始,将压入序列的元素依次压入 `stack`,直到 `stack` 的栈顶元素等于 `pop_value` 或者 `push_index` 超出压入序列的范围。
- 如果 `stack` 的栈顶元素等于 `pop_value`,则弹出栈顶元素;否则,输出 "no" 并结束程序。
3. 如果遍历完出栈序列后,所有元素都能匹配,输出 "yes"。
### C++代码
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
bool isPopOrder(const vector<int>& pushSeq, const vector<int>& popSeq) {
stack<int> stack;
int pushIndex = 0;
for (int popValue : popSeq) {
while (stack.empty() || stack.top() != popValue) {
if (pushIndex == pushSeq.size()) {
return false;
}
stack.push(pushSeq[pushIndex++]);
}
stack.pop();
}
return true;
}
int main() {
int n;
cin >> n;
vector<int> pushSeq(n), popSeq(n);
for (int i = 0; i < n; ++i) {
cin >> pushSeq[i];
}
for (int i = 0; i < n; ++i) {
cin >> popSeq[i];
}
if (isPopOrder(pushSeq, popSeq)) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
return 0;
}
### 总结
- 使用一个辅助栈来模拟压入和弹出操作。
- 遍历出栈序列,依次检查每个元素是否可以通过当前的栈顶元素弹出。
- 如果当前栈顶元素与出栈序列的当前元素不匹配,则继续从压入序列中压入元素到栈中,直到匹配为止。
- 如果所有元素都能匹配,则出栈序列是合法的,否则不是。