• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【Java数据结构】栈与队列 经典面试题——刷题笔记

互联网 diligentman 3小时前 2次浏览

【Java数据结构】栈与队列 经典面试题——刷题笔记

【Java数据结构】栈与队列 经典面试题——解题笔记+动图思路

  • 1. 实现一个最小栈
    • 题目:
    • 思路:
    • 实现代码
  • 2. 括号匹配问题
    • 题目:
    • 思路:
    • 实现代码
  • 3. 用队列实现栈
    • 题目:
    • 思路:
    • 实现代码:
  • 4. 用栈实现队列
    • 题目:
    • 思路:
    • 实现代码:
  • 5. 设计循环队列
    • 题目:
    • 思路:
    • 实现代码:

1. 实现一个最小栈

题目:

【Java数据结构】栈与队列 经典面试题——刷题笔记

思路:

  1. 把题目要求的最小栈内部分为两个栈,一个stack用于储存所有元素,另一个min_stack用于储存最小的元素

  2. 压入第一个元素时,这个元素就是当前栈里最小元素,所以不光要压入stack栈中也要压入min_stack栈中
    压入第二个元素的时候,要判断这个元素是否小于min_stack里的栈顶元素,如果小于,则将其压入min_stack
    总之min_stack栈顶元素要始终保持是栈里最小的元素

  3. 删除栈顶元素的时候,除了要弹出stack里的栈顶元素
    还要判断这个栈顶元素是否和min_stack栈里的栈顶元素相同,如果相同则要把min_stack栈里的栈顶元素也弹出
    因为min_stack只是辅助栈,一个元素如果在储存元素的栈里都没了,辅助栈里怎么能还有呢?

  4. 获取栈顶元素就简单了,直接用java自带的方法peek()就好了,只是获取,不操作

  5. 检索最小元素就更简单了,min_stack栈是用来干嘛的?
    就是用来存最小元素的嘛,直接弹出min_stack栈栈顶元素可以了
    这个栈顶元素必然是整个栈里的最小元素

【Java数据结构】栈与队列 经典面试题——刷题笔记

实现代码

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> MinStack;

    public MinStack() {//构造两个栈,一个普通栈,一个辅助栈
        stack = new Stack<>();
        MinStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);//压入元素
        if(MinStack.isEmpty()){
            MinStack.push(val);如果两个栈都是空,也要将此元素压入辅助栈
        }
        else{
            if(val <= MinStack.peek())//如果新压入的元素小于辅助栈栈顶元素
            MinStack.push(val);//将新元素压入辅助栈
        }
    }
    
    public void pop() {
        //如果从普通栈中弹出的元素等于辅助栈的栈顶元素,那么也要将此元素从辅助栈弹出
        if(stack.pop().equals(MinStack.peek())){//这里要用eqauls,不能用==,pop方法和peek方法返回的是一个object类型,也就是两个对象,我们要比较对象的值,如果用==,比较的是对象的地址
            MinStack.pop();//弹出辅助栈栈顶元素
        }
    }
    
    public int top() {
        if(MinStack.isEmpty()){
            return -1;
        }
        return stack.peek();//查看普通栈栈顶元素
    }
    
    public int getMin() {
        if(MinStack.isEmpty()){
            return -1;
        }
        return MinStack.peek();//查看辅助栈栈顶元素
    }
}

2. 括号匹配问题

题目:

【Java数据结构】栈与队列 经典面试题——刷题笔记

思路:

  1. 左括号和右括号是匹配关系,考虑用栈的方法实现

  2. 栈里只放三种左括号

  3. 遍历字符串,遇到左括号,将其入栈遇到右括号,就查看栈顶的左括号,看是否能匹配。如果能匹配上,就将此左括号出栈(删除),如果最后栈为空,那么它是有效的括号,反之不是。

【Java数据结构】栈与队列 经典面试题——刷题笔记

实现代码

class Solution {
    public boolean isValid(String s) {
        if(s==null||s.length()==0){
            return true;
        }

        //定义一个栈,来存放左括号
        Stack stack = new Stack();

        //遍历字符串
        for(int i =0; i<s.length(); i++){
            //获取当前i小标是一个啥字符
            char ch = s.charAt(i);
            //判断当前的字符是哪个左括号,因为题上说 只有3种左括号。
            if(ch=='('||ch=='['||ch=='{'){
                stack.push(ch);
            }else{
                //进入else 说明当前i下标是一个右括号
                //但是 要判断栈空不空,有可能第一个括号就是右括号
                if(stack.empty()){
                    //说明右括号多了
                    return false;
                }
            
               //获取栈顶元素,只是查看是否能和读取到的括号匹配,不是出栈
               char tmp = (char)stack.peek();
               if(tmp=='('&& ch == ')'||tmp=='['&& ch == ']'||tmp=='{'&& ch == '}'){
                   //如果有可匹配的,就出栈当前的栈顶的括号
                   stack.pop();
               }else{
                   //说明括号不匹配
                   return false;
               }
            }
        }
        //字符遍历完了,判断栈是否为空
        if(stack.empty()){//如果栈最终为空,说明括号刚好都匹配上了
            return true;
        }else{//左括号多了
            return false;
        }
    }
}

3. 用队列实现栈

题目:

【Java数据结构】栈与队列 经典面试题——刷题笔记
【Java数据结构】栈与队列 经典面试题——刷题笔记

思路:

  1. 栈是先进后出,队列是先进先出,所以这里用两个队列来回倒,从而实现栈
  2. 抓住一个关键点,不管入栈还是出栈,都找不为空的队列进行操作
  3. 入栈时,找到不为空的队列,从队列尾部插入元素即可,就达到了入栈的效果
  4. 出栈时,找到不为空的队列,将size-1个元素加入到另一个空的队列里,然后把这个队列最后一个元素出列,就达到了出栈效果
  5. 返回栈顶元素方法与出栈类似(注意,只查看,不删除),不过要设置一个临时变量tmp储存最后出队的那个元素,而且最后出队的这个元素也要继续加入另一个队列,不然就是出栈操作了
    【Java数据结构】栈与队列 经典面试题——刷题笔记

实现代码:

class MyStack {

    //创建两个队列
    Queue<Integer> que1;
    Queue<Integer> que2;

    public MyStack() {
        que1 = new LinkedList<>();//队列是接口,不能直接实例化
        que2 = new LinkedList<>();//队列是由链表实现的,所以要用链表来实例化队列

    }
    
    public void push(int x) {
        if(empty()){//一开始两个队列都是空的时候,默认将第一个元素插入到que1中
            que1.offer(x);
        }else{//从第二个元素开始,哪个队列不为空,对哪个队列进行插入操作
            if(que1.isEmpty()){
                que2.offer(x);
            }else{
                que1.offer(x);
            }
        }
    
    }
    
    public int pop() {
        if(empty()){
            return -1;
        }
      //出栈也是找哪个队列不为空,就对哪个队列进行操作
        if(que1.isEmpty()){
            int size = que2.size();
            for(int i =0 ; i<size-1 ;i++){
                int tmp = que2.poll();
                que1.offer(tmp);
            }
            return que2.poll();
        }else{
            int size = que1.size();
            for(int i =0 ; i<size-1 ;i++){
                int tmp = que1.poll();
                que2.offer(tmp);
            }
            return que1.poll();
        }
    }
    
    public int top() {
        if(empty()){
            return -1;
        }
     //查看栈顶元素,和出栈类似,只不过记得把队列最后一个元素继续插入到另一个队列的最后
     //不然就是出栈操作了
        if(que1.isEmpty()){
            int size = que2.size();
            int tmp = -1;
            for(int i =0 ; i<size ;i++){
                tmp = que2.poll();
                que1.offer(tmp);
            }
            return tmp;
        }else{
            int size = que1.size();
            int tmp = -1;
            for(int i =0 ; i<size ;i++){
                tmp = que1.poll();
                que2.offer(tmp);
            }
            return tmp;
        }

    }
    
    public boolean empty() {
        return que1.isEmpty() &&  que2.isEmpty();
    }
}

4. 用栈实现队列

题目:

【Java数据结构】栈与队列 经典面试题——刷题笔记

思路:

  1. 队列是先进先出,需要用到两个栈才能实现队列
  2. 指定S1为输入栈,S2为输出栈
  3. 入队时,直接将元素压入S1栈即可
  4. 出队时,要将输入栈S1中的元素依次出栈,并压入输出栈S2中,然后将S2栈顶元素出栈,这样就能实现先入队的元素先出队,有一点要注意,只有S2为空的时候,才能将输入栈S1中的元素移到S2中,不然会打乱队列顺序!
    【Java数据结构】栈与队列 经典面试题——刷题笔记

实现代码:

class MyQueue {
    //创建两个栈
    Stack<Integer> s1;//输入栈
    Stack<Integer> s2;//输出栈

    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    public void push(int x) {
        s1.push(x);//入队直接将元素压入S1即可
    }
    
    public int pop() {
        int size = s1.size();//出队时,将s1中所以元素移至s2中
        if(!s2.isEmpty()){
            return s2.pop();//s2不为空,则直接弹出栈顶元素即可
        }else{
          for(int i=0; i<size; i++){//否则要将s1中元素转移到s2中再弹出s2栈顶元素
              int tmp = s1.pop();
              s2.push(tmp);
            }
        return s2.pop();
        }
    }
    
    public int peek() {//和出队方法一样,只不过由删除变成查看,只看不删
        int size = s1.size();
        if(!s2.isEmpty()){
            return s2.peek();
        }else{
          for(int i=0; i<size; i++){
              int tmp = s1.pop();
              s2.push(tmp);
            }
        return s2.peek();
        }
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

5. 设计循环队列

题目:

【Java数据结构】栈与队列 经典面试题——刷题笔记

思路:

  1. 要设计一个循环队列,用到的是一个数组,需要设置一个front下标表示队列首元素,rear下标,表示尾元素后一个可用位置的下标
  2. 有三个关键问题要解决
    ①front和rear相遇之后,队列到底是空了还是满了?
    答:每次再放元素的时候,都去判断rear位置的下一个位置是不是front,如果是,就满了,所以要预留一个空间,不放元素
    ②rear每次存放完成之后,能不能进行rear=rear+1
    ③front每次出队之后,能不能进行front=front+1
    答:rear和front都不能直接+1,因为假设7个元素的循环队列,下标走到6了,6+1=7 数组此时能访问7下标嘛?不能,所以研究处一个公式rear/front = (rear/front+1)%len就能表示下一个位置了
    【Java数据结构】栈与队列 经典面试题——刷题笔记

【Java数据结构】栈与队列 经典面试题——刷题笔记

实现代码:

class MyCircularQueue {
    private int[] elem; //数组
    private int front;// 头
    private int rear;//尾巴下标   当前可以存放元素的下标
    
    public MyCircularQueue(int k) {
        //这里为什么是k+1: 题的描述指定要放k个,因为用我的方法实现的时候就是多一个空间出来的
        this.elem = new int[k+1];
        this.rear = 0;
        this.front = 0;
    }
    
    //入队
    public boolean enQueue(int value) {
        if(isFull()) //判断循环队列满了没有
        return false;//满了就返回false
        
        this.elem[this.rear] = value;//没满就给rear位置插入元素
        this.rear = (this.rear+1)%this.elem.length;//然后rear下标往后走一步
        //this.rear = this.rear+1;
        return true;
    }
    
    //删除  出队
    public boolean deQueue() {
         if(isEmpty()) {//先判断循环队列是否空
            return false;//空的就返回false
        }
        //循环队列不为空,就将首元素位置,front往后走一步
        //原来的元素会被以后加入的覆盖掉,或者不再能被访问到
        this.front = (this.front+1)%this.elem.length;
        return true;
    }
    
    //得到队头元素
    public int Front() {
         if(isEmpty()) {//依旧先判断是否为空
            return -1;
        }
        return this.elem[this.front];
    }
    
    //得到队尾元素  注意:当rear == 0下标的时候
    public int Rear() {
         if(isEmpty()) {//依旧先判断是否为空
            return -1;
        }
        //这里注意一个问题,我们已经知道rear-1位置就是队尾元素,可是当rear=0的时候,0-1=-1,这样不就出错了?所以遇到这种情况的时候用 循环队列的长度-1 就是0下标的上一个位置了
        int index = (this.rear == 0) ? this.elem.length-1 : this.rear-1;
        return this.elem[index];
    }
    
    public boolean isEmpty() {
        //只要他两相遇了 那么就是空的队列
        if(this.front == this.rear) {
            return true;
        }
        return false;
    }
    
    public boolean isFull() {
        //判断rear位置的下一个位置是不是front,如果是,就满了
        if((this.rear+1) % this.elem.length == this.front) {
            return true;
        }
        return false;
    }
}

🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
       ❤原创不易,如有错误,欢迎评论区留言指出,感激不尽❤
       ❤               如果觉得内容不错,给个三连不过分吧~        ❤
       ❤                            看到会回访~                                      ❤
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙


程序员灯塔
转载请注明原文链接:【Java数据结构】栈与队列 经典面试题——刷题笔记
喜欢 (0)