栈的压入、弹出序列

⭐️ 题目描述

---

🌟 OJ链接：栈的压入、弹出序列

思路： 我们使用一个栈来模拟题目所给的压入、和弹出序列，若模拟成功则是真，模拟失败返回假。我们可以每次先从 pushV 入栈一个元素，在判断当前栈顶元素和 popV 当前元素相等，若相等则出栈，需要注意的是有可能是连续出栈，所以这里需要使用循环来判断。
  假设入栈序列和出栈序列是：[1 2 3 4 5] [4 , 5 , 3 , 2 , 1] stack => {1 , 2 , 3 , 4} 当栈入到 4 的时候与 popV 的第一个元素相等所以出栈，stack => {1 , 2 , 3} 循环继续比较为假，下一次入栈 stack => {1 , 2 , 3 , 5} 在依次循环比较后面的元素就都消了，所以如果是相等序列最后栈一定为空，若不是相同序列则栈不为空。

代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        int push_i = 0;
        int pop_i = 0;
        // 用栈来模拟 压入和弹出
        stack<int> imitate_stack;
        while (push_i < pushV.size()) {
            imitate_stack.push(pushV[push_i++]);    // 入栈

            // 检查是否和 popV 的元素相等 相等则是出栈
            // 而出栈的可能是连续出栈 所以使用 while 循环
            // 这里判断相等的时候 要考虑 pop_i 是否已经越界 且栈不为空的情况
            while (!imitate_stack.empty() && pop_i < popV.size() && imitate_stack.top() == popV[pop_i]) {
                imitate_stack.pop();
                pop_i++;
            }
        }

        // 若栈中还有元素则不是栈的弹出序列
        // 若栈中没有元素则是栈的弹出序列
        return imitate_stack.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---