当前位置： 首页 > article >正文

数据结构之栈的详解

article 2024/9/20 16:29:06

文章目录

  • 一.什么是栈
  • 二. 栈的使用
    • 2.1栈的基本操作
    • 2.2 栈的基本使用
  • 三.栈的实现
    • 3.1 数组实现栈的方式
    • 3.2 链式栈的实现
  • 四.栈的应用
  • 4.1 括号匹配
  • 4.2 逆波兰表达式求值
      • 什么是逆波兰表达式
  • 4.3 出栈入栈次序匹配
  • 4.4 最小栈
  • 五.总结

一.什么是栈

  • 栈是一种先入后出(FILO)的线性表数据结构
  • 添加和删除操作只在表的一端进行,这一端称为栈顶,另一端称为栈底
  • 添加操作又称入栈或进栈,删除操作又称出栈

例如手枪的弹夹就是诸如此类的结构
在这里插入图片描述

二. 栈的使用

2.1栈的基本操作

栈有插入操作和删除操作,这俩个操作本身就叫入栈和出栈.具体如下图所示.
在这里插入图片描述

2.2 栈的基本使用

在这里插入图片描述

public static void main(String[] args) {
        Stack<Integer> s = new Stack();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s.size()); // 获取栈中有效元素个数---> 4
        System.out.println(s.peek()); // 获取栈顶元素---> 4
        s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
        System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
        if(s.empty()){
            System.out.println("栈空");
        }else{
            System.out.println(s.size());
        }
    }

三.栈的实现

  • 可以使用数组或链表实现栈
  • 使用数组实现时,数组的一端作为栈顶,另一端作为栈底
  • 使用链表实现时,链表的头节点作为栈顶,尾节点作为栈底
  • 实现需要包含的方法有:入栈push、出栈pop、获取栈顶top、判断是否为空isEmpty等

3.1 数组实现栈的方式

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 EmptyException("栈是空的！");
        }
        /*int val = elem[usedSize-1];
        usedSize--;
        return val;*/
       /* usedSize--;
        return elem[usedSize];*/
        return elem[--usedSize];
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }
    public int peek() {
        if(isEmpty()) {
            throw new EmptyException("栈是空的！");
        }
        return elem[usedSize-1];
    }
}

这段代码实现了一个数组栈,有以下几点:

  1. 使用数组elem存储栈元素,usedSize表示栈的大小。
  2. 构造方法初始化elem数组长度为10。
  3. 入栈操作先判断栈是否为满,若满则扩容为原来的2倍。然后将新元素添加至数组末端,usedSize增加1。
  4. isFull方法判断栈是否为满,usedSize是否等于elem数组长度。
  5. 出栈操作先判断栈是否为空,若为空则抛出异常。然后usedSize减1,返回出栈元素。
  6. isEmpty方法判断usedSize是否为0,来判断栈是否为空。
  7. peek方法获取栈顶元素,判断非空后返回elem[usedSize-1]。
  8. 扩容使用Arrays.copyOf()方法实现,扩容为原来的2倍。
    时间复杂度:
  • push:O(n),取决于是否扩容。未扩容为O(1),扩容为O(n)。
  • pop和peek:O(1)。
  • isEmpty和isFull:O(1)。
    空间复杂度:O(n),数组elem的大小。

3.2 链式栈的实现

private class Node {
    int val;
    Node next;
    public Node(int val) {
        this.val = val;
    }
}

private Node top;  // 栈顶指针

// 入栈
public void push(int val) {
    Node node = new Node(val);
    if (top == null) {
        top = node;
        return;
    }
    node.next = top;
    top = node;
}

// 出栈 
public int pop() {
    if (top == null) {
        throw new RuntimeException("栈空");
    }
    int val = top.val;
    top = top.next;
    return val; 
}

// 获取栈顶元素
public int top() {
    if (top == null) {
        throw new RuntimeException("栈空");
    }    
    return top.val;
}

// 判断栈是否为空
public boolean isEmpty() {
    return top == null; 
}

这个实现使用链表来构建栈。有以下几点:

  1. 私有内部类Node用于表示栈节点,包含val和next两个属性。
  2. top指针指向栈顶,初始指向null。
  3. 入栈操作将新节点的next指向栈顶,然后将top指向新节点。
  4. 出栈操作将top指向栈顶的next,并返回该出栈节点的值。
  5. 获取栈顶与判断非空操作均依赖top是否指向null。
  6. 额外判断栈空的情况,避免空指针异常。
    时间复杂度:入栈和出栈为O(1),与栈的大小无关。其他操作也均为O(1)。
    空间复杂度:O(n),取决于栈中元素的个数。

四.栈的应用

4.1 括号匹配

题目链接
具体思路:

  1. 定义一个栈,用于存储左括号。
  2. 遍历输入字符串的每个字符。
  3. 如果遇到左括号(、[或{,则将其压入栈。
  4. 如果遇到右括号),则弹出栈顶元素,并判断是否匹配。如果匹配则继续遍历,如果不匹配则返回false。
  5. 如果遇到右括号]或},同理弹出栈顶元素判断是否匹配,不匹配则返回false。
  6. 遍历结束后,如果栈为空则返回true,否则返回false

在这里插入图片描述

代码如下:

  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.empty()) {
                    return false;
                }
                char ch2 = stack.peek();//左括号
                if(ch == ')' && ch2 == '(' || ch == '}' && ch2 == '{' || ch == ']' && ch2 == '[') {
                    stack.pop();
                }else {
                    return false;//不匹配
                }
            }
        }
        if(!stack.empty()) {
            return false;
        }
        return true;
    }

4.2 逆波兰表达式求值

题目链接

什么是逆波兰表达式

我这里做出简单的一个解释,简单来说就是后缀表达式,我这里做出一个简单的图示
在这里插入图片描述具体思路:

  1. 定义一个栈,用于存储操作数。
  2. 遍历字符串数组tokens中的每个元素。
  3. 如果当前元素不是运算符,则直接将其PARSE为整数并压入栈。
  4. 如果当前元素是运算符,则弹出栈顶的两个操作数进行运算。
  5. 根据运算符不同,进行加减乘除运算。将结果压入栈。
  6. 遍历结束后,栈顶元素为最终结果,弹出并返回。

在这里插入图片描述

代码如下:

public int evalRPN(String[] tokens) {
        Stack<Integer> 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 x) {
        if(x.equals("+") || x.equals("-") || x.equals("/")||x.equals("*")) {
            return true;
        }
        return false;
    }

4.3 出栈入栈次序匹配

题目链接

具体思路:

  1. 定义一个栈stack和两个索引i和j,i用于遍历pushA,j用于遍历popA。
  2. 循环遍历pushA,每次将当前元素pushA[i]入栈。
  3. 当栈不为空 && 栈顶元素等于popA[j]时,循环弹出栈顶元素。同时j++。
  4. 遍历pushA结束后,检查栈是否为空。如果为空则popA为pushA的弹出序列,返回true;否则返回false
    在这里插入图片描述

代码如下:

  public boolean isPopOrder(int [] pushA,int [] popA) {

        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (j < popA.length && !stack.empty() && stack.peek().equals(popA[j])) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }

4.4 最小栈

题目链接
具体思路:

  1. 使用两个栈,stack用于存储所有元素,minStack用于存储当前最小元素。
  2. 在push操作中,先将元素val入栈stack,然后判断minStack是否为空或val是否小于等于minStack的栈顶元素。
  3. 如果minStack为空或val小于等于minStack栈顶,则也将val入栈minStack。这样minStack的栈顶始终是当前最小值。
  4. 在pop操作中,先从stack弹出元素,然后判断此元素是否等于minStack的栈顶元素,如果相等则也从minStack弹出,以保持minStack的栈顶为当前最小值。
  5. 在getMin操作中,直接返回minStack的栈顶元素,为当前最小值。

代码如下:

import java.util.Stack;

class MinStack {
    private Stack<Integer> stack ;
    private 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 {
            if(val <= minStack.peek()) {
                minStack.push(val);
            }
        }
    }
    
    public void pop() {
        if(!stack.empty()) {
            Integer val = stack.pop();
            //维护最小栈
            if (val.equals(minStack.peek())) {
                minStack.pop();
            }
        }
    }
    // peek
    public int top() {
        if(!stack.empty()) {
            return stack.peek();
        }
        return -1;
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

五.总结

  • 栈是一种先入后出的线性表数据结构
  • 可以使用数组或链表实现栈,实现需要包含的方法有入栈push、出栈pop等
  • 栈操作的时间复杂度均为O(1)
  • 栈有许多重要应用,如递归调用、表达式求值、浏览器的前进后退等

http://www.kler.cn/news/18349.html

相关文章：

  • ASP.NET Core Web API用户身份验证
  • 鸿蒙Hi3861学习七-Huawei LiteOS-M（信号量）
  • Linux网络架构: XDP, iptables/netfilter和iproute2/tc/ip/Qdiscs
  • windows环境安装运行kafka
  • Java EE--多线程（二）
  • Linux命令·netstat
  • electron +VUE 获取本地MAC地址
  • 又一起数据泄露事件五个月内的第二次
  • OpenPCDet系列 | 7.PointPillars模型测试KITTI数据集流程解析
  • 文件压缩与解压性能对比 lzop, gzip
  • CentOS 7 常用的命令，你知道多少？
  • 5.9-5.10学习总结
  • PDN Handover流程介绍
  • Java RSA密钥转换，从RSAPrivateKey得到RSAPublicKey
  • HTML5字体集合的实践经验
  • ( 位运算 ) 268. 丢失的数字 ——【Leetcode每日一题】
  • 当生命里有程序来串门——一个北邮信通大一学生的漫谈
  • Linux权限 - 概念与管理 | 文件权限的修改与转让 【详解】
  • 给你安利一款不需要魔法就能免费使用的idea插件Bito-ChatGPT
  • IO-Netty
  • Linux_红帽8学习笔记分享_10(SELinux管理与防火墙)
  • SpringBoot——入门程序的简单介绍
  • wiringPi常用函数
  • 使用 ChatGPT 辅助学习——为自己找一个老师
  • docker部署SpringBoot项目
  • 【sop】基于灵敏度分析的有源配电网智能软开关优化配置（Matlab代码实现）
  • Linux 安装 NFS 实现文件目录共享
  • SpringBoot创建和使用
  • RESTful风格（个人笔记）
  • MySQL事务：原理、类型和使用场景