精选力扣500题第27题 LeetCode 232. 用栈实现队列【c++ / java 详细题解】

﹏ヽ暗。殇╰゛Y 2021-07-25 01:38 323阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、c++代码
         *  4、java代码

### 1、题目 ###

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作`（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`（双端队列）来模拟一个栈，只要是标准的栈操作即可。

**进阶：**

*  你能否实现每个操作均摊时间复杂度为$ O(1) $的队列？换句话说，执行 `n`个操作的总时间复杂度为  O ( n ) O(n) O(n) ，即使其中一个操作可能花费较长时间。

**示例：**

输入：
    ["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` 操作）

### 2、思路 ###

模拟含有`1`,`2`,`3`元素的队列`queue`

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70][]

用两个栈`a`，`b`模拟队列，`a`是存元素的栈，`b`是辅助栈

*  1、`push(int x)`：直接将元素加入到`a`栈中
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]
 *  2、`pop()` – 即需要弹出栈底元素，我们先将`a`栈的所有元素插入辅助栈`b`中，然后弹出`b`栈顶元素，最后再将辅助栈`b`中的元素重新压入当前栈`a`中；
    
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2][]
 *  3、`peek()` – 返回栈顶元素，同理，我们先将`a`栈的所有元素插入辅助栈`b`中，然后输出`b`栈顶元素，最后再将辅助栈`b`中的元素重新压入当前栈`a`中，恢复当前栈`a`原状；
    
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3][]
 *  4、`empty()` – 返回当前栈是否为空；

**时间复杂度分析**：`push(x)` 和 `emtpy()`均只有一次操作，时间复杂度是 O ( 1 ) O(1) O(1)；`pop()`和 `peek()`涉及到 `n`次操作，所以时间复杂度是  O ( n ) O(n) O(n)。

### 3、c++代码 ###

class MyQueue { 
    public:
        /** Initialize your data structure here. */
        stack<int>a,b; //定义两个栈
        /** Initialize your data structure here. */
        
        MyQueue() { 
    
        }
        /** Push element x to the back of queue. */
         void push(int x) { 
            a.push(x);
        }
        
        /** Removes the element from in front of queue and returns that element. */
        int pop() { 
            while(a.size()) b.push(a.top()),a.pop();
            int t = b.top();    
            b.pop();
            while(b.size())   a.push(b.top()),b.pop();
            return t; 
        }
        
        /** Get the front element. */
         int peek() { 
            while(a.size()) b.push(a.top()),a.pop();
            int t = b.top();    
            while(b.size())   a.push(b.top()),b.pop();
            return t; 
        }
        
        /** Returns whether the queue is empty. */
         bool empty() { 
            return a.empty();
        }
    };
    
    /** * 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(); * bool param_4 = obj->empty(); */

### 4、java代码 ###

class MyQueue { 
        static Stack<Integer> a = new Stack<Integer>();
        static Stack<Integer> b = new Stack<Integer>();
        /** Initialize your data structure here. */
        public MyQueue() { 
            a.clear();
            b.clear();
        }
    
        /** Push element x to the back of queue. */
        public void push(int x) { 
            a.add(x);
        }
    
        /** Removes the element from in front of queue and returns that element. */
        public int pop() { 
            int n = a.size();
            for(int i = 0;i < n - 1;i ++) b.add(a.pop());
            int t = a.pop();
            for(int i = 0;i < n - 1;i ++) a.add(b.pop());
            return t;
        }
    
        /** Get the front element. */
        public int peek() { 
            int n = a.size();
            for(int i = 0;i < n - 1;i ++) b.add(a.pop());
            int t = a.peek();
            for(int i = 0;i < n - 1;i ++) a.add(b.pop());
            return t;
        }
    
        /** Returns whether the queue is empty. */
        public boolean empty() { 
            return a.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(); */

**原题链接:** [232. 用栈实现队列][232.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/fc3e1366dbb6479ab6dca2739c6c7b32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/109ed0205e8f4c40b2e22ffd9c7585a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]: /images/20210724/551d0acd13a74694bc05334f1bdd3070.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3]: /images/20210724/46860a906ff945b7add0c14284000328.png
[232.]: https://leetcode-cn.com/problems/implement-queue-using-stacks/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 4]: /images/20210724/b9c206a38d6448e0a68ae52111cc481a.png