Problem
I am taking a helper stack, which is used during dequeue. Kindly suggest improvement or some solution with less complexity.
import java.util.ArrayDeque;
import java.util.Deque;
public class MyQueueUsingTwoStack {
Deque<Integer> mainStack = new ArrayDeque<>();
Deque<Integer> helperStack = new ArrayDeque<>();
public void enqueue(int x) {
mainStack.push(x);
}
//popping up all the object from mainStack to helper stack(except the last one) and then putting all object
//from helper stack to mainStack
public int dequeue() {
while(!mainStack.isEmpty()) {
helperStack.push(mainStack.pop());
}
int pop = helperStack.pop();
while(!helperStack.isEmpty()) {
mainStack.push(helperStack.poll());
}
return pop;
}
public boolean isEmpty() {
return mainStack.isEmpty();
}
}
Solution
In dequeue, you do this:
- pop everything from main and push to helper
- pop one from helper
- pop everything from helper and push to main
Basically moving all elements, twice.
You can do better:
- if helper is empty: pop everything from main and push to helper
- pop one from helper
This will significantly reduce the number of times elements are moved.
Don’t forget to adjust isEmpty
accordingly.