algorithm - 实现Stack的高效算法是什么？

Question

我遇到了一个问题。我需要通过入栈和出栈操作来实现堆栈。

输入

输入文件的第一行包含一个整数 N (1 <= N <= 10^6) – 测试用例的数量。

接下来的 N 行讲述了操作。 +意思是推。 -意思是流行。我需要打印弹出的元素。

Example
Input      Output
6
+ 1       10
+ 10      1234
-
+ 2
+ 1234
-

我写了以下代码

   public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(new File("stack.in"));
        PrintWriter pw = new PrintWriter(new File("stack.out"));
        int n=sc.nextInt(); 
        int[] stack = new int[n]; int i=0;
        while(n-->0) {
            String s = sc.next();
            if(s.equals("+")) {
                stack[i++]=sc.nextInt();
            } else {
                pw.println(stack[--i]);
            }
        }       
        sc.close(); pw.close();
    }
}

此程序给我超出时间限制。 请建议我一个有效的算法来解决这个问题。

对于每个输入文件:

Time limit:  2 seconds 
Memory limit: 256 megabytes

Answer 1

经验法则:如果您正在解决竞争性编程风格问题并且输入很大(例如，10^5 数字或更多)，Scanner太慢了。

您可以在 BufferedReader 之上使用 StringTokenizer 来加快输入速度。

它可以看起来像这样:

class FastScanner {
    private StringTokenizer tokenizer;
    private BufferedReader reader;

    public FastScanner(InputStream inputStream) {
        reader = new BufferedReader(new InputStreamReader(inputStream));
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            String line;
            try {
                line = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            if (line == null)
                return null;
            tokenizer = new StringTokenizer(line);
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
}