class MyQueue {
Stack<Integer> s1 = new Stack();
Stack<Integer> s2 = new Stack();
// Push element x to the back of queue.
public void push(int x) {
while (!s2.isEmpty())
s1.push(s2.pop());
s1.push(x);
}
// Removes the element from in front of queue.
public void pop() {
while (!s1.isEmpty())
s2.push(s1.pop());
s2.pop();
}
// Get the front element.
public int peek() {
while (!s1.isEmpty())
s2.push(s1.pop());
return s2.peek();
}
// Return whether the queue is empty.
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
Accepted clean Java solution


Suppose you insert 1,2,3,4 in order to S1, then it looks like [4,3,2,1], then you implement a peek, S1 changes to [], S2 changes to [1,2,3,4] and you get correct answer 1. No issue here. Everything good.
However, if you continue to implement push(5), push(6) and push(7), S1 changes to [7,6,5], S2 is still [1,2,3,4], at this time when we want to peek, correct answer should be 1. But your code will make S2 change to [5,6,7,1,2,3,4], then return 5.

In my above code, when we do push, first I will push all the items from S2 to S1, so when you push(5), S1 will become
[5, 4, 3, 2, 1]
, S2 will be[]
. And then when you peek(), I will push all the items from S1 to S2, so S2 will change to[1, 2, 3, 4, 5]
and S1 will be empty.I've added a better solution.

Actually the following solution is much better, when we push, we don't need to put all the elements from
s2
tos1
.class MyQueue { Stack<Integer> s1 = new Stack<>(); Stack<Integer> s2 = new Stack<>(); // Push element x to the back of queue. public void push(int x) { s1.push(x); } // Removes the element from in front of queue. public void pop() { peek(); s2.pop(); } // Get the front element. public int peek() { if (s2.isEmpty()) { while (!s1.isEmpty()) { s2.push(s1.pop()); } } return s2.peek(); } // Return whether the queue is empty. public boolean empty() { return s1.isEmpty() && s2.isEmpty(); } }