栈(Stack)and leetcode刷题

栈(Stack)and leetcode刷题

  • 1. 栈(Stack)的概念
  • 2. 栈(Stack)的实现
    • 2.1 用数组实现
    • 2.2 用链表实现
      • 2.2.1 用单链表实现
  • 3. leetcode刷题
    • 3.1 括号匹配问题
    • 3.2 栈的弹出压入序列
    • 3.3 逆波兰表达式求值
      • 中缀表达式和后缀表达式
    • 3.4 最小栈
  • 4. 栈、虚拟机栈、栈帧有什么区别?

1. 栈(Stack)的概念

栈是一种线性表,它的结构可以类比于无盖容器,元素遵循“先进后出”的原则

例如:将12,23,34,45,56依次放入栈中,如图:
在这里插入图片描述

当需要取出栈中的元素中,需要依次取出最上面的元素,不能直接取出下面的元素。所以,该栈取出元素的顺序只能为:56,45,34,23,12

压栈: 栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈: 栈的删除操作叫做出栈。出数据在栈顶。

值得注意的是:压栈的过程中也可以进行出栈,即压栈和出栈可以交替进行

2. 栈(Stack)的实现

栈(Stack)既可以使用数组来实现,也可以使用链表来实现

2.1 用数组实现

用数组来实现栈需要创建三个文件:MyStack.java、EmptyStackException.java、Test.java。下面仅展示MyStack.java和EmptyStackException.java文件,Test.java测试文件不做展示

MyStack.java:

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[10];
    }

    //入栈
    public void push(int val) {
        if(isFull()) {
            //扩容
            elem = Arrays.copyOf(elem, 2*elem.length);
        }
        elem[usedSize++] = val;
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    //出栈,会删除栈顶元素
    public int pop() {
        if(isEmpty()) {
            throw new EmptyStackException();
        }
        int val = elem[usedSize-1];
        usedSize--;
        return val;
    }
    //获取栈顶元素 但是不删除
    public int peek() {
        if(isEmpty()) {
            throw new EmptyStackException();
        }
        return elem[usedSize-1];
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }
}

EmptyStackException.java:

public class EmptyStackException extends RuntimeException{
    public EmptyStackException() {
    }

    public EmptyStackException(String message) {
        super(message);
    }
}

其中,EmptyStackException.java是自定义异常,用于抛出空栈异常。

2.2 用链表实现

链表分为单链表和双链表,用哪个来实现好呢?其实两个都是可以的!

2.2.1 用单链表实现

假如用单链表实现时,当压栈(或者出栈)时,用采用头插(头删)还是尾插(尾删)呢?

  • 若采用尾插和尾删,则每次都需要找到尾节点,就算用一个引用last标志尾节点,当尾删尾节点后,需要重新遍历链表找到尾节点,进而重新用last引用标记尾节点,这时的时间复杂度就是O(N)。
  • 若采用头插和头删,每次只需将头节点head向前或向后移动就可以了,时间复杂度为O(1)。

综上可知,当采用单链表实现栈时,采用头插和头删更好!

3. leetcode刷题

3.1 括号匹配问题

题目链接:有效的括号

解题思路:

  1. 遍历字符串,如果是左括号,放入栈中;如果是右括号,就与栈顶的元素比较看是否相同
  2. 如果相同,则将栈顶元素弹出;不同则返回false
  3. 再考虑左右括号数不相等的情况

代码如下:

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(ch =='(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }else {
                if(stack.isEmpty()) {
                    //左括号数少于右括号数的情况
                    return false;
                }
                char ch2 = stack.peek();
                if((ch2 == '(' && ch == ')') 
                || (ch2 == '[' && ch == ']') 
                || (ch2 == '{' && ch == '}')) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if(!stack.isEmpty()){
            //左括号数多于右括号数的情况
            return false;
        }
        return true;
    }
}

3.2 栈的弹出压入序列

题目链接:JZ31 栈的压入、弹出序列

解题思路:

  1. 分别遍历pushV数组和popV数组,依次将pushV数组中元素放入栈中,每次放入一个元素到栈中的同时,比较栈顶元素是否与数组popV当前元素是否相等,相等则弹出栈顶元素
  2. 由于栈顶元素弹出后,新的栈顶元素可能与数组popV的下一个相等,因此需要循环比较
  3. 当栈为空,且popV数组遍历完时,popV数组为pushV数组的一个弹出顺序

代码如下:

public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            //注意循环的条件
            while(!stack.isEmpty() && j < popV.length && stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
        }
        if(stack.isEmpty() && j == popV.length) {
            return true;
        }
        return false;
    }

3.3 逆波兰表达式求值

中缀表达式和后缀表达式

在做这道题之前,我们需要了解什么是逆波兰表达式。逆波兰表达式又叫做后缀表达式,而我们平常所见到的表达式是一般都是中缀表达式,下面通过一个例子来讲解如何由中缀表达式得到后缀表达式

例: 中缀表达式a + bc+(de+f)g,其转换成后缀表达式则为abc+def+g+,演算过程如下图:
在这里插入图片描述
假如例子中a,b,c,d,e,f,g分别取1,2,3,4,5,6,7。由中缀表达式可以很容易求得该表达式的结果为189,那么怎么由后缀表达式求值呢?运用后缀表达式求值需要用到栈

后缀表达式求值规则: 从左往后,如果是数字,就将其放去栈中;如果是加减乘除符号,取出一个栈顶元素作为该符号的右操作数,再取出一个栈顶元素做为左操作数,计算得到的结果放入栈中,如此下去,最后栈中只会剩一个元素,这就是最终的结果
在这里插入图片描述

题目链接:150. 逆波兰表达式求值

解题思路:

  1. 遍历字符串数组,判断是数字还是符号
  2. 如果是数字,则将该数字转化为整型后,放入栈中
  3. 如果是符号,取出栈顶元素作为右操作数,再取出一个栈顶元素作为左操作数,进行运算,得到的运算结果放入栈中
  4. 最终栈中的元素即为后缀表达式的运算结果

代码如下:

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < tokens.length; i++) {
            //判断是否为符号
            if(tokens[i].equals("+") 
            || tokens[i].equals("-") 
            || tokens[i].equals("*") 
            || tokens[i].equals("/")) {
                int val2 = stack.pop();
                int val1 = stack.pop();
                int result = 0;
                //进行运算操作
                switch(tokens[i]) {
                    case "+":
                        result = val1+val2;
                        break;
                    case "-":
                        result = val1-val2;
                        break;
                    case "*":
                        result = val1*val2;
                        break;
                    case "/":
                        result = val1/val2;
                        break;
                }
                //将运算结果放入栈中
                stack.push(result);
                continue;
            }
            int val = Integer.parseInt(tokens[i]);
            stack.push(val);
        }
        return stack.pop();
    }
}

计算机的工作原理也是这样的,将你输入的中缀表达式转化为后缀表达式,再按照后缀表达式的运算规则进行运算,得到结果!

3.4 最小栈

题目链接:155. 最小栈

解题思路:

  1. 这道题想表达的意思是得到当前栈中的最小元素,而这个栈是可以压栈或出栈的,因此这个最小元素也是变化的
  2. 想解决这道题,仅仅靠一个栈是不够的。需要创建两个栈,一个普通栈stack,一个最小栈minStack

入栈:

  1. 普通栈是一定要放的,最小栈放的原则:1. 如果普通栈为空,则最小栈也要放;2.如果入栈元素小于最小栈的栈顶元素,则需要放
  2. 这时就有一个问题了:如果入栈元素等于最小栈的栈顶元素,那么需要放吗?答案是需要的!因为当出栈时,普通栈的这个元素(即最小元素)出去时,最小栈的栈顶元素也同样需要出去。如果入栈的时候不放,那么在出栈后,得到的最小元素就可能不对了!举个例子:假设普通栈里有0,1,-1,-2,2,-2,那么对应最小栈里有0,-1,-2,-2,假如普通栈最后一个元素入栈时没有放入最小栈,那么最小栈里就只有0,-1,-2,而当后面出栈时,普通栈出去了-2,最小栈的栈顶元素也是-2,同样也需要出栈。出栈后最小栈里就只有0,-1了,就说明此时普通栈的最小元素为-1,而事实上普通栈的最小元素为-2,这互相矛盾了。因此当入栈元素等于最小栈的栈顶元素,需要放入最小栈

出栈:

  1. 需要判断普通栈的出栈元素是否与最小栈的栈顶元素相等,相等则最小栈也需要出栈

代码如下:

class MinStack {
    public Stack<Integer> stack;
    public  Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.empty()) {
            minStack.push(val);
        }else {
            int peekVal = minStack.peek();
            if(val <= peekVal) {
                minStack.push(val);
            }
        }
    }
    public void pop() {
        if(stack.empty()) {
            return;
        }
        int popVal = stack.pop();
        if(popVal == minStack.peek()) {
            minStack.pop();
        }
    }
    
    public int top() {
        if(stack.empty()) {
            return -1;
        }
        return stack.peek();
    }
    
    public int getMin() {
        if(minStack.empty()) {
            return -1;
        }
        return minStack.peek();
    }
}

4. 栈、虚拟机栈、栈帧有什么区别?

栈是一种数据结构;虚拟机栈是JVM中的一块内存;当你运行一个方法,给这个方法开辟的内存叫做栈帧

上一篇:【C++】优先级队列(底层代码解释)


下一篇:python爬虫网页解析模块及测试案例详解-bs4模块