Sword31——栈的压入、弹出序列

Sword31——栈的压入、弹出序列

方法1——模拟

• 思路：按照给定的入栈顺序和弹出顺序进行，最后栈中若无元素，则证明为可行
• 特殊情况与临界分析：无，因为pushed和popped长度相等，当二者均为空时也是可行
• 终止条件：栈为空即代表可行
• 步骤：
  • 定义一个栈
  • 定义弹出顺序数组的下标
  • foreach循环入栈顺序数组
    • 将当前元素压入栈中
    • 循环条件：栈非空，且栈顶元素等于弹出顺序数组中下标对应的元素
    • while循环
      • 弹出栈顶元素
      • 弹出顺序数组下标后移
  • 判断此时栈是否为空，为空则可行，否则不可行

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // 定义一个栈
        Deque<Integer> stack = new LinkedList<>();
        // 定义弹出顺序数组的下标
        int index = 0;
        // foreach循环
        for (int num : pushed) {
            // 将当前元素入栈
            stack.push(num);
            // 当栈顶元素等于弹出顺序数组中下标对应元素时
            while (!stack.isEmpty() && stack.peek() == popped[index]) {
                // 弹出栈顶元素
                stack.pop();
                // 下标后移
                index++;
            }
        }
        // 判断此时栈是否为空
        return stack.isEmpty();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20