【LeetCode】 225. 用队列实现栈 2020年3月1日

本是古典何须时尚 2021-06-10 20:38 322阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 思路 ###

1.  栈的特点，先入后出；队列的特点，先入先出
2.  使用队列来实现栈，每次就要把加入的元素添加到队列的头部，用来保证先入后出，所以，每次添加元素时先把队列中的元素保存到另外的一个临时队列中，然后再向当前队列中添加元素  
    以下的图示，表示的是添加元素时进行的操作

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 2]

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 3]

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 4]  
3. 其他的操作直接堆queue进行判断即可，比较简单

入栈时间复杂度：**O(n)**  
出栈时间复杂度：**O(1)**

### code ###

class MyStack { 
    
        Queue<Integer> queue;
        Queue<Integer> queueTemp;
    
        /** * Initialize your data structure here. */
        public MyStack() { 
            queue = new LinkedList<>();
            queueTemp = new LinkedList<>();
        }
    
        /** * Push element x onto stack. */
        public void push(int x) { 
            while (!queue.isEmpty()) queueTemp.add(queue.poll());
            queue.add(x);
            while (!queueTemp.isEmpty()) queue.add(queueTemp.poll());
        }
    
        /** * Removes the element on top of the stack and returns that element. */
        public int pop() { 
            if (queue.isEmpty()) return -1;
            else return queue.poll();
        }
    
        /** * Get the top element. */
        public int top() { 
            if (queue.isEmpty()) return -1;
            else return queue.peek();
        }
    
        /** * Returns whether the stack is empty. */
        public boolean empty() { 
            return queue.isEmpty();
        }
    }
    
    /** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * boolean param_4 = obj.empty(); */

[Link 1]: https://leetcode-cn.com/problems/implement-stack-using-queues/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/e26e3512f6ca4fa79b461b09d867631b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]: /images/20210529/3321008acd444054af05f96434e3e02e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 2]: /images/20210529/16a6675238604c019a16170a1154ea5c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 3]: /images/20210529/ab0e1f0fb213494b85e3016f3cc093be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 4]: /images/20210529/c63a82c877b14d59b06d974e66a79a54.png