232. 用栈实现队列【112】

亦凉 2023-09-23 16:28 92阅读 0赞

> **难度等级：简单**

> **上一篇算法：**
> 
> [剑指 Offer 30. 包含min函数的栈【栈与队列】][Offer 30. _min]

> **力扣此题地址：**
> 
> [232. 用栈实现队列 - 力扣（Leetcode）][232. _ - _Leetcode]

### 一、题目：232. 用栈实现队列 ###

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（`push`、`pop`、`peek`、`empty`）：

实现 `MyQueue` 类：

*  `void push(int x)` 将元素 x 推到队列的末尾
 *  `int pop()` 从队列的开头移除并返回元素
 *  `int peek()` 返回队列开头的元素
 *  `boolean empty()` 如果队列为空，返回 `true` ；否则，返回 `false`

### `二、解题思路：` ###

> 创建两个ArrayDeque对象，作为两个栈，
> 
> 将一个栈当作输入栈，用于压入 push传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。
> 
> 每次 pop 或 peek 时，**若输出栈为空**则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。  
> 
> 
> **参考：**[232. 用栈实现队列 - 力扣（Leetcode）][232. _ - _Leetcode 1]

### 三、代码实现： ###

class MyQueue {
        Deque<Integer> inStack;
        Deque<Integer> outStack;
    
        public MyQueue() {
            inStack = new ArrayDeque<Integer>();
            outStack = new ArrayDeque<Integer>();
        }
    
        public void push(int x) {
            inStack.push(x);
        }
    
        public int pop() {
            if (outStack.isEmpty()) {
                in2out();
            }
            return outStack.pop();
        }
    
        public int peek() {
            if (outStack.isEmpty()) {
                in2out();
            }
            return outStack.peek();
        }
    
        public boolean empty() {
            return inStack.isEmpty() && outStack.isEmpty();
        }
    
        private void in2out() {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }

[Offer 30. _min]: https://blog.csdn.net/m0_51697147/article/details/128014085?spm=1001.2014.3001.5501
[232. _ - _Leetcode]: https://leetcode.cn/problems/implement-queue-using-stacks/
[232. _ - _Leetcode 1]: https://leetcode.cn/problems/implement-queue-using-stacks/solutions/632369/yong-zhan-shi-xian-dui-lie-by-leetcode-s-xnb6/