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

EastWoodYang 发布于2019-08-16 10:38 / 679人阅读

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

堆栈和队列统称线性表

简单的线性结构

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

堆栈

基本理解

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();
        }

}

GPU服务器服务器托管栈和队列面试题 java 栈队列面试更新数据的存储过程 mysql 存储过程更新

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

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

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

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

Luosunce 2019-08-22 15:15 评论0 收藏0
我的面试准备过程－－多线程(更新中)

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

zoomdong 2019-08-16 10:38 评论0 收藏0
蚂蚁金服实习生面经总结(已拿口头offer)

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

Lemon_95 2019-08-19 11:38 评论0 收藏0
一个 16年毕业生所经历的 PHP 面试

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

dabai 2019-06-28 14:25 评论0 收藏0
【译】JavaScript数据结构（2）：栈与队列

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

zlyBear 2019-08-20 18:18 评论0 收藏0