```
class MyStack {
// Push element x onto stack.
Queue<Integer> q = new LinkedList<>();
// the element is added to the tail of the queue
// in order to simulate the stack where new element is added to the front
// after the new element is added, move all the elements in front of it to its behind
public void push(int x) {
q.add(x);
for(int i = 1; i < q.size(); i++){
int temp = q.poll();
q.add(temp);
}
}
// Removes the element on top of the stack.
public void pop() {
q.remove();
}
// Get the top element.
public int top() {
return q.peek();
}
// Return whether the stack is empty.
public boolean empty() {
return q.isEmpty();
}
}
class MyQueue {
// Push element x to the back of queue.
// use two stacks
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
// s1 is only used for storing elements
// s2 is used for output
// first, new element is pushed into s1
public void push(int x) {
s1.push(x);
}
// Removes the element from in front of queue.
// since the element is layed on the top, we need to
// simulate the queue in which it is added to the tail
// for example, the input sequence is 1,2,3,4, the ideal queue is 1,2,3,4
// after pushing, the s1 shows like
// | 4 |
// | 3 |
// | 2 |
// | 1 |
// pop the element one by one from s1 and push into s2, now s2 looks like
// | 1 |
// | 2 |
// | 3 |
// | 4 |
// now pop from s2 we get 1, which gives the same result as poping from the queue 1,2,3,4
public void pop() {
if(s2.isEmpty()){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
}
s2.pop();
}
// the peek is the same as 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());
}
}
```