AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】栈结构与应用

2024-01-07 194
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】栈结构与应用

一、栈的概述

1、栈的介绍

  1. 栈的英文为stack
  2. 栈是一个先入后出（FILO-First In Last Out）的有序列表。
  3. 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。
  4. 允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)
  5. 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

2、栈的应用场景

  1. 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
  2. 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
  3. 表达式的转换（中缀表达式转后级表达式）与求值（实际解决）。
  4. 二叉树的遍历。
  5. 图的深度优先搜索dfs。

3、栈的代码实现

1）数组实现

package work.rexhao.stack;

public class arrayStackdemo {
   

    public static void main(String[] args) {
   
        arrayStact as = new arrayStact(10);
        as.push(1);
        as.push(2);
        as.list();
        System.out.println(as.pop());
        System.out.println(as.pop());
        as.list();
    }

}

class arrayStact {
   
    int maxSize;
    int[] data;
    int top;

    /**
     * 栈的构造器
     * 
     * @param maxSize 栈的大小
     */
    arrayStact(int maxSize) {
   
        this.maxSize = maxSize;
        data = new int[maxSize];
        top = -1;
    }

    /**
     * 判空
     */
    public boolean isEmpty() {
   
        return top == -1;
    }

    /**
     * 判满
     */
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    /**
     * 弹出
     */
    public int pop() {
   
        if (isEmpty()) {
   
            System.out.println("栈空");
            return -1;
        }
        return data[top--];
    }

    /**
     * 压栈
     */
    public void push(int num) {
   
        if (isFull()) {
   
            System.out.println("栈满");
        } else {
   
            data[++top] = num;
        }
    }

    /**
     * 遍历
     */
    public void list() {
   
        if (isEmpty()) {
   
            System.out.println("栈空");
            return;
        }
        for (int i = 0; i <= top; i++) {
   
            System.out.printf("data[%d] = %d\n", i, data[i]);
        }
    }
}

2）链表实现

package work.rexhao.stack;

public class linkedListStackDemo {
   
    public static void main(String[] args) {
   
        linkedListStack lls = new linkedListStack();
        try {
   
            lls.pop();
        } catch (Exception e) {
   
            System.out.println(e.getMessage());
        }
        lls.push(1);
        lls.push(2);
        lls.pop();
        lls.push(3);
        lls.push(4);
        lls.show();
    }
}

class linkedListStack {
   
    private stackNode head = new stackNode(-1);

    /**
     * 压栈
     */
    public void push(int num) {
   
        if (head.next == null) {
   
            head.next = new stackNode(num);
            return;
        }
        stackNode temp = head.next;
        while (true) {
   
            if (temp.next == null) {
   
                temp.next = new stackNode(num);
                return;
            }
            temp = temp.next;
        }

    }

    /**
     * 出栈
     */
    public int pop() {
   
        if (isEmpty()) {
   
            throw new RuntimeException("栈空");
        }
        stackNode temp = head;
        while (true) {
   
            if (temp.next.next == null) {
   
                break;
            }
            temp = temp.next;
        }
        int ans = temp.next.getData();
        temp.next = null;
        return ans;
    }

    /**
     * 判空
     */
    public boolean isEmpty() {
   
        return head.next == null;
    }

    /**
     * 遍历
     */
    public void show() {
   
        if (isEmpty()) {
   
            return;
        }
        stackNode temp = head.next;
        while (true) {
   
            if (temp == null) {
   
                return;
            }
            System.out.println(temp.toString());
            temp = temp.next;
        }
    }
}

class stackNode {
   
    private int data;
    public stackNode next;

    stackNode(int data) {
   
        this.data = data;
    }

    public int getData() {
   
        return data;
    }

    public void setData(int data) {
   
        this.data = data;
    }

    @Override
    public String toString() {
   
        return data + "";
    }
}

二、栈实现综合计算器

1、思路

  1. 通过一个index 值（索引），来遍历我们的表达式
  2. 扫描到一个数字，直接入数栈
  3. 扫描到一个符号
    1. 符号栈为空，就直接入栈
    2. 有操作符，就进行比较
      1. 如果当前的操作符的优先级小于或者等于栈顶的操作符，就需要从数栈中pop出两个数，在从符号栈中pop出一个符号，进行运算，将得到结果入数栈，然后将当前的操作符入符号栈
      2. 如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈
  4. 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号
  5. 最后在数栈只有一个数字，就是表达式的结果

2、代码实现

package work.rexhao.stack;

import java.util.Scanner;

/**
 * 个位数四则计算器
 *
 */
public class calculatorDemo {
   
    public static void main(String[] args) {
   
        System.out.println("请输入表达式");
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        sc.close();
        System.out.println("表达式值为:" + calculator.calculate(s));
    }

}

class calculator {
   

    /**
     * 计算
     * 
     * @param s 表达式
     * @return 结果
     */
    public static int calculate(String s) {
   
        /*
         * 初始化栈
         */
        numStact ns = new numStact(20); // 数栈
        signStact ss = new signStact(20); // 运算符栈

        /*
         * 扫描字符串
         */
        int slen = s.length();
        // int index = 0; // 扫描索引
        for (int i = 0; i < slen; i++) {
   
            char c = s.charAt(i);
            if (c == '*' || c == '/') {
   
                ss.push(c);
            } else if (c == '+' || c == '-') {
   
                while (true) {
   
                    // 栈空：入栈
                    if (ss.isEmpty()) {
   
                        break;
                    }
                    // 栈非空：比较
                    if (ss.top() == '+' || ss.top() == '-') {
   
                        // 同优先级
                        break;
                    } else {
   
                        // 大于优先级
                        // 1.取出两个数和运算符
                        int ans = count(ns.pop(), ns.pop(), ss.pop());
                        // 2.结果入栈
                        ns.push(ans);
                    }
                }
                ss.push(c);
            } else {
   
                ns.push(c - '0');
            }
        }
        while(ns.top != 0) {
   
            ns.push(count(ns.pop(), ns.pop(), ss.pop()));
        }
        return ns.pop();
    }

    /**
     * 辅助计算
     */
    private static int count(int a, int b, char c) {
   
        if (c == '+') {
   
            return a + b;
        } else if (c == '-') {
   
            return b - a;
        } else if (c == '*') {
   
            return a * b;
        } else if (c == '/') {
   
            return a / b;
        }
        throw new RuntimeException("NaN");
    }
}

/**
 * 数栈
 * 
 */
class numStact {
   
    int maxSize;
    int[] data;
    int top;

    /**
     * 栈的构造器
     * 
     * @param maxSize 栈的大小
     */
    numStact(int maxSize) {
   
        this.maxSize = maxSize;
        data = new int[maxSize];
        top = -1;
    }

    /**
     * 判空
     */
    public boolean isEmpty() {
   
        return top == -1;
    }

    /**
     * 判满
     */
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    /**
     * 弹出
     */
    public int pop() {
   
        if (isEmpty()) {
   
            System.out.println("栈空");
            return -1;
        }
        return data[top--];
    }

    /**
     * 压栈
     */
    public void push(int num) {
   
        if (isFull()) {
   
            System.out.println("栈满");
        } else {
   
            data[++top] = num;
        }
    }

    /**
     * 遍历
     */
    public void list() {
   
        if (isEmpty()) {
   
            System.out.println("栈空");
            return;
        }
        for (int i = 0; i <= top; i++) {
   
            System.out.printf("data[%d] = %d\n", i, data[i]);
        }
    }
}

/**
 * 符号栈
 *
 */
class signStact {
   
    int maxSize;
    char[] data;
    int top;

    /**
     * 栈的构造器
     * 
     * @param maxSize 栈的大小
     */
    signStact(int maxSize) {
   
        this.maxSize = maxSize;
        data = new char[maxSize];
        top = -1;
    }

    /**
     * 判空
     */
    public boolean isEmpty() {
   
        return top == -1;
    }

    /**
     * 判满
     */
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    /**
     * 弹出
     */
    public char pop() {
   
        if (isEmpty()) {
   
            throw new RuntimeException("栈空");
        }
        return data[top--];
    }

    /**
     * 压栈
     */
    public void push(char c) {
   
        if (isFull()) {
   
            System.out.println("栈满");
        } else {
   
            data[++top] = c;
        }
    }

    /**
     * 遍历
     */
    public void list() {
   
        if (isEmpty()) {
   
            System.out.println("栈空");
            return;
        }
        for (int i = 0; i <= top; i++) {
   
            System.out.printf("data[%d] = %s\n", i, data[i]);
        }
    }

    /**
     * 栈顶元素
     */
    public char top() {
   
        return data[top];
    }
}

三、逆波兰计算器

package work.rexhao.stack;

public class polandNotationDemo {
   

    public static void main(String[] args) {
   
        System.out.println(polandNotation.calculate("34+5*6-"));
    }

}

class polandNotation {
   
    public static int calculate(String s) {
   
        numStact ns = new numStact(20);
        // 不需要符号栈
        int slen = s.length();
        for (int i = 0; i < slen; i++) {
   
            char c = s.charAt(i);
            if (c == '*' || c == '/' || c == '+' || c == '-') {
   
                ns.push(count(ns.pop(), ns.pop(), c));
            } else {
   
                ns.push(c - '0');
            }
        }
        return ns.pop();
    }

    /**
     * 辅助计算
     */
    private static int count(int a, int b, char c) {
   
        if (c == '+') {
   
            return a + b;
        } else if (c == '-') {
   
            return b - a;
        } else if (c == '*') {
   
            return a * b;
        } else if (c == '/') {
   
            return a / b;
        }
        throw new RuntimeException("NaN");
    }
}

四、中缀转后缀

1、思路

后缀表达式适合计算式进行运算，但是却不太容易写出来，尤其是表达式很长的情况下

因此在开发中，我们常常需要将中缀表达式转成后缀表达式

  1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2;
  2. 从左至右扫描中缀表达式
  3. 遇到操作数时，将其压s2
  4. 遇到运算符时，比较其与 s1栈顶运算符的优先级
    1. 如果s1为空，或栈顶运算符为左括号(，压入s1
    2. 若该运算符优先级比栈顶运算符的高，压入s1
    3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到与与s1中新的栈顶运算符相比较
  5. 遇到括号
    1. 如果是左括号(，则直接压入s1
    2. 如果是右括号)，则依次弹出s1的运算符压s2，直到遇到左括号为止，将这一对括号丢弃
  6. 重复步骤直到表达式的最右边
  7. 将s1中剩余的运算符依次弹出并压入s2
  8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

2、代码实现

/**
 * 中缀转后缀
 * 
 * @param s 中缀表达式
 * @return 后缀表达式
 */
public static String toPoland(String s) {
   
    sStact s1 = new sStact(20);// 运算符栈
    sStact s2 = new sStact(20);// 中间结果栈
    int slen = s.length();
    for (int i = 0; i < slen; i++) {
   
        char c = s.charAt(i);
        if (s1.isEmpty() || c == '(') {
   
            s1.push(c);
        } else if (c == ')') {
   
            while (true) {
   
                char temp = s1.pop();
                if (temp == '(') {
   
                    break;
                }
                s2.push(temp);
            }
        } else if (c == '+' || c == '-') {
   
            while (true) {
   
                if (s1.isEmpty() || s1.top() == '(') {
   
                    s1.push(c);
                    break;
                }
                s2.push(s1.pop());
            }
        } else if (c == '*' || c == '/') {
   
            while (true) {
   
                if (s1.isEmpty() || s1.top() == '+' || s1.top() == '-' || s1.top() == '(') {
   
                    s1.push(c);
                    break;
                }
                s2.push(s1.pop());
            }
        } else {
   
            // 数字
            s2.push(c);
        }
    }
    while (!s1.isEmpty()) {
   
        s2.push(s1.pop());
    }
    StringBuilder sb = new StringBuilder();
    while (!s2.isEmpty()) {
   
        sb.append(s2.pop());
    }
    return sb.reverse().toString();
}
文章标签：
索引
关键词：
数据结构应用
数据结构栈
数据结构栈应用
数据结构结构
数据结构栈结构
wmh1024
目录
相关文章
蓝易云
|
26天前
|
消息中间件 缓存 NoSQL
Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
这只是利用Go语言和Gin框架与Redis交互最基础部分展示；根据具体业务需求可能需要更复杂查询、事务处理或订阅发布功能实现更多高级特性应用场景。
蓝易云
158 86
陌陌谣
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据，传统数据结构存在性能瓶颈。红黑树通过自平衡机制，确保查找、插入、删除操作的时间复杂度稳定在 O(log n)，适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现，并探讨其在企业监控系统中的实践价值，提升系统性能与稳定性。
陌陌谣
76 1
陌陌谣
|
3月前
|
存储 监控 算法
公司员工泄密防护体系中跳表数据结构及其 Go 语言算法的应用研究
在数字化办公中，企业面临员工泄密风险。本文探讨使用跳表（Skip List）数据结构优化泄密防护系统，提升敏感数据监测效率。跳表以其高效的动态数据处理能力，为企业信息安全管理提供了可靠技术支持。
陌陌谣
59 0
hahaha无
|
4月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因，涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问，修改了变量`i`的值，导致`for`循环条件始终为真，形成死循环。原因是VS2022栈区从低地址到高地址分配内存，`arr`数组与`i`相邻，`arr[15]`恰好覆盖`i`的地址。而在VS2019中，栈区先分配高地址再分配低地址，因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致，需避免数组越界以确保代码健壮性。
hahaha无
61 0
栈区的非法访问导致的死循环(x64)
游客beejssedmb2sq
|
4月前
232.用栈实现队列，225. 用队列实现栈
在232题中，通过两个栈（`stIn`和`stOut`）模拟队列的先入先出（FIFO）行为。`push`操作将元素压入`stIn`，`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列（`que`）模拟栈的后入先出（LIFO）特性。通过多次调整队列头部元素的位置，确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素，`empty`判断队列是否为空。 两题均仅使用基础数据结构操作，展示了栈与队列之间的转换逻辑。
游客beejssedmb2sq
72 0
RossyYan
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
336 77
蓝易云
|
8月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例，希望能帮助读者更好地理解和应用这些重要的数据结构。
蓝易云
169 11
羑悻的小杀马特
|
8月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法：用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下： 1. **用两个队列实现栈**： - 插入元素时，选择非空队列进行插入。 - 移除栈顶元素时，将非空队列中的元素依次转移到另一个队列，直到只剩下一个元素，然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**： - 插入元素时，选择非空栈进行插入。 - 移除队首元素时，将非空栈中的元素依次转移到另一个栈，再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
羑悻的小杀马特
110 14
RossyYan
|
9月前
|
C++
【C++数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】
【数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】（1）遇到左括号：进栈Push()（2）遇到右括号：若栈顶元素为左括号，则出栈Pop()；否则返回false。（3）当遍历表达式结束，且栈为空时，则返回true，否则返回false。本关任务：编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务，你需要掌握：栈对括号的处理。（1）遇到左括号：进栈Push()开始你的任务吧，祝你成功！测试输入：(()))
RossyYan
196 7
ephemerals__
|
11月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
885 9

热门文章

最新文章

  • 1
    软考中级软件设计师专项-数据结构与算法上篇
  • 2
    【Redis】常用数据结构之List篇：从常用命令到典型使用场景
  • 3
    Redis数据结构：别小看这5把“瑞士军刀”，用好了性能飙升！
  • 4
    Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
  • 5
    Redis基础命令与数据结构概览
  • 6
    【Redis】 常用数据结构之String篇：从SET/GET到INCR的超全教程
  • 7
    【📕分布式锁通关指南 12】源码剖析redisson如何利用Redis数据结构实现Semaphore和CountDownLatch
  • 8
    024 栈追踪
  • 9
    基本数据结构和算法回顾
  • 10
    【算法与数据结构】中缀表达式转为后缀表达式
  • 1
    Redis原理—1.Redis数据结构
    297
  • 2
    c语言及数据结构实现简单贪吃蛇小游戏
    205
  • 3
    ☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
    110
  • 4
    C 408—《数据结构》算法题基础篇—链表（下）
    203
  • 5
    C 408—《数据结构》算法题基础篇—链表（上）
    318
  • 6
    C 408—《数据结构》算法题基础篇—数组（通俗易懂）
    298
  • 7
    C 408—《数据结构》图、查找、排序专题考点（含解析）
    295
  • 8
    C 408—《数据结构》易错考点200题（含解析）
    520
  • 9
    数据结构（C语言）之对归并排序的介绍与理解
    121
  • 10
    Go语言中的map数据结构是如何实现的？
    238

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云免费云服务器:个人用户每月750小时免费