r/learnjava • u/pyeri • Apr 17 '24
Implementing efficient Stack data structure in Java
Having already solved the Keystrokes problem on Open Kattis using Python3, I'm now trying to re-implement the same algorithm in Java. I've come up with below class which compiles and runs fine but runs into the time-out error when I submit for evaluation. What can I do to make it more efficient?
import java.util.*;
class lyklagangriti {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
Stack<Character> l = new Stack<>();
Stack<Character> r = new Stack<>();
for(int i=0;i<s.length();i++) {
char c = s.charAt(i);
char item;
switch(c) {
case 'L':
item = l.pop();
r.push(item);
break;
case 'R':
item =r.pop();
l.push(item);
break;
case 'B':
l.pop();
break;
default:
l.push(c);
}
}
for(char c : l) {
System.out.print(c);
}
while(r.size() > 0) {
char c = r.pop();
System.out.print(c);
}
System.out.println("");
}
}Edit
Special thanks to /u/Cengo789 for suggesting ArrayDeque instead of Stack, and to /u/-doublex- for suggesting BufferedReader instead of Scanner for reading the input. After implementing these ideas, the program passes the test in only 0.21 seconds!
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
class lyklagangriti {
public static void main(String[] args) throws IOException {
//Scanner sc = new Scanner(System.in);
BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
String s = bi.readLine();
//String s = sc.nextLine();
Deque<Character> l = new ArrayDeque<Character>();
Deque<Character> r = new ArrayDeque<Character>();
for(int i=0;i<s.length();i++) {
char c = s.charAt(i);
char item;
switch(c) {
case 'L':
item = l.pollLast();
r.addFirst(item);
break;
case 'R':
item =r.pollFirst();
l.addLast(item);
break;
case 'B':
l.pollLast();
break;
default:
l.addLast(c);
}
}
StringBuilder sb = new StringBuilder(l.size() + r.size());
for(char c : l) {
sb.append(c);
}
for(char c : r) {
sb.append(c);
}
System.out.println(sb);
}
}
0
Upvotes
2
u/Cengo789 Apr 17 '24
Try using ArrayDeque instead of Stack. The Stack class is built on top of the very old Vector class and it’s synchronized. So you are probably paying for something you don’t need.