Java数据结构01——栈

Bertha 。 2024-03-27 13:21 26阅读 0赞

### 一、栈 ###

1、栈的性质

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

![422eacdcd8fb42edab09f4a1e309b051.jpeg][]

### 二、Java实现 ###

1、功能分析

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

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

2、代码实现

（1）、初始化

public class Stack {
        //使用arrayList来保存元素，并作为栈的数据结构
        ArrayList array = new ArrayList<Integer>();
        //空参构造器
        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博客][96_ Java_2_771_-CSDN]

2、代码实现

（1）、创建栈类

public Stack<E>{}

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

（2）、创建节点类

public Stack<E>{
        
        class Node<E>{
            //数据
            Object data;
            //节点指向
            Node <E> 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<E> temp = front;
                front = new Node<>(data);
                front.nextNode = temp;
            }
        }

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

出栈

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

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

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

[422eacdcd8fb42edab09f4a1e309b051.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/bda62543932046859d3fa6b39784087f.png
[96_ Java_2_771_-CSDN]: https://blog.csdn.net/qq_64037280/article/details/128362716?spm=1001.2014.3001.5502