Stackを実装する効率的なアルゴリズムは何ですか？

Question

私は問題に遭遇しました。 pushとpop操作でスタックを実装する必要があります。

入力

入力Fiのルの第1のラインは、単一の整数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()); 
    } 
}