1 题目地址
https://leetcode.cn/problems/implement-queue-using-stacks/description/
2 题目说明
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（
push、pop、peek、empty）：实现
MyQueue类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入： ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 1, 1, false] 解释： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false
提示：
1 <= x <= 9- 最多调用
100次push、pop、peek和empty- 假设所有操作都是有效的 （例如，一个空的队列不会调用
pop或者peek操作）进阶：
- 你能否实现每个操作均摊时间复杂度为
O(1)的队列？换句话说，执行n个操作的总时间复杂度为O(n)，即使其中一个操作可能花费较长时间。
3 解题思路
定义两个栈，一个负责入栈stackIn，一个负责出栈stackOut。
逻辑：
1 入队列：先判断stackOut是否有数据
有：将stackOut依次弹出放入stackIn，然后才将新增的数据放入stackIn
否：直接放入stackIn
2 出队列：先判断stackOut中是否有数据
有：直接pop
无： 将stackIn中的数据放入stackOut，在弹出
提示：stackIn和stackOut同时只会有一个存放数据，另外一个为空
案例：
1 queue.push(1) queue.push(2) queue.push(3) // stackIn
2 queue.pop() // stackOut为空，则将stackIn中的数据pop到stackOut
3 queue.pop() // stackOut不为空，直接stackOut.pop()
4 queue.push(4) // stackOut不为空，则将stackOut.pop()到stackIn，最后stackIn.push(4)
4 代码编写
class MyQueue {
Stack<Integer> stackIn = null;
Stack<Integer> stackOut = null;
public MyQueue() {
stackIn = new Stack();
stackOut = new Stack();
}
public void push(int x) {
while (!stackOut.isEmpty()) {
stackIn.push(stackOut.pop());
}
stackIn.push(x);
}
public int pop() {
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.pop());
}
if (!stackOut.isEmpty()) {
return stackOut.pop();
}
return -1;
}
public int peek() {
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.pop());
}
if (!stackOut.isEmpty()) {
return stackOut.peek();
}
return -1;
}
public boolean empty() {
return stackOut.isEmpty() && stackIn.isEmpty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/