225. Implement Stack using Queues
两个 Queue。把非空队列的n-1个压入空对列，剩的第n个出队。
push - O(1), pop O(n)
class MyStack {
Deque<Integer> queue1;
Deque<Integer> queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1 = new ArrayDeque<>();
queue2 = new ArrayDeque<>();
}
/** Push element x onto stack. */
public void push(int x) {
if (queue2.isEmpty()) {
queue1.offerLast(x);
} else if (queue1.isEmpty()) {
queue2.offerLast(x);
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
int pop = -1;
if (!queue1.isEmpty()) {
while (queue1.size() > 1) {
queue2.offerLast(queue1.pollFirst());
}
pop = queue1.pollFirst();
} else if (!queue2.isEmpty()) {
while (queue2.size() > 1) {
queue1.offerLast(queue2.pollFirst());
}
pop = queue2.pollFirst();
}
return pop;
}
/** Get the top element. */
public int top() {
int top = -1;
if (!queue1.isEmpty()) {
while (queue1.size() > 1) {
queue2.offerLast(queue1.pollFirst());
}
top = queue1.peekFirst();
queue2.offerLast(queue1.pollFirst());
} else if (!queue2.isEmpty()) {
while (queue2.size() > 1) {
queue1.offerLast(queue2.pollFirst());
}
top = queue2.peekFirst();
queue1.offerLast(queue2.pollFirst());
}
return top;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty() && queue2.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/