Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, ..., N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4. 输入描述: Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space. 输出描述: For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not. 输入例子: 5 7 5 1 2 3 4 5 6 7 3 2 1 7 5 6 4 7 6 5 4 3 2 1 5 6 4 3 7 2 1 1 7 6 5 4 3 2 输出例子: YES NO NO YES NO
本题目主要考察对栈的模拟
解题思路：
对于每行要测试的数据，单独进行模拟验证，符合要求输出YES，否则输出NO。
再验证流程：
1. 设置一个索引 index = 0，如果第一个待检测数值为X，则把 index+1 ~ X的数据全部入栈，并把 index
设置为 X，同事还要保证栈的容量不能超标。之后再弹出栈顶原素，和第一个待检测数值比较。
2. 接着判断第二待检测原素Y，如果 index > Y，则直接从栈顶弹出原素和Y比较。如果 index < Y，把
index+1 ~ Y的数据全部入栈，并把 index 设置为 Y，同事还要保证栈的容量不能超标。之后再弹出栈顶原素，和待检测数值 Y
比较。 再弹出栈顶原素和待检测数值比较时，需要判断栈顶是否为空。
3. 重复操作 2 即可
在比较过程中，发现不符号要求即可终止判断。
代码如下：
import java.io.PrintStream;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static PrintStream out = System.out;
public static Scanner in = new Scanner(System.in);
public void popSequenceTest(String[] seq, int n, int capacity) {
int[] array = new int[n];
for(int i=0;i array[i] = Integer.valueOf(seq[i]); } Stack int i,j,index = 0; for(i=0;i // 需要入栈 if(array[i]>index){ for(j=index+1;j<=array[i];++j){ stack.push(j); // 栈溢出 if(stack.size()>capacity){ out.println("NO"); return; } } index = array[i]; } // 出栈异常 if(stack.empty()){ out.println("NO"); return; } // 出栈正常 int val = stack.pop(); if(val != array[i]){ // 输出的待验证的序列错误 out.println("NO"); return; } } out.println("YES"); } public void test() { int M, N, K; M = in.nextInt(); N = in.nextInt(); K = in.nextInt(); in.nextLine(); // 读取空白行 for (int i = 1; i <= K; ++i) { String[] seq = in.nextLine().split(" "); popSequenceTest(seq, N, M); } } public static void main(String[] args) { Main m = new Main(); m.test(); } }
