资讯专栏INFORMATION COLUMN

我的面试准备过程--队列与栈(更新中)

EastWoodYang / 748人阅读

摘要:和三个方法的时间复杂度必须为两种解法,解法一,将最小值存入自有的数据结构中,如下所示原本的值最小值解法二,用两个栈

堆栈和队列统称线性表

简单的线性结构

数组和链表可以实现这两种数据结构

堆栈

基本理解

DFS

深度优先---按深度遍历

递归转非递归

队列

基本理解

BFS

广度优先---按层序遍历

出入栈的合法性
模拟出入栈的过程,不是入栈,就是出栈,不然就不合法

public boolean isPossible(int[] in, int[] out){
    if(in.length != out.length){
        return false;
    }
    
    Stack s = new Stack<>();
    for(int i = 0, j = 0;j < out.length; j++){
        //如果不是入栈的
        while(s.isEmpty() && s.peek() != out[j]){
            if(i >= in.length){
                return false;
            }
            s.push(in[i++]);
        }
        //那就出栈
        s.pop();
    }
    
    return true;
}

两个栈实现队列

    public class MyQueue{
        Stack s1 = new Stack<>();
        Stack s2 = new Stack<>();

        public void push(int x){
            s1.push(x);
        }

        //负负得正
        public int pop(){
            if(s2.isEmpty()){
                while(!s1.isEmpty()){
                    s2.push(s1.pop());
                }
            }
            return s2.pop();
        }

        public int peek(){
            if(s2.isEmpty()){
                while(!s1.isEmpty()){
                    s2.push(s1.pop());
                }
            }
            return s2.peek();
        }

        public boolean empty(){
            return s1.isEmpty() && s2.isEmpty();
        }

    } 

两个队列实现栈

public class MyStack {
    Queue queue1;
    Queue queue2;
    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        if(!queue1.isEmpty()){
            queue1.offer(x);
        }else{
            queue2.offer(x);
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        if(queue1.size() != 0){
            while(queue1.size() > 1){
                queue2.add(queue1.peek());
                queue1.poll();
            }
            return queue1.remove();
        }else{
            while(queue2.size() > 1){
                queue1.add(queue2.peek());
                queue2.poll();
            }
            return queue2.remove();
        }
    }
    
    /** Get the top element. */
    public int top() {
        if(queue1.size() != 0){
            while(queue1.size() > 1){
                queue2.add(queue1.poll());
            }
            int res = queue1.peek();
            queue2.add(queue1.poll());
            return res;
        }else{
            while(queue2.size() > 1){
                queue1.add(queue2.poll());
            }
            int res = queue2.peek();
            queue1.add(queue2.poll());
            return res;
        }
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

设计一个栈,除pop与push方法,还支持min方法,可返回栈元素中的最小值。push、pop和min三个方法的时间复杂度必须为O(1)

两种解法,解法一,将最小值存入自有的数据结构中,如下所示

public class MyStack extends Stack{
    
    public void push(int value){
        int newMin = Math.min(value, min());
        super.push(new NodeWithMin(value, newMin));
    }
    
    public int min(){
        if(this.isEmpty()){
            return Integer.MAX_VALUE;
        }else{
            return peek().min;
        }
    }
    
    public int pop(){
        super.pop().value;
    }
}

class NodeWithMin{
    int value;//原本的值
    int min;//最小值
    public NodeWithMin(int value, int min){
        this.value = value;
        this.min = min;
    }
}

解法二,用两个栈

public class MyStack{
        Stack s1 = new Stack<>();
        Stack s2 = new Stack<>();

        public void push(int i){
                s1.push(i);
                if(s2.isEmpty() || min() >= i){
                        s2.push(i);
                }
        }

        public int pop(){
                if(s1.peek() == min()){
                        s2.pop();
                }

                return s1.pop();
        }

        public int min(){
                return s2.peek();
        }

}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/70161.html

相关文章

  • V8 的 Error 对象与栈追踪的妙用

    摘要:现状最近在写欢迎的时候,一直为错误的栈追踪而愁。由于送入队列的是函数,因此在的参数可以放心地使用。其次,这些函数并不是立即在中调用的,而是由专门的队列处理代码来调用。 本文的讲述都是以 Node.js 环境为例子,而 Node.js 使用的 JavaScript 引擎是 V8,因此理论上 Chrome 也能适用,其它浏览器我就不清楚了。 现状 最近在写 Rize(欢迎 star) 的时...

    Luosunce 评论0 收藏0
  • 我的面试准备过程--多线程(更新)

    摘要:但是,实际中无法保证达到让步目的,因为让步的线程还有可能被线程调度程序再次选中。在大多数情况下,将导致线程从运行状态转到可运行状态,但有可能没有效果。 多线程编程 线程状态图 总是无法上传,稍后上传 常用函数 状态转换 运行中->阻塞 sleep(long millis) 在指定的毫秒数内让当前正在执行的线程休眠 join() 等待t线程终止 使用方式 Thread t =...

    zoomdong 评论0 收藏0
  • 蚂蚁金服实习生面经总结(已拿口头offer)

    摘要:我自己总结的学习的系统知识点以及面试问题,已经开源,目前已经。面试官那你都了解里面的哪些东西呢我哈哈哈这可是我的强项,从,说到,,又说到线程池,分别说了底层实现和项目中的应用。 我自己总结的Java学习的系统知识点以及面试问题,已经开源,目前已经 35k+ Star。会一直完善下去,欢迎建议和指导,同时也欢迎Star: https://github.com/Snailclimb... ...

    Lemon_95 评论0 收藏0
  • 一个 16年毕业生所经历的 PHP 面试

    摘要:正确做法是给加索引,还有联合索引,并不能避免全表扫描。 前言:有收获的话请加颗小星星,没有收获的话可以 反对 没有帮助 举报三连 有心的同学应该会看到我这个noteBook下面的其它知识,希望对你们有些许帮助。 本文地址 时间点:2017-11 一个16年毕业生所经历的php面试 一、什么是面试 二、面试准备 1. 问:什么时候开始准备? 2. 问:怎么准备? 三、面试...

    dabai 评论0 收藏0
  • 【译】JavaScript数据结构(2):栈与队列

    摘要:栈和队列是开发中最常用的两种数据结构。如果又有数据入栈,的值将增加到。如果一个数据从栈中被取出,的值将会减少为。队列与栈类似,队列也是一个线性数据结构。与栈不同的是,队列只删除最先添加的数据。现在,让我们将栈大小的实现应用到队列中。 翻译:疯狂的技术宅英文:https://code.tutsplus.com/art...说明:本文翻译自系列文章《Data Structures With...

    zlyBear 评论0 收藏0

发表评论

0条评论

EastWoodYang

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<