题解 | 验证栈序列

import java.util.Scanner;
import java.util.Stack;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = Integer.parseInt(in.nextLine());
        while (q-- > 0) {
            int n = Integer.parseInt(in.nextLine());
            int[] pushedArr = parseInput(in.nextLine(), n);
            int[] poppedArr = parseInput(in.nextLine(), n);

            Stack<Integer> stack = new Stack<>();
            int popIndex = 0;

            for (int num : pushedArr) {
                stack.push(num);
                // 这里必须是while不能是if，因为栈中可能已经存储了多个可被pop出的元素
                while (!stack.isEmpty() && stack.peek() == poppedArr[popIndex]) { 
                    stack.pop();
                    popIndex++;
                }
            }
            System.out.println(stack.isEmpty() ? "Yes" : "No");
        }
    }

    private static int[] parseInput(String input, int n) {
        String[] parts = input.split(" ");
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = Integer.parseInt(parts[i]);
        }
        return result;
    }
}

用一个栈来模拟入栈和出栈过程。

1，顺序遍历入栈序列：每次将入栈序列的元素依次压入栈中。

2，尝试出栈：每次入栈后，检查栈顶元素是否等于当前出栈序列的下一个元素。如果相等，则弹出栈顶元素，并向右移动出栈序列指针，重复此过程直到不相等或栈为空。注意每次入栈后，尽可能多地进行出栈操作，即必须用while不能是if。

3，所有入栈操作完成后，如果栈为空，说明出栈序列合法，否则不合法。