前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >用两个栈就能造一个队列

用两个栈就能造一个队列

作者头像
公众号袁厨的算法小屋
发布2020-11-25 09:47:24
4360
发布2020-11-25 09:47:24
举报
文章被收录于专栏:袁厨的算法小屋

如何用两个栈造一个队列

今天给大家带来一个有意思的题目,思路很easy,但是刚刷题的小伙伴,示例理解起来可能会有点费劲,花里胡哨一大堆是啥意思啊。在之前的文章《不知道这篇文章合不合你的胃口》中写了栈是先进后出,队列是先进先出。本题让我们用两个先进后出的栈,完成一个先进先出的队列。我们应该怎么实现呢?

废话不多说,大家看图

这就是具体思路,然后我们来看一下题目示例及官方提供的函数都是什么意思。

代码语言:javascript
复制
class CQueue {
    //创建队列
    public CQueue() {

    }
    //入队
    public void appendTail(int value) {

    }
    //出队
    public int deleteHead() {

    }
}

示例 1:

代码语言:javascript
复制
输入:
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出:[null,null,3,-1]

示例 2:

代码语言:javascript
复制
输入:
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]

其实也很容易理解,输入有两行第一行,为执行的函数,Cqueue代表创建队列(代表我们初始化两个栈),appendTail代表入队操作(代表stackA入栈),deleteHead代表出队操作(代表我们stackB出栈) 第二行输入代表值,分别给每个函数传入的参数,我们发现只有appendTail函数下有对应值,因为只有该函数传入参数。

大家可以点击该链接剑指 Offer 09. 用两个栈实现队列去实现一下,下面我们看代码。

代码语言:javascript
复制
class CQueue {
     //初始化两个栈
    Stack<Integer> stack1,stack2;
    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
 
    }
    //入队,我们往第一个栈压入值
    public void appendTail(int value) {
        stack1.push(value);
    }
    //出队
    public int deleteHead() {
        //大家可以自己思考一下为什么if条件为stack2.isEmpty()
        if(stack2.isEmpty()){
           //如果此时A栈没有值,则直接-1,我们可以看示例
           if(stack1.isEmpty()){
               return -1;
           }
           //将A栈的值,压入B栈中
           while(!stack1.isEmpty()){
               stack2.push(stack1.pop());
           }
        }
        return stack2.pop();
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-11-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 袁厨的算法小屋 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 如何用两个栈造一个队列
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档