【栈】用俩个栈来实现队列（剑指Offer 09）

傷城~ 2022-10-18 14:56 29阅读 0赞

## 一、题目 ##

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，
    分别完成在队列尾部插入整数和在队列头部删除整数的功能。
    (若队列中没有元素，deleteHead 操作返回 -1 )
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

## 二、分析 ##

本题要求用栈来实现队列，也就是要让先进队的元素先出，后进队的元素后出队，这恰好和栈的性质相反。因此本题采用2个栈来是实现队列的要求，构建两个函数： appendTail() 和 deleteHead()，其主要步骤如下：

*  对于 appendTail() 函数，要求是向队列中的队尾增加元素，可以直接采用stack1来暂存新的元素。当然，需要满足先进的元素先出，只靠一个栈是不行的，所以后面借助stack2来完成。
 *  对于 deleteHead() 函数，要求是删除队首的元素，**且遵循先入队先删除的原则**。这时候，需要借助辅助栈stack2，将stack1中的元素转存至stack2中，这时候stack1栈底的元素(先入队的)就会在stack2的栈顶上stack2.top()，此时就能很方便地将先入队的元素删除stack2.pop()。
 *  需要注意的是：一次转存，将stack1中所有的元素转存至stack2中；但是，一次deleteHead()操作，只删除stack2中的一个元素。**所以在进行deleteHead()操作时，会先判断stack2中是否有元素**。如果有，则每次按顺序删除1个；如果没有，则将stack1中的元素全部转存至stack2中，然后进行删除操作。如果stack1中也没有元素，说明此时栈都是空的，因此返回-1。

## 三、题解 ##

C++实现如下：

class CQueue { 
        stack<int> stack1;
        stack<int> stack2;
    public:
        CQueue() { 
        }
    
        //将新增的元素暂存在stack1，待需要删除操作时，再一次性将多有元素转存于stack2中
        void appendTail(int value) { 
            stack1.push(value);  
        }
        
        int deleteHead() { 
            if(!stack2.empty()){      //情况1：stack2里还有之前转存的元素，则直接按顺序pop
                int ans = stack2.top();
                stack2.pop();
                return ans;
            }
            else{      //情况2：stack2是空的，进一步判断stack1里是否有元素
                if(!stack1.empty()){    //如果stack1非空，需将stack1中的元素转存于stack2中，再按照顺序pop
                    while(!stack1.empty()){ 
                        stack2.push(stack1.top());
                        stack1.pop();
                     }
                     int ans = stack2.top();
                     stack2.pop();
                     return ans;
                }
                else{     //如果stack1是空的，说明没有添加任何元素，队列是空的，返回-1
                    return -1;
                }
            }
        }
    };

提交结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]: /images/20221005/01a364050e294f65bb1049229ee158bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]: /images/20221005/5c0dccecb2904888aef2790e6e57a18c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，29人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指 Offer 09. 用两个栈实现队列

目录题目思路代码实现题目来源 [剑指 Offer 09. 用两个栈实现队列][Offer 09.] 题目思路加入队尾 ap

客官°小女子只卖身不卖艺/ 2024年03月23日 13:51/ 0 赞/ 60 阅读

相关剑指offer | 09. 用两个栈实现队列

题目内容 > 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead > ，分别完成在队列尾部插入整数和在队列头部删除整

系统管理员/ 2022年12月21日 14:55/ 0 赞/ 101 阅读

相关剑指 Offer 09. 用两个栈实现队列

题目用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(

墨蓝/ 2022年12月16日 12:00/ 0 赞/ 140 阅读

相关剑指 Offer 09. 用两个栈实现队列

题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若

谁践踏了优雅/ 2022年12月07日 12:17/ 0 赞/ 124 阅读

相关【栈】用俩个栈来实现队列（剑指Offer 09）

一、题目用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列

傷城~/ 2022年10月18日 14:56/ 0 赞/ 30 阅读

相关剑指 Offer 09. 用两个栈实现队列

链接：[https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/][https_le

朱雀/ 2022年10月16日 09:49/ 0 赞/ 139 阅读

相关剑指offer09 : 用两个栈实现队列

https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/submissions/

川长思鸟来/ 2022年10月16日 08:50/ 0 赞/ 136 阅读

相关剑指Offer09——用两个栈实现队列

问题描述：用两个栈实现队列 [剑指 Offer 09. 用两个栈实现队列][Offer 09.] 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 `appen

快来打我*/ 2022年10月08日 11:15/ 0 赞/ 126 阅读

相关剑指 Offer 09. 用两个栈实现队列

题目链接 [https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/][https

港控/mmm°/ 2022年09月07日 15:53/ 0 赞/ 130 阅读

相关剑指 Offer 09. 用两个栈实现队列

题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数

柔情只为你懂/ 2021年07月24日 19:53/ 0 赞/ 298 阅读