数据结构-栈(Java实现)

本文主要是介绍数据结构-栈(Java实现)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

栈

1.利用数组实现栈

package stack;

/*
    @CreateTime 2021/9/9 12:43
    @CreateBy cfk
    通过数组实现
*/

import java.util.Scanner;

public class ArrayStackDemo {
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(4);
        boolean flag = true;
        Scanner scanner = new Scanner(System.in);

        while (flag) {
            System.out.println("请输入你要选择的功能是?");
            System.out.println("show.显示栈中所有的数据");
            System.out.println("push.进栈");
            System.out.println("pop.出栈");
            System.out.println("exit.退出");
            String next = scanner.next();
            switch (next){
                case "show":
                    try {
                        stack.showStack();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "push":
                    try {
                        System.out.println("请输入要进栈的元素");
                        int i = scanner.nextInt();
                        stack.pushStack(i);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "pop":
                    try {
                        int i = stack.popStack();
                        System.out.println("出栈的元素为"+i);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    flag = false;

            }

        }
    }
}



class ArrayStack{

    public int top = -1;//栈顶

    public int[] stack;//创建数组代替栈

    public int maxSize;//栈的最大长度

    public ArrayStack(int maxSize){
        this.maxSize = maxSize;
        stack = new int[maxSize];//初始化数组
    }

    //判断栈满
    public boolean overStack(){
        return top == maxSize-1;
    }

    //判断栈内是否有元素
    public boolean emptyStack(){
        return top == -1;
    }

    //出栈
    public int popStack(){
        if (emptyStack()){
            throw new RuntimeException("栈为空!!");
        }
        int value = stack[top];
        top--;
        return value;
    }


    //进栈
    public void pushStack(int value){
        if (overStack()){
            throw new RuntimeException("栈已满,无法进行添加数据!!");
        }
        top++;
        stack[top] = value;

    }

    //显示栈
    public void showStack(){
        if (emptyStack()) {
            throw new RuntimeException("栈中没有数据!!");
        }

        for (int i = top; i >= 0; i--) {
            System.out.printf("栈中元素为arr[%d]为%s\n",i,stack[i]);
        }
    }


}

2.利用链表实现栈

package stack;

/*
    @CreateTime 2021/9/9 12:43
    @CreateBy cfk
    通过双向链表实现 非常简单
*/



import java.util.Scanner;

public class LinkedListStackDemo {
    public static void main(String[] args) {
        LinkedListStack stack = new LinkedListStack(4);
        boolean flag = true;
        Scanner scanner = new Scanner(System.in);

        while (flag) {
            System.out.println("请输入你要选择的功能是?");
            System.out.println("show.显示栈中所有的数据");
            System.out.println("push.进栈");
            System.out.println("pop.出栈");
            System.out.println("exit.退出");
            String next = scanner.next();
            switch (next){
                case "show":
                    try {
                        stack.showStack();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "push":
                    try {
                        System.out.println("请输入要进栈的元素");
                        int i = scanner.nextInt();
                        stack.pushStack(new Node(i));
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "pop":
                    try {
                        stack.popStack();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    flag = false;

            }

        }
    }
}


class LinkedListStack{

    public Node top = new Node(-1);//栈顶

    public int maxSize;//栈的最大长度z

    public LinkedListStack(int maxSize){
        this.maxSize = maxSize;

    }

    //判断栈满
    public boolean overStack(){
        return getLength(top) == maxSize;
    }

    //判断栈内是否有元素
    public boolean emptyStack(){
        return getLength(top) == 0;
    }

    //出栈
    public void popStack(){
        if (emptyStack()){
            throw new RuntimeException("栈为空!!");
        }

        Node tmp = top;

        while (tmp.next!=null){
            tmp = tmp.next;
        }

        tmp.pre.next = null;

    }


    //进栈
    public void pushStack(Node value){

        Node tmp = top;
        if (overStack()){
            throw new RuntimeException("栈已满,无法进行添加数据!!");
        }
        while (tmp.next != null) {
            tmp = tmp.next;
        }

        tmp.next = value;
        value.pre = tmp;


    }

    //显示栈
    public void showStack(){
        if (emptyStack()) {
            throw new RuntimeException("栈中没有数据!!");
        }
        //因为头节点是不能够改变的所以得创建一个临时存储
        Node tmp = top;

        while (true){
            if (tmp.next!=null){
                System.out.printf("栈中元素的id为%d\n", tmp.next.id);

                //这里一定要记得移动,这样才能够循环遍历所有的变量
                tmp = tmp.next;
            }else {
                break;
            }
        }

    }

    public int getLength(Node top){
        if (top.next==null)return 0;

        Node tmp = top.next;

        int i = 0;

        while (true) {
            if (tmp == null) {
                break;
            }else {
                //当tmp
                tmp = tmp.next;
                i++;
            }
        }
        return i;
    }


}


class Node{
    public int id;
    public Node next;
    public Node pre;

    public Node(int id){
        this.id = id;
    }
}

3.利用数组栈实现的计算器

package stack;

/*
    @CreateTime 2021/9/9 17:26
    @CreateBy cfk
    利用数组栈实现一个简单的计算器
*/


public class Calculator {

    public static void main(String[] args) {
        //开始考虑算法的实现
        //表达式
        String expression = "9999999+1*1-1+1*2*3/6";

        //创建两个栈一个用来存储数  一个用来存储符号
        ArrayStackCal numStack = new ArrayStackCal(10);
        ArrayStackCal operStack = new ArrayStackCal(10);

        //用来记录位置
        int index = 0;

        //操作数与运算符
        int num1;
        int num2;
        int oper;

        //结果
        int res;

        //用来保存从字符串中获取的字符
        char ch;

        //使用StringBuilder用来实现多多位的存储
        StringBuilder keepNum = new StringBuilder();

        do {
            //判断获取字符串中的第一个元素
            ch = expression.substring(index, index + 1).charAt(0);
            //如果第一个字符是符号的话
            if (operStack.isOper(ch)) {
                //如果符号栈直接不为空的话
                if (!operStack.emptyStack()) {
                    //如果当前符号栈中的运算符的优先级高于获取的运算符
                    if (operStack.useOrder(ch) <= operStack.useOrder(operStack.stack[operStack.top])) {
                        //进行一次运算 把数字栈的数据获取 以及获取符号栈的字符
                        num1 = numStack.popStack();
                        num2 = numStack.popStack();
                        oper = operStack.popStack();
                        res = numStack.cal(num1, num2, oper);
                        //这里最后记得把运算结果在放入数字栈中
                        numStack.pushStack(res);
                    }
                }
                //如果符号栈为空 或者 以及进行完了一次运算后 把获取的运算符加入到符号栈中
                operStack.pushStack(ch);
            } else {
                //让数字直接添加进数栈
                //如果直接传入字符的话 需要减去48 因为数字1对应的ASCII表为49
                //numStack.pushStack(ch - 48);

                //先把获取的字符添加到一个字符串中保存
                keepNum.append(ch);

                //如果当前已经是最后一个字符的话
                //直接把字符串转化入栈
                if (index == expression.length()-1){
                    numStack.pushStack(Integer.parseInt(keepNum.toString()));
                }else {
                    //如果下一位字符也是数字的话 不做任何处理 进行进行循环
                    //如果下一位字符是运算符的话,把数字入栈 并且把临时字符串置空
                    ch = expression.substring(index+1,index+2).charAt(0);
                    if (operStack.isOper(ch)){
                        numStack.pushStack(Integer.parseInt(keepNum.toString()));
                        keepNum.setLength(0);
                    }
                    // numStack.pushStack(Integer.parseInt(keepNum));
                    // keepNum = "";
                }

            }
            //每判断完一个字符 都依次自增 直到表达式的最后一位
            index++;
        } while (index < expression.length());

        //在进行完前面的运算后 如果运算符 还不为空 说明还有数据没进行运算
        //让剩下的数据进行运算
        while (!operStack.emptyStack()) {
            num1 = numStack.popStack();
            num2 = numStack.popStack();
            oper = operStack.popStack();
            res = numStack.cal(num1, num2, oper);
            numStack.pushStack(res);
        }

        //最后把数字栈中的最后一个数据出栈
        //此时这个数字就为最终结果
        res = numStack.popStack();
        System.out.printf("表达式%s,结果为%d",expression,res);

    }


}



class ArrayStackCal{

    public int top = -1;//栈顶

    public int[] stack;//创建数组代替栈

    public int maxSize;//栈的最大长度

    public ArrayStackCal(int maxSize){
        this.maxSize = maxSize;
        stack = new int[maxSize];//初始化数组
    }

    //判断栈满
    public boolean overStack(){
        return top == maxSize-1;
    }

    //判断栈内是否有元素
    public boolean emptyStack(){
        return top == -1;
    }

    //出栈
    public int popStack(){
        if (emptyStack()){
            throw new RuntimeException("栈为空!!");
        }
        int value = stack[top];
        top--;
        return value;
    }


    //进栈
    public void pushStack(int value){
        if (overStack()){
            throw new RuntimeException("栈已满,无法进行添加数据!!");
        }
        top++;
        stack[top] = value;

    }


    //编写运算符号的优先级
    public int useOrder(int oper){
        if (oper == '+' || oper == '-'){
            return 1;
        }
        if (oper == '*' || oper == '/'){
            return 2;
        }
        else {
            return 0;
        }
    }

    //判断输入的是不是符号
    public boolean isOper(char val){
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    //编写程序的运算方法
    //目前只考虑了加减乘除
    public int cal(int num1, int num2, int oper){
        int res = 0;
        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;

    }


}

这篇关于数据结构-栈(Java实现)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

数据结构-栈(Java实现)

栈

1.利用数组实现栈

2.利用链表实现栈

3.利用数组栈实现的计算器

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯