左神算法学习笔记 - 014【入门】队列和栈入门题目-栈和队列相互实现
https://www.bilibili.com/video/BV1E14y1B7j4/?spm_id_from=333.1387.search.video_card.click
如何用栈实现队列，如何用队列实现栈？
用栈实现队列
我们可以用两个栈 + 一个精妙的规则来实现「先进先出」的逻辑结构。
思路如下：
两个栈一个是 in 栈，一个是 out 栈，简单来说，加入数据的时候加入 in，拿数据的时候从 out 拿
关键在于 in 的数据要「倒入」out 栈，规则如下：
out 为空的时候才能「倒」 数据
如果「倒」数据，就把 in 的数据 “倒完”
理解的关键点：通过两个栈，就相当于负负得正，让两个先进后出的结构，对外提供了一个先进先出的结构。而关于倒数据的规则，两条实际上都是在保证，数据是按顺序入队和出队的，如果 out 没空或者 in 不倒完，都不能保证这个顺序。
看一下代码：
class MyQueue {
public Stack<Integer> in;
public Stack<Integer> out;
public MyQueue() {
in = new Stack<>();
out = new Stack<>();
}
private void inToOut() {
if (out.isEmpty()) {
while (!in.isEmpty()) {
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();
}
}内部有两个栈
倒数据对应关键方法
inToOut()关于倒数据的实际：拿数据和看数据的时候，肯定要先倒数据；插入的时候顺便倒一下数据（非必要）
分析复杂度的话，对于 n 个操作，均摊的时间复杂度就是 O(1)，因为每个数都只会进出 in 和 out，各两次。不是每次进出都存在倒数据的行为，因此有的插入和弹出时间复杂度会高一点，但是均摊下来，就是常数时间。
用队列实现栈
用队列实现栈，其实也是通过某种操作，把先进先出的结构，对外呈现出后进先出的行为。而无论用一个队列还是两个队列实现栈，这种行为就是「插入的时候，把队列中已有的元素，一个一个地出队再入队」，这样每次队列的头部就是刚刚插入的数据了。我们就把队列维护成了栈的样子。
直接看用一个队列实现的代码：
class MyStack {
public Queue<Integer> queue;
public MyStack() {
queue = new LinkedList();
}
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) 的，和“栈”当前的数据量有关，没有均摊行为。其他的操作，pop peek 都是建立在“栈”维护好上的操作，都是 O(1) 常数操作。