锻练编程思维——每日一题：《剑指offer》用两个栈实现队列

待我称王封你为后i 2023-02-13 03:55 34阅读 0赞

今天的每日一题还算简单，虽然我看了看题解。（因为我又想的有所偏差了/(ㄒoㄒ)/~~）  
私有成员给的居然是stack容器，有点懵，好在我摸索着用这个东西，还是能迅速上手的因为它本质就是个栈。

### 目录 ###

*  题目分析
 *  题目分析
 *  题解代码

# 题目分析 #

题目描述

*  用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
 *  需要借助题目给出的代码进行分析

class Solution
    {
        
    public:
        void push(int node) {
        
            
        }
    
        int pop() {
        
            
        }
    
    private:
        stack<int> stack1;
        stack<int> stack2;
    };

# 题目分析 #

首先运用了stack容器这个无可置疑，然后补充几个前置知识。

*  **stack.push()代表往stack容器里压入一个数据（结点,后同）**
 *  **stack.pop()代表往stack容器里弹出一个数据**
 *  **stack.top()相当于取stack的top（栈顶）指针指向的栈顶数据（和咱们用C语言定义的栈有所区别，就在这里top“指针”指向的不同）**

好的，然后我们知道队列是FIFO，假设我有4个数据1、2、3、4要入队，就是按1、2、3、4的顺序入队对吧，出队也是这个顺序。但栈是LIFO，入栈顺序1、2、3、4，但是出栈顺序4、3、2、1。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]

这是对于一个队列和一个栈来说的。

*  **然后重点来了**，现在有两个栈，我把1、2、3、4入到第一个栈里（从栈顶到栈底是4、3、2、1顺序）
 *  再弹出，再入第二个栈，会发现，顺序从栈顶到栈底是1、2、3、4。
 *  这时候我在把他们出栈，出栈顺序变成1、2、3、4，
 *  **刨去中间栈1到栈2的过程，入栈出栈的顺序是不是变成了1、2、3、4？**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 1]

好，那我们动手实现一下，先实现入队（两个栈组成的队），毋庸置疑的是我们本着1、2、3、4的顺序入队，在前面的分析中**我们一定是会经过一番操作然后按照1、2、3、4原顺序出队**，所以我们不必担心元素入的是什么（管他栈还是队列），直接往里入就可以，**这里我们把元素入进栈1**，入队操作就完成了。

然后是出队，出队就需要考虑到一番操作了，这番操作就取自咱们上面重点来了那里分析的。**全入栈，全出栈，再全入另一栈，再指定元素出栈，就等于元素出队了。**

但是有一个问题，

*  我们用了一个栈来存放入队的元素并中转这些元素去起到出队作用的栈。
 *  比方说那个起到出队作用的栈，有元素了，
 *  然后你入队一个元素先到了第一个栈，
 *  然后你再出第一个栈入到第二个栈，
 *  它是不是就压住了第二个栈的原先所有元素，然后你出栈操作就会出错元素了吧，后进先出？不是的，对吧。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 2]

怎么解决呢？

*  就是如果第二批及以后入栈（队）的元素，要等待第二个栈的元素全部出栈（队），第二批及以后入栈（队）的元素再进去。

好的，因此我们就可以通过分析来写代码了

# 题解代码 #

//push操作就直接往stack1中push， pop操作需要分类一下：如果stack2为空，
    //那么需要将stack1中的数据转移到stack2中，
    //然后在对stack2进行pop，如果stack2不为空，直接pop就ok。
    class Solution
    {
        
    public:
        void push(int node) {
        
            stack1.push(node);
        }
    
        int pop() {
        
            int val;
            if(stack2.empty())//empty()函数如果栈空返回true！！！！
            {
        
                while(!stack1.empty())
                {
        
                    stack2.push(stack1.top());
                    stack1.pop();
                }
            }
            
            //不能有else，因为这个函数有返回值，你if完了，else不走，那么该返回谁呢？
            val=stack2.top();
            stack2.pop();
            return val;
            
        }
    
    private:
        stack<int> stack1;
        stack<int> stack2;
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200527134159244.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200527134207879.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200527134221404.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA==,size_16,color_FFFFFF,t_70