1 题目地址
232. 用栈实现队列 - 力扣（LeetCode）232. 用栈实现队列 - 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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 1myQueue.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) ，即使其中一个操作可能花费较长时间。
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();*/
