深入理解栈(Stack)

发布时间:2022-08-19 12:50

目录

1. 栈(Stack)之概念

2. 栈(Stack)之模拟实现

3. 栈(Stack)之使用

4.栈(Stack)之使用场景

4.1 改变元素的序列

4.2 将递归转化为循环

4.3 括号匹配

4.4 逆波兰表达式求值

4.5 出栈入栈次序匹配


1. 栈(Stack)之概念

首先明确:

栈是一种特殊的线性表,它特殊在只能在一端进行插入删除操作,并且最重要的是先进后出

深入理解栈(Stack)_第1张图片

(1)栈顶:进行数据插入和删除操作的一端 

(2)栈顶:栈顶的另一端

(3)入栈:栈的插入操作,也叫做压栈/进栈,入数据在栈顶

(4)出站:栈的删除操作,出数据也在栈顶

 下面理解一下,先进后出,看图解

深入理解栈(Stack)_第2张图片

分析一下,

1. 栈是先进后出的,那么入栈和出栈的时间复杂度是多少

因为入栈和出栈的数据都是在栈顶进行操作的 ,所以

入栈时间复杂度O(1)  出栈时间复杂度O(1)

2. 前面说的顺序存储的方式,那么栈的链式存储是什么样的

 假设栈是以单向链表存储,那么插入数据有头插和尾插

(1)入栈是尾插法,那么时间复杂度就是O(N)

         出栈,删除尾结点也是O(N)        

(2)入栈是头插法,那么时间复杂度是O(1)从头结点插入不需要遍历链表

          出栈,删除头结点就是O(1)        

所以当栈的存储方式是链式时,并且是单链表,那么对比下来,

入栈就选头插法,出栈就删除头结点

3. 如果是以双向链表来看做栈,那么从哪里入哪里出 

(1)从头入栈,从头出栈

(2)从尾入栈,从尾出栈

两种时间复杂度都是O(1)因为双向链表有头结点和尾结点,两边入栈出栈都一样


2. 栈(Stack)之模拟实现

栈继承了Vector,Vector和ArrayList类似,都是动态的顺序表,不过Vector的线程是安全的

深入理解栈(Stack)_第3张图片

先写一个栈

public int[] elem;
    public int usedSize;

    public static final int DEFAULT_CAPATI = 10;

    public MyStack() {
        elem = new int[DEFAULT_CAPATI];
    }

  1.入栈push()

入栈前先要判断栈是否满的isFull()

    public boolean isFull() {
        if (usedSize == elem.length) {
            return true;
        }
    return false;
    }
    public void push(int val) {
        //判断栈满
        if (isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = val;
        usedSize++;
    }

2.删除栈顶元素pos()

删除栈顶元素前,先判断栈空isEmpty()

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

如果栈是空的,还要写一个异常EmptyStackException

public class EmptyStackException extends RuntimeException{
    public EmptyStackException() {

    }
    public EmptyStackException(String msg) {
        super(msg);
    }
}
    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException("栈是空的");
        }
        int oldVal = elem[usedSize-1];
        usedSize--;
        return oldVal;
    }

 3.获取栈顶元素,不删除peek()

    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException("栈是空的");
        }
        return elem[usedSize-1];
    }

4.获取中有效元素个数getUsedSize()

    public int getUsedSize() {
        return usedSize;
    }

3. 栈(Stack)之使用

    public static void main(String[] args) {
        Stack stack = new Stack<>();
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(7);
        System.out.println(stack.size());
        System.out.println(stack.peek());
        stack.pop();
        System.out.println(stack.pop());
    }

 

4.栈(Stack)之使用场景

4.1 改变元素的序列

(1)先看牛客上的一道题

深入理解栈(Stack)_第4张图片 

 分析一下 ,答案选C深入理解栈(Stack)_第5张图片

(2) 若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是()

             A: 1,4,3,2      B: 2,3,4,1      C: 3,1,4,2       D: 3,4,2,1

 分析一下,答案选C

深入理解栈(Stack)_第6张图片 

2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈,然后再依次出栈,则元素出栈的顺序是()。
A: 12345ABCDE       B: EDCBA54321      C: ABCDE12345        D: 54321EDCBA
分析一下,答案选B

 深入理解栈(Stack)_第7张图片


 

4.2 将递归转化为循环

写一个逆序打印链表

(1)递归

public class Demo01 {
    static class Node{
        public int val;
        public Node next;
        public Node(int val) {
            this.val = val;
        }
    }
    public Node head;
    public void printList(Node head) {
        if (head == null) {
            return;
        }
        if (head.next == null) {
            System.out.print(head.val + " ");
            return;
        }
        printList(head.next);
        System.out.print(head.val + " ");
    }
}

(2)非递归实现

既然栈是先进后出的,那么可以将数字依次放进去,然后再pop取出栈顶元素,打印出来,这不就实现了逆序打印

    public void printList2(Node head) {
        Stack stack = new Stack<>();
        Node cur = head;
        //将元素全部依次放入栈中
        while(cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        //给栈pop取出栈顶元素然后拿出val打印
        while(!stack.empty()) {
            Node top = stack.pop();
            System.out.println(top.val + " ");
        }
    }

4.3 括号匹配

链接   20. 有效的括号 - 力扣(LeetCode)

题目要求

深入理解栈(Stack)_第8张图片

分析一下

深入理解栈(Stack)_第9张图片

 上代码

class Solution {
    public boolean isValid(String s) {
        Stack stack = new Stack<>();
        for(int i = 0; i < s.length(); i++ ) {
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }else {
                //此时ch 是右括号
                //说明走到右边括号了
                if(stack.empty()) {
                    //遇到有括号了,但是栈空了,说明1.右括号多
                    return false;
                }
                char top = stack.peek();
                if(ch == ')' && top == '(' || ch == ']' && top == '[' || ch == '}' && top == '{') {
                    //说明当前字符是匹配的
                    stack.pop();
                }else {
                    //2.左右括号不匹配
                    return false;
                }
            }
        }
        if(stack.empty()) {
            return true;
        }else {
            //3.说明是左括号多
            return false;
        }
    }
}

 

4.4 逆波兰表达式求值

链接 150. 逆波兰表达式求值 - 力扣(LeetCode)

在说这道题前先明白 逆波兰表达式又叫做后缀表达式

(1)后缀表达式又可以通过中缀表达式来转化出来(考研-选择题)

深入理解栈(Stack)_第10张图片

 所以中缀变后缀三步走

(1)按规则加括号  (2)将运算符放括号外面  (3)去掉所有括号

(2)后缀表达式计算结果(代码题)

深入理解栈(Stack)_第11张图片

后缀计算4步走

(1)将数字按顺序依次放入栈中

(2)遇到运算符后,拿出栈顶两个元素

(3)按这样的规则计算( 次栈顶元素 运算符  栈顶元素  )

(4)将计算的结果,继续放入栈中,继续执行前面操作

 好了,下面看一下这道题

深入理解栈(Stack)_第12张图片

根据前面的后缀计算4步走验证一下这个例子

深入理解栈(Stack)_第13张图片

 

class Solution {
    public int evalRPN(String[] tokens) {
        Stack stack = new Stack<>();
        for(String x : tokens) {
            if(!isOperation(x)) {
                //不是加减乘除
                //字符转成整数.放进栈中
                stack.push(Integer.parseInt(x));
            }else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch(x) {
                    case "+": stack.push(num1 + num2);
                    break;
                    case "-": stack.push(num1 - num2);
                    break;
                    case "*": stack.push(num1 * num2);
                    break; 
                    case "/": stack.push(num1 / num2);
                    break;
                }
            }
        }
        return stack.pop();
    }

    private boolean isOperation(String opera) {
        if(opera.equals("+") || opera.equals("-") || opera.equals("*") || opera.equals("/")) {
            return true;
        }
        return false;
    }
}

 


4.5 出栈入栈次序匹配

链接 栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

题目要求:

深入理解栈(Stack)_第14张图片

分析一下

深入理解栈(Stack)_第15张图片

 上代码 

import java.util.*;
import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack stack = new Stack<>();
        int j = 0;
      for(int i = 0; i < pushA.length; i++) {
          stack.push(pushA[i]);
          while(j 

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号