What is the efficient algorithm to implement Stack?

Question

I have come across a problem. I need to implement stack with push and pop operations.

Input

The first line of the input file contains a single integer number N (1 <= N <= 10^6) – the number of test cases.

Next N lines tells about operations. + means push. - means pop. I need to print popped element.

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

I have written following code

 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();
 }
}

This program is giving me Time Limit Exceeded. Please suggest me an efficient algorithm to solve this.

For each input file:

Time limit: 2 seconds 
Memory limit: 256 megabytes

• Antonín Lejsek: The stack is ok. The problem is somewhere in the IO. Maybe the Scanner is slow? At first You can start to store strings instead of converting ints there and back.
• NeoR: try Java collections analogous to C++ STL.Just google them
• sanapala mohanarao: @Antonin, Do you suggest to use String[] array instead of int[] ?. I tried in that way also.
• sanapala mohanarao: @NeoR, In Java Stack<> collection is there, but it is also giving me timed out.
• SomeWittyUsername: Well, analyze it. Put timestamps in your code and find the bottleneck

Answer 1

A rule of thumb: if you're solving a competitive programming style problem and the input is large (say, 10^5 numbers or more), the Scanner is too slow.

You can use a StringTokenizer on top of a BufferedReader to speed up the input.

It can look like this:

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());
 }
}