【剑指Offer】9.《用两个栈实现队列》详解-创新互联

题目描述
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

创新互联长期为上千余家客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为双湖企业提供专业的成都网站建设、成都做网站双湖网站改版等技术服务。拥有十载丰富建站经验和众多成功案例,为您定制开发。

解题思路
栈(Stack)又叫堆栈,是一种特殊的“线性”数据结构,它是在同一端进行插入和删除数据的线性表。
栈是最基础也是最常见的数据结构之一。对于栈的操作如下图所示:
在这里插入图片描述
基本了解了栈这种数据结构之后,我们再来看如何解决这个题目。由于栈是先进后出的操作方式,而队列是先进先出的操作方式,所以为了解决这个题,我们要引入2个栈。

//正序
    Stacks1;
    //逆序
    Stacks2;

分别为正序栈和逆序栈。
当需要对队列进行尾部添加时,需要考虑以下几种情况:
1.正序栈s1与逆序栈s2都为空,则当前队列为空
2.正序栈s1为空但逆序栈s2不为空时,则当前为逆序存放于逆序栈s2中,s2中当前的操作对象是队列头部,我们需要将逆序栈s2中的数据全部pop进正序栈s1中实现reverse反转,反转之后s1中操作对象就是当前队列的尾部以实现尾部添加数据

public void appendTail(int value) {//两个都为空,所以添加的是第一个。或者目前正处于正序队列中,直接添加到序列中
        if((s1.empty()&&s2.empty())||!(s1.empty())){s1.add(value);
            return;
        }

        //当前处于逆序状态中,将其添加到正序队列中
        if(!(s2.empty())){int size=s2.size();
            for (int i = 0; i< size; i++) {s1.push(s2.pop());
            }
            s1.push(value);
        }
    }

对队列进行删除也是同理,大家可以看看代码理解一下:

public int deleteHead() {if(s1.empty()&&s2.empty()){return -1;
        }
        if(!(s2.empty())){return s2.pop();
        }
        if(!(s1.empty())){int size=s1.size();
            for (int i = 0; i< size; i++) {s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

全部解题代码

class CQueue{//正序
    Stacks1;
    //逆序
    Stacks2;
    public CQueue() {s1=new Stack<>();
        s2=new Stack<>();
    }

    public void appendTail(int value) {//两个都为空,所以添加的是第一个。或者目前正处于正序队列中,直接添加到序列中
        if((s1.empty()&&s2.empty())||!(s1.empty())){s1.add(value);
            return;
        }

        //当前处于逆序状态中,将其添加到正序队列中
        if(!(s2.empty())){int size=s2.size();
            for (int i = 0; i< size; i++) {s1.push(s2.pop());
            }
            s1.push(value);
        }
    }

    public int deleteHead() {if(s1.empty()&&s2.empty()){return -1;
        }
        if(!(s2.empty())){return s2.pop();
        }
        if(!(s1.empty())){int size=s1.size();
            for (int i = 0; i< size; i++) {s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
}

总结
该题目非常的简单且很有意思,在网上看到有别的同学说Java实现的Stack栈比较占内存,大家可以尝试以下用队列实现2个栈的方式来减少内存的使用,如果对我的解题有任何问题欢迎各位大佬在评论区进行指点,如果你喜欢我的文章的话“一键三连”(点赞、评论、收藏)支持一下吧~

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站名称:【剑指Offer】9.《用两个栈实现队列》详解-创新互联
文章位置:http://myzitong.com/article/cshhoi.html