题解 | #两个队列实现栈#
两个队列实现栈
https://www.nowcoder.com/practice/9fc5ae0e203f4d079b68dee34818832a
先进先出，变先进后出。两个队列，
- push时，push到q1
- pop时，先将q1的元素转移到q2中，最终q1只剩一个元素，长度为1，此时即为最后push进来的，后进先出
- pop完成后，需要交换q1和q2，方便下次pop
- push操作始终在q1
public class MyStack {
// 进行push操作
Queue<Integer> q1 = new LinkedList<>();
// 进行pop操作时，存储之前的值
Queue<Integer> q2 = new LinkedList<>();
public void push(int node) {
q1.add(node);
}
public int pop() {
while (q1.size() > 1) {
q2.add(q1.poll());
}
// 交换q1和q2
Queue<Integer> tmp = q1;
q1 = q2;
q2 = tmp;
return q2.poll();
}
public int top(){
while (q1.size() > 1) {
q2.add(q1.poll());
}
int res = q1.peek();
// 最后一个也放进去q2，然后交换q1和q2
q2.add(q1.poll());
// 交换q1和q2
Queue<Integer> tmp = q1;
q1 = q2;
q2 = tmp;
return res;
}
public boolean empty() {
return q1.isEmpty() && q2.isEmpty();
}
}
