18932 出栈序列合法性判定

发布于:2024-10-15 ⋅ 阅读:(134) ⋅ 点赞:(0)

### 思路
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;
}

### 总结
- 使用一个辅助栈来模拟压入和弹出操作。
- 遍历出栈序列,依次检查每个元素是否可以通过当前的栈顶元素弹出。
- 如果当前栈顶元素与出栈序列的当前元素不匹配,则继续从压入序列中压入元素到栈中,直到匹配为止。
- 如果所有元素都能匹配,则出栈序列是合法的,否则不是。


网站公告

今日签到

点亮在社区的每一天
去签到