关阿姨带你横扫LeetCode系列之用队列实现栈|Java 刷题打卡

关阿姨带你横扫LeetCode系列之用队列实现栈|Java 刷题打卡

技术杂谈小彩虹2021-07-14 3:18:4260A+A-

关阿姨正在参加「Java主题月 - Java 刷题打卡」,详情查看 活动链接

首先跟大家阐明一点就是,每道算法题都有多种解法,我们只讲LeetCode上几种优秀的解题思路~,希望

可以帮助到大家,那我们先来看下题目描述吧~

一、题目描述:

使用队列实现栈的下列操作:

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

注意: 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。 你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。

二、思路分析:

用队列实现栈,那我们要先了解队列和栈的特性,栈是先进后出的数据结构,而队列是先进先出的数据结构。要想用队列实现先进后出,那么我们把队列中先添加的元素放到后面不就好了~ 而且,队列中也有获取、删除第一个元素的操作,所以我们重点应该是在添加元素的时候,如何将先添加的元素放到后面。让我们来看看实现吧:

三、代码演示

class MyStack {
    Queue<Integer> queue;
    public MyStack() {
        queue = new LinkedList<Integer>();
    }
   //添加元素
    public void push(int x) {
        //先获取队列中已有的元素个数
        int n = queue.size();
        //然后添加新元素
        queue.offer(x);
        //再将新元素之前的重新添加到队列,保证先添加的元素在后面,即先进后出
        for(int i=0; i<n; i++){
            queue.offer(queue.poll());
        }
    }
    //删除队列的第一个元素,即删除栈顶的元素
    public int pop() {
        return queue.poll();
    }
    //获取队列的第一个元素,即获取栈顶元素
    public int top() {
        return queue.peek();
    }
    //判断队列是否为空,即可判断栈是否为空
    public boolean empty() {
        return queue.isEmpty();
    }
}

刷题总结

如果大家还有其他解题思路,只要能实现要求,都是没问题的,条条大路通罗马,不要仅仅局限于我讲的这种解法哈~,优秀的思路和代码更具备学习意义,我们一起加油吧

点击这里复制本文地址 以上内容由权冠洲的博客整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!

支持Ctrl+Enter提交

联系我们| 本站介绍| 留言建议 | 交换友链 | 域名展示
本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除

权冠洲的博客 © All Rights Reserved.  Copyright quanguanzhou.top All Rights Reserved
苏公网安备 32030302000848号   苏ICP备20033101号-1

联系我们