Java数据结构01——栈

一、栈

        1、栈的性质

                栈(stack)是限定仅在表尾进行插入或者删除的线性表。对于栈来说，表尾端称为栈顶（top），表头端称为栈低（bottom）。不含元素的空表称为空栈。因为栈限定在表尾进行插入或者删除，因此栈又被称为先进后出（后进先出）的线性表（简称LIFO结构）。

二、Java实现 

        1、功能分析

                对于一个栈首先是向数据结构中添加元素和删除元素因此需要push入栈 以及pop出栈。

同时也需要一个能够遍历栈的函数。

        2、代码实现

                （1）、初始化

public class Stack {    //使用arrayList来保存元素，并作为栈的数据结构    ArrayList array = new ArrayList();    //空参构造器    public Stack(){}}

分析：此处使用Java内置的ArrayList作为数据存储的结构，并存储整型数据。

                （2）、入栈

public void push(int data){        array.add(data);    }

分析：依据ArrayList的性质，可以直接调用其中的add方法进行入栈操作。

                 （3）、出栈

 public void pop(){        //判断栈是否为空        if(array.size() == 0){            System.out.println("栈为空");        }else {            System.out.println(array.get(array.size() - 1));            array.remove(array.size() - 1);        }    }

分析：在进行出栈操作时，需要先判断栈是否为空，当栈为空时需要捕获异常。当栈内有元素时将从ArrayList的尾部输出元素，通过该方法实现栈的先进后出性质

                （4）、遍历

 public void travel(){        for (int i = 0; i < array.size(); i++) {            System.out.println(array.get(i));        }    }

分析：此处即遍历ArrayList的方法。

三、栈的拓展

        1、简述

                上述栈的结构只能保存整型的数据，因此这种类型的数据结构普适性很差。因此我们需要创建一个能够保存任何结构的数据。在Java中即需要使栈能够保存对象。结合之前所说的泛型数组，我们将要对上述栈进行改造。关于泛型数组可以查看博客：

泛型数组：(96条消息) Java数组（2）_️771的博客-CSDN博客

        2、代码实现

                （1）、创建栈类

public Stack{}

分析：当我们需要创建一个泛型类的话只需要在类名后面声明其性质

                （2）、创建节点类

public Stack{        class node{        //数据        Object data;        //节点指向        Node  nextNode;        //节点有参构造器        public Node(E data){            //保存当前节点的数据            this.data = data;            //设置节点指向            this.nextNode = null;        }   }}

分析：此处在栈类中包含了一个节点类，该类用于存储当前节点的数据以及指向下一个节点。

                （3）、方法实现

                     入栈

public void push(E data){        //判断栈是否为空并执行相应操作        if (front == null) {            front = new Node<>(data);            front.nextNode = null;        }        //栈内有元素时相应操作        else {            Node temp = front;            front = new Node<>(data);            front.nextNode = temp;        }    }

分析：该方法需要从外界接受参数，根据定义栈的数据类型，传入值为泛型，之后需要判断栈是否为空。当栈为空时我们需要设置栈顶元素并设置指向下一个元素 为空。当栈内存在元素时，首先要创建一个临时变量用于保存传入值，并将栈尾元素的节点指向这个临时节点。  

              出栈

public void pop(){        //创建输出变量        E data = front.data;        //去除已经出栈的元素        front = front.nextNode;        System.out.println(data);    }

分析：先从栈尾获取元素，并将下一个对象的节点指向该对象。

（本章用最简单的数据结构实现栈，内容持续更新）

来源地址：https://blog.csdn.net/qq_64037280/article/details/128884264