Java数据结构与算法——栈

简介: Java数据结构与算法——栈

1.简介


1.    栈的英文为(stack)

2.    栈是一个先入后出(FILO-First In Last Out)的有序列表。

3.    (stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端,为变化的一端,称为栈顶(Top),另一端为固定的一端,称为栈底(Bottom)

4.    根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除。

那么栈主要的操作就是入栈和出栈了。



那么关于栈的应用场景,其实还是有很多的:

·       子程序的调用:在跳往子程序前,会先将下个指令的地址存到堆栈中,直到子程序执行完后再将地址取出,以回到原来的程序中。    

·       处理递归调用:和子程序的调用类似,只是除了储存下一个指令的地址外,也将参数、区域变量等数据存入堆栈中。

·       表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)

·       二叉树的遍历。

·       图形的深度优先(depthfirst)搜索法。

2.代码案例


下面的代码就是使用数组简单的模拟栈的相关操作。

package com.szh.stack;
import java.util.Scanner;
/**
 *
 */
class ArrayStack {
    private int maxSize;  //栈的大小
    private int[] stack;  //数组模拟栈
    private int top = -1; //栈顶指针
    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }
    //栈满
    public boolean isFull() {
        return top == maxSize - 1;
    }
    //栈空
    public boolean isEmpty() {
        return top == -1;
    }
    //入栈
    public void push(int value) {
        //先判断栈是否已满
        if (isFull()) {
            System.out.println("栈满,无法继续入栈。");
            return;
        }
        top++;
        stack[top] = value;
    }
    //出栈
    public int pop() {
        //先判断栈是否为空
        if (isEmpty()) {
            throw new RuntimeException("栈空,没有元素可以出栈。");
        }
        int value = stack[top];
        top--;
        return value;
    }
    //遍历栈中所有元素
    public void list() {
        //先判断栈是否为空
        if (isEmpty()) {
            System.out.println("栈空,没有数据~~");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d] = %d\n", i, stack[i]);
        }
    }
}
public class ArrayStackDemo {
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(4);
        String key = "";
        boolean loop = true;
        Scanner scanner = new Scanner(System.in);
        while (loop) {
            System.out.println("show: 表示显示栈");
            System.out.println("exit: 退出程序");
            System.out.println("push: 表示添加数据到栈(入栈)");
            System.out.println("pop: 表示从栈取出数据(出栈)");
            System.out.println("请输入你的选择: ");
            key = scanner.next();
            switch (key) {
                case "show":
                    stack.list();
                    break;
                case "push":
                    System.out.println("请输入一个数: ");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case "pop":
                    int res = stack.pop();
                    System.out.printf("出栈的数据是 %d\n", res);
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出~~~");
    }
}


3.栈实现简单的计算器


package com.szh.stack;
/**
 *
 */
class ArrayStack2 {
    private int maxSize;  //栈的大小
    private int[] stack;  //数组模拟栈
    private int top = -1; //栈顶指针
    public ArrayStack2(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }
    //栈满
    public boolean isFull() {
        return top == maxSize - 1;
    }
    //栈空
    public boolean isEmpty() {
        return top == -1;
    }
    //入栈
    public void push(int value) {
        //先判断栈是否已满
        if (isFull()) {
            System.out.println("栈满,无法继续入栈。");
            return;
        }
        top++;
        stack[top] = value;
    }
    //出栈
    public int pop() {
        //先判断栈是否为空
        if (isEmpty()) {
            throw new RuntimeException("栈空,没有元素可以出栈。");
        }
        int value = stack[top];
        top--;
        return value;
    }
    //遍历栈中所有元素
    public void list() {
        //先判断栈是否为空
        if (isEmpty()) {
            System.out.println("栈空,没有数据~~");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d] = %d\n", i, stack[i]);
        }
    }
    //增加一个方法,可以返回当前栈顶的值, 但是不是真正的pop
    public int peek() {
        return stack[top];
    }
    //返回运算符的优先级,int数字表示,数字越大优先级越高
    public int priority(int oper) {
        if(oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1; //假定目前的表达式只有 +, -, *, /
        }
    }
    //判断是不是一个运算符
    public boolean isOper(char val) {
        return val == '+' || val == '-' || val == '*' || val == '/';
    }
    //计算方法
    public int cal(int num1, int num2, int oper) {
        int res = 0; //res用于存放计算的结果
        switch (oper) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1; //注意顺序
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                break;
        }
        return res;
    }
}
public class Calculator {
    public static void main(String[] args) {
        String expression = "7*2*2-5+1-5+3-4"; //15
        //创建两个栈,一个数字栈,一个符号栈
        ArrayStack2 numStack = new ArrayStack2(10);
        ArrayStack2 operStack = new ArrayStack2(10);
        //定义需要的相关变量
        int index = 0; //用于扫描
        int num1 = 0;  //操作数1
        int num2 = 0;  //操作数2
        int oper = 0;  //符号
        int res = 0;   //计算结果
        char ch = ' '; //每次扫描得到的字符
        String keepNum = ""; //用于拼接多位数
        //循环扫描计算的表达式expression
        while (true) {
            //依次得到expression 的每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            //判断ch是不是符号
            if (operStack.isOper(ch)) { //如果是运算符
                //再判断当前符号栈是否为空
                if (!operStack.isEmpty()) { //不为空
                    //如果符号栈有操作符,就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数
                    //再从符号栈中pop出一个符号,进行运算,将得到的运算结果再次压入数栈,然后将当前的操作符入符号栈
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = operStack.cal(num1, num2, oper);
                        //将计算结果再次压入数字栈
                        numStack.push(res);
                        //将当前操作符压入符号栈
                        operStack.push(ch);
                    } else { //如果当前的操作符的优先级大于栈中的操作符, 就直接入符号栈.
                        operStack.push(ch);
                    }
                } else { //如果符号栈为空,则直接入栈
                    operStack.push(ch);
                }
            } else { //如果是数,则直接入数栈
                /**
                 * 1. 当处理多位数时,不能发现是一个数就立即入栈,因为他可能是多位数
                 * 2. 在处理数,需要向expression的表达式的index后再看一位,如果是数就进行扫描,如果是符号才入栈
                 * 3. 因此我们需要定义一个变量 字符串,用于拼接
                 */
                keepNum += ch;
                //如果ch已经是expression的最后一位,就直接入栈
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {
                    //判断下一个字符是不是数字,如果是数字,就继续扫描,如果是运算符,则入栈
                    //注意是看后一位,不是index++
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                        //如果后一位是运算符,则入栈 keepNum = "1" 或者 "123"
                        numStack.push(Integer.parseInt(keepNum));
                        //重要的!!!!!!, keepNum清空
                        keepNum = "";
                    }
                }
            }
            index++;
            if (index >= expression.length()) {
                break;
            }
        }
        //当表达式扫描完毕,就顺序的从数字栈和符号栈中pop出相应的数和符号,并运行
        while (true) {
            //如果符号栈为空,则计算到最后的结果, 数字栈中只有一个数字【结果】
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1, num2, oper);
            numStack.push(res);
        }
        //将数栈的最后数,pop出,就是结果
        int ans = numStack.pop();
        System.out.printf("表达式 %s = %d", expression, ans);
    }
}

相关文章
|
4天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
13天前
|
存储 算法 Java
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
|
26天前
|
存储 人工智能 算法
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
|
27天前
|
算法 安全 Java
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
68 16
|
30天前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
50 5
|
30天前
|
算法 搜索推荐 Java
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
62 6
|
1月前
|
存储 监控 算法
剖析基于Java算法驱动的智能局域网管控之道
本文探讨了基于Java语言的局域网控制方案,结合链表数据结构与令牌桶算法,解决设备管理和流量调度难题。通过链表灵活存储网络设备信息,实现高效设备管理;令牌桶算法则精准控制流量,确保网络平稳运行。二者相辅相成,为校园、企业等局域网提供稳固高效的控制体系,保障业务连续性和数据安全。
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】

热门文章

最新文章