用栈来实现队列
算法思路
我们可以使用一个in栈和一个out栈来实现，初始入队时，把入队元素均加入in栈；当需要出队时，我们将in栈中的所有元素顺序弹出，再加入到out栈中，再从out栈弹出，即为出队；后续入队同样是加入in栈，出队需要进行判断，若out栈不为空，直接从out栈弹出元素，若out栈为空，就将in栈中的所有元素倒入out栈，然后再从out栈弹出。
用栈实现队列
代码实现
class MyQueue {
public Stack<Integer> in;
public Stack<Integer> out;
public MyQueue() {
in = new Stack<Integer>();
out = new Stack<Integer>();
}
// 倒数据
// 从in栈，把数据倒入out栈
// 1) out空了，才能倒数据
// 2) 如果倒数据，in必须倒完
private void inToOut() {
if (out.empty()) {
while (!in.empty()) {
out.push(in.pop());
}
}
}
// 入队
public void push(int x) {
in.push(x);
inToOut();
}
// 出队
public int pop() {
inToOut();
return out.pop();
}
// 返回队头元素
public int peek() {
inToOut();
return out.peek();
}
// 判空
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
}
时间复杂度：每一个元素，从入队到出队，最多进行两次入栈和两次出栈，共四次操作，故评价下来，时间复杂度为O（1）。
用队列来实现栈
算法思路
入栈时，将新元素入队，然后将此前队列中已有元素顺序出队后再入队；出栈时，弹出队头元素即可。
用队列实现栈
代码实现
class MyStack {
Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<Integer>();
}
// 入栈
public void push(int x) {
int n = queue.size();
queue.offer(x);
for (int i = 0; i < n; i++) {
queue.offer(queue.poll());
}
}
// 出栈
public int pop() {
return queue.poll();
}
// 返回栈顶元素
public int top() {
return queue.peek();
}
// 判空
public boolean empty() {
return queue.isEmpty();
}
}
时间复杂度：由于每一次入栈操作都需要对整个队列进行一次遍历，故时间复杂度为O（n）。
