Java 数据结构篇-用链表、数组实现栈

🔥博客主页： 【小扳_-CSDN博客】
❤感谢大家点赞👍收藏⭐评论✍  

文章目录

        1.0 栈的说明

        2.0 用链表来实现栈

        2.1 实现栈 - 入栈方法（push）

        2.2 实现栈 - 出栈（pop）

        2.3 实现栈 - 查看栈顶元素（peek）

        2.4 实现栈 - 判断是否为空栈（isEmpty）

        2.5 实现栈 - 判断是否为满栈（isFull）

        2.6 实现栈 - 重写迭代器

        2.7 用链表实现栈的完整代码

        3.0 用数组来实现栈

        3.1 实现栈 - 入栈（push）

        3.2 实现栈 - 出栈（pop）

        3.3 实现栈 - 查找栈顶元素（peek）

        3.4 实现栈 - 判断是否为空栈（isEmpty）

        3.5 实现栈 - 判断是否为满栈（isFull）

        3.6 实现栈 - 重写迭代器

        3.7 用数组实现栈的完整代码

        1.0 栈的说明

        栈是一种数据结构，它具有后进先出（LIFO）的特性，即最后入栈的元素最先出栈。栈通常可以通过数组或链表来实现。栈有两个基本操作：入栈（push）和出栈（pop）。入栈操作将元素放入栈顶，出栈操作将栈顶元素移除并返回。栈还有一个辅助操作叫做查看栈顶元素（peek），用于查看栈顶的元素但不移除它。

        2.0 用链表来实现栈

        首先，需要准备实现带哨兵的单链表，用来存放数据。把链表的头部称为栈顶，链表的尾部称为栈底，对于栈来说，只对栈顶操作，对栈底不会有任何的操作。所以该链表中需要的成员变量有 sentry 哨兵节点、 size 记录节点的数量、capacity 栈的容量。为了更好的实现相关的API，所以另外定义了一个接口。

代码如下：


public class LinkedListStack<E> implements StackInterface<E>{

    static class Node<E> {
        public E value;
        Node<E> next;

        public Node() {
        }

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    private int size;
    private final int capacity;
    private final Node<E> sentry;

    public LinkedListStack(int capacity) {
        this.capacity = capacity;
        this.sentry = new Node<>(null,null);
    }

}

        

        2.1 实现栈 - 入栈方法（push）

        用链表实现栈中，入栈就相当于在链表中进行头插节点，需要注意的是，在进行入栈的时候需要先判断是否栈满了，若栈满了，返回 false；反则，返回 true 。

代码如下：

    public boolean push(E value) {

        if (isFull()) {
            System.out.println("栈容量满了！！！");
            return false;
        }
        sentry.next = new Node<>(value,sentry.next);
        size++;
        return true;
    }

        sentry.next 所指向的就是头节点，现在头节点要换成新入栈的节点，则就是 sentry.next 指向该节点，而新入栈的节点指向原来就旧的头节点。需要注意的是，记得进行 size++ 。

        2.2 实现栈 - 出栈（pop）

        用链表实现栈中，出栈相当于头删节点，不过结束的时候需要返回该节点的值，所以先找到头节点 head = sentry.next ，然后再让哨兵节点指向头节点的下一个节点，即可将该头节点从该链表中删除掉了，sentry.next = head.next 。最后返回 head.value 。

代码如下：

    public E pop() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = sentry.next;
        sentry.next = first.next;
        size--;
        return first.value;
    }

        在进行出栈操作时，需要先判断该链表是否为空，若是空链表，则返回 null ；若不是空链表，则返回该删除节点的值。还需要注意的是，每一次删除后，都需要进行 size-- 操作。

        2.3 实现栈 - 查看栈顶元素（peek）

        用链表实现栈中，查看栈顶元素相当与查找头节点，即 head =  sentry.next，因此直接返回该头节点的值即可 head.value 。

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = sentry.next;
        return first.value;
    }

        在查看栈顶元素时，也要先判断该栈是否为空栈。若为空栈，直接返回 null 。

        2.4 实现栈 - 判断是否为空栈（isEmpty）

        当且仅当 size == 0 时，则为空栈。还有一种判断的方式，就是当 sentry.next 时，也为空栈。

代码如下：

    public boolean isEmpty() {
        return size == 0;
        //return sentry.next == null;
    }

        2.5 实现栈 - 判断是否为满栈（isFull）

        用链表实现栈时，当 size == capacity 时，则为满栈。

代码如下：

    public boolean isFull() {
        return size == capacity;
    }

         2.6 实现栈 - 重写迭代器

        先实现该接口 Iterable<E> ，再重写该接口的两个方法，hasNext() 与 next() 。对于 hasNext() ，当 p != null 时，继续循环下去，p == null 时，循环结束；对于 next() ，需要进行 p = p.next，将 p 往后移一步的动作，还得需要完成每一次返回对应的数据的动作。 

代码如下：

    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = sentry.next;
            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public E next() {
                E key = p.value;
                p = p.next;
                return key;
            }
        };
    }

        2.7 用链表实现栈的完整代码

相关的接口：

public interface StackInterface <E>{

    /**
     * 先栈顶压入元素
     * value - 代压入值
     * 压入成功返回true,否则返回false
     */
    boolean push(E value);

    /**
     * 从栈顶弹出元素
     * 栈非空返回栈顶元素，栈为空返回 null
     */
    E pop();

    /**
     返回栈顶元素，不弹出
     栈非空返回栈顶元素，栈为空返回 null
     */
    E peek();

    /**
     * 判断栈是否为空
     * 空返回true，否则返回false
     */
    boolean isEmpty();

    /**
     * 判断栈是否满
     * 满返回true,否则返回false
     */
    boolean isFull();

}

用链表实现栈的代码：

import java.util.Iterator;
public class LinkedListStack<E> implements StackInterface<E>,Iterable<E>{

    static class Node<E> {
        public E value;
        Node<E> next;

        public Node() {
        }

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    private int size;
    private final int capacity;
    private final Node<E> sentry;

    public LinkedListStack(int capacity) {
        this.capacity = capacity;
        this.sentry = new Node<>(null,null);
    }


    @Override
    public boolean push(E value) {

        if (isFull()) {
            System.out.println("栈容量满了！！！");
            return false;
        }
        sentry.next = new Node<>(value,sentry.next);
        size++;
        return true;
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = sentry.next;
        sentry.next = first.next;
        size--;
        return first.value;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = sentry.next;
        return first.value;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
        //return sentry.next == null;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = sentry.next;
            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public E next() {
                E key = p.value;
                p = p.next;
                return key;
            }
        };
    }
}

        3.0 用数组来实现栈

        该类中的成员变量有 Object[] array 的数组，来存放数据；还有 int top ，用来记录数据的个数，当 top - 1 索引对应该位置，称为栈顶；0 索引对应的位置，称为栈底。这样的设置，提高了对栈顶操作的效率。

代码如下：

public class ArrayStack<E> {


    private int top;
    private Object[] arrayStack;

    public ArrayStack() {
    }

    public ArrayStack(int capacity) {
        arrayStack = new Object[capacity];
    }
}

        利用该类的构造方法，可以自定义初始化数组的容量。

        3.1 实现栈 - 入栈（push）

        用数组实现栈，相当与在数组 top 位置中存放数据，即 arrayStack[top] = value 。

代码如下：

 
    public boolean push(E value) {
        if (isFull()) {
            return false;
        }
        arrayStack[top++] = value;
        return true;
    }

        但是在入栈之前需要先判断该栈是否满了，若为满栈，则不能继续存放数据了。若存放数据之后，需要将 top++ 进行自加的操作。

        3.2 实现栈 - 出栈（pop）

        用数组实现栈，出栈相当于进行尾删，不过先得记录要删除的数据，将其返回即可。

代码如下：

    public E pop() {
        if (isEmpty()) {
            return null;
        }

        return (E)arrayStack[--top];
    }

        但是，在出栈之前需要先判断该栈是否为空栈。

         3.3 实现栈 - 查找栈顶元素（peek）

        用数组实现栈，查找栈顶元素相当于去查找数组 top - 1索引的值。

代码如下：

    public E peek() {
        if (top == 0) {
            return  null;
        }
        return (E) arrayStack[top - 1];
    }

        在查找栈顶元素之前，需要先判断 top 是否为 0 ，为 0 即为空，没有必要查找了。

        3.4 实现栈 - 判断是否为空栈（isEmpty）

        用数组实现栈，判断是否为空栈，就是判断 top 是否等于 0 。

代码如下：

    public boolean isEmpty() {
        return top == 0;
    }

        3.5 实现栈 - 判断是否为满栈（isFull）

        用数组实现栈，判断是否为满栈，就是判断 top 是否等于该数组的长度 arrayStack.length 。

代码如下：

    @Override
    public boolean isFull() {
        return arrayStack.length == top;
    }

        3.6 实现栈 - 重写迭代器

        先实现该接口 Iterable<E> ，再重写该接口的两个方法，hasNext() 和 next() 。对于 hasNext() ，当 top > 0 时，继续循环下去，top == 0 时，循环结束；对于 next() ，完成需要进行 top-- 的动作，还得需要完成每一次返回对应的数据的动作。 

代码如下：


    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = top;
            @Override
            public boolean hasNext() {
                return p > 0;
            }

            @Override
            public E next() {
                return (E)arrayStack[--p];
            }
        };
    }

        3.7 用数组实现栈的完整代码

接口代码：

public interface StackInterface <E>{

    /**
     * 先栈顶压入元素
     * value - 代压入值
     * 压入成功返回true,否则返回false
     */
    boolean push(E value);

    /**
     * 从栈顶弹出元素
     * 栈非空返回栈顶元素，栈为空返回 null
     */
    E pop();

    /**
     返回栈顶元素，不弹出
     栈非空返回栈顶元素，栈为空返回 null
     */
    E peek();

    /**
     * 判断栈是否为空
     * 空返回true，否则返回false
     */
    boolean isEmpty();

    /**
     * 判断栈是否满
     * 满返回true,否则返回false
     */
    boolean isFull();

}

用数组实现栈的代码：

import java.util.Iterator;

public class ArrayStack<E> implements StackInterface<E>,Iterable<E>{


    private int top;
    private Object[] arrayStack;

    public ArrayStack() {
    }

    public ArrayStack(int capacity) {
        arrayStack = new Object[capacity];
    }


    @Override
    public boolean push(E value) {
        if (isFull()) {
            return false;
        }
        arrayStack[top++] = value;

        return true;
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            return null;
        }

        return (E)arrayStack[--top];
    }

    @Override
    public E peek() {
        if (top == 0) {
            return  null;
        }
        return (E) arrayStack[top - 1];
    }

    @Override
    public boolean isEmpty() {
        return top == 0;
    }

    @Override
    public boolean isFull() {
        return arrayStack.length == top;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = top;
            @Override
            public boolean hasNext() {
                return p > 0;
            }

            @Override
            public E next() {
                return (E)arrayStack[--p];
            }
        };
    }
}

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/204320.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

[个人笔记] Zabbix实现Webhook推送markdown文本

[个人笔记] Zabbix实现Webhook推送markdown文本

系统工程 - 运维篇 第四章 Zabbix实现Webhook推送markdown文本 系统工程 - 运维篇系列文章回顾Zabbix实现Webhook推送markdown文本前言实施步骤 Zabbix新增报警媒介类型Zabbix给用户新增报警媒介Zabbix修改动作的执行操作和恢复操作验证&测试 参考来源 系列文章回顾 第一章…
阅读更多...
赤霞珠葡萄酒的风味特征是怎样的？

赤霞珠葡萄酒的风味特征是怎样的？

赤霞珠最值得注意的特点之一是它在发酵或桶陈酿期间对橡木的亲和力&#xff0c;除了对葡萄的天然高单宁产生软化效果外&#xff0c;香草和香料的独特木材风味还补充了黑醋栗和烟草的天然葡萄风味。 来自云仓酒庄品牌雷盛红酒分享基于赤霞珠的波尔多混合物在225升&#xff08;59…
阅读更多...
【vue_1】console.log没有反应

【vue_1】console.log没有反应

1、打印不出来&#xff1f;2、警告也会出现问题3、插播&#xff1a;如何使用if-else 语句来处理逻辑 1、打印不出来&#xff1f; 要做一个权限不够的弹出消息框 const authority_message () > {ElMessage({type: warrnings,message: 当前用户的权限不够});console.log(he…
阅读更多...
neo4j使用之超神之旅

neo4j使用之超神之旅

1.查询整个链路中任意一段的关系类型是“department”的链路数据 MATCH path (n)-[r1 *0..7 {relation_type:once2once}]-(m) where id(n)0 and any(x in relationships(path) where type(x)department) return path效果图&#xff1a; 2.查询整个链路中最后一段的关系类型…
阅读更多...
ROS报错：RLException:Invalid roslaunch XML Syntax: mismatched tag:

ROS报错：RLException:Invalid roslaunch XML Syntax: mismatched tag:

运行roslaunch文件提示&#xff1a; RLException:Invalid roslaunch XML Syntax: mismatched tag: line 45&#xff0c; column 2 The traceback for the exception was written to the log file. j 解决办法&#xff1a; line45 行多了标签&#xff1a;</node> 另外…
阅读更多...
拓数派荣获上海市“智慧工匠”工业软件创新案例奖

拓数派荣获上海市“智慧工匠”工业软件创新案例奖

近日&#xff0c;由上海市经济和信息化委员会指导、上海市城市数字化转型应用促进中心主办、上海中创产业创新研究院承办的“工业软件赋能新型工业化”主题沙龙暨2023“智慧工匠”工业软件创新案例竞赛颁奖典礼在上海圆满落幕。拓数派凭借上汽集团工业数据管理服务平台案例成功…
阅读更多...
深度学习大数据物流平台 python 计算机竞赛

深度学习大数据物流平台 python 计算机竞赛

文章目录 0 前言1 课题背景2 物流大数据平台的架构与设计3 智能车货匹配推荐算法的实现**1\. 问题陈述****2\. 算法模型**3\. 模型构建总览 **4 司机标签体系的搭建及算法****1\. 冷启动**2\. LSTM多标签模型算法 5 货运价格预测6 总结7 部分核心代码8 最后 0 前言 &#x1f5…
阅读更多...
绝地求生PUBG提示msvcp140.dll缺失的5个解决方法，亲测有效

绝地求生PUBG提示msvcp140.dll缺失的5个解决方法，亲测有效

在玩《绝地求生》这款游戏时&#xff0c;我们可能会遇到各种各样的问题。其中之一就是“吃鸡提示msvcp140.dll缺失怎么办”。这个问题可能导致游戏无法正常启动运行&#xff0c;但是不用担心&#xff0c;下面我将为大家详细介绍如何解决这个问题。 msvcp140.dll文件的概述 msv…
阅读更多...
如何利用树莓派与Nginx结合内网穿透服务实现远程访问内部站点——“cpolar内网穿透”

如何利用树莓派与Nginx结合内网穿透服务实现远程访问内部站点——“cpolar内网穿透”

文章目录 1. Nginx安装2. 安装cpolar3.配置域名访问Nginx4. 固定域名访问5. 配置静态站点 安装 Nginx&#xff08;发音为“engine-x”&#xff09;可以将您的树莓派变成一个强大的 Web 服务器&#xff0c;可以用于托管网站或 Web 应用程序。相比其他 Web 服务器&#xff0c;Ngi…
阅读更多...
【产品功能】dolphinscheduler怎么修改，实现超时就结束掉当前工作流

【产品功能】dolphinscheduler怎么修改，实现超时就结束掉当前工作流

超时就结束工作流 代码 代码 MasterExecThread类 的 runProcess方法 里面有超时告警&#xff0c;原本里面只有超时告警的&#xff0c;这时候我只要加上海豚自己写好的结束任务的方法endProcess&#xff08;&#xff09;方法
阅读更多...
视频监控平台EasyCVR多场景应用，AI视频分析技术助力行业升级转型

视频监控平台EasyCVR多场景应用，AI视频分析技术助力行业升级转型

传统的视频监控系统建设&#xff0c;经常存在各方面的因素制约&#xff0c;造成管理机制不健全、统筹规划不到位、联网共享不规范&#xff0c;形成“信息孤岛”、“数据烟囱”。在监控系统的建设中缺乏统一规划&#xff0c;标准不统一、视频图像信息利用率低等问题日益突出。随…
阅读更多...
7款趣味性不错的前端特效动画及源码分享（附源码）

7款趣味性不错的前端特效动画及源码分享（附源码）

鼠标悬停切换表情动画特效 基于CSS的transform属性制作鼠标悬停切换表情动画特效&#xff0c;默认为笑脸表情&#xff0c;鼠标悬停上去切换爱心眼睛色眯眯的表情。 预览获取 核心代码 <!DOCTYPE html> <html lang"en"> <head><meta charset&…
阅读更多...
【C++】C++11

【C++】C++11

一、C11 简介 C11 - cppreference.com 在 2003 年 C 标准委员会曾经提交了一份技术勘误表&#xff08;简称TC1&#xff09;&#xff0c;使得 C03 这个名字已经取代了 C98 称为 C11 之前的最新 C 标准名称。不过由于 C03&#xff08;TC1&#xff09;主要是对 C98 标准中的漏洞进…
阅读更多...
智能遥测终端机RTU的注意事项

智能遥测终端机RTU的注意事项

智能遥测终端机RTU是一种用于实时监测和控制现场数据的设备&#xff0c;可以广泛应用于水利、水文、电力、煤炭等各个领域。但是在使用智能遥测终端机RTU时&#xff0c;也需要注意一些事项&#xff0c;以确保终端的正常使用效果。 ◆注意安装位置 　　应安装在稳定、通风的室内…
阅读更多...
虚幻学习笔记4—文本内容处理

虚幻学习笔记4—文本内容处理

一、前言 本文使用的虚幻引擎5.3.2&#xff0c;在虚幻中已经集成了很多可以直接处理多样化文本的蓝图&#xff0c;比如格式化动态显示、浮点数多样化等。 二、实现 2.1、格式化文本显示动态内容&#xff1a;在设置某个文本时可以使用“Format Text”蓝图设置自定义可以的显示…
阅读更多...
企业怎么在社交媒体进行软文推广？媒介盒子为你支招

企业怎么在社交媒体进行软文推广？媒介盒子为你支招

数字化时代下&#xff0c;社交媒体已经成为企业进行营销推广的重要渠道&#xff0c;在社交媒体进行软文推广&#xff0c;能够提高企业的知名度与曝光度&#xff0c;还能更好地吸引用户关注&#xff0c;从而实现推广目标。但是想要在社交媒体上进行宣传&#xff0c;软文内容是十…
阅读更多...
智能工厂是什么？

智能工厂是什么？

今天就聊聊企业智能工厂的打造&#xff0c;企业想实现数字化转型建立智能工厂&#xff0c;就需要先建设数字化车间&#xff0c;可以说数字化车间是建设智能工厂的重要一环&#xff0c;智能工厂的基础是数字化车间。数字化车间可以实现企业生产过程中车间计划调度、工艺执行管理…
阅读更多...
zookeeper 单机伪集群搭建简单记录（实操课程系列）

zookeeper 单机伪集群搭建简单记录（实操课程系列）

本系列是zookeeper相关的实操课程&#xff0c;课程测试环环相扣&#xff0c;请按照顺序阅读测试来学习zookeeper 1、官方下载加压后&#xff0c;根目录下新建data和log目录&#xff0c;然后分别拷贝两份&#xff0c;分别放到D盘&#xff0c;E盘&#xff0c;F盘 2、data目录下面…
阅读更多...
分类模型的评价指标

分类模型的评价指标

分类模型有时候光靠loss和acc的指标太过于片面&#xff0c;不能很好全面的评判训练出来的模型。所以还需要分类报告、混淆矩阵、ROC曲线&#xff08;AUC的值&#xff09;等几个指标进行评判&#xff0c;本文主要用代码简洁的介绍如何得出这些指标。 首先要得到每个数据的真实值…
阅读更多...
百度推送收录工具-免费的各大搜索引擎推送工具

百度推送收录工具-免费的各大搜索引擎推送工具

在互联网时代&#xff0c;网站收录是网站建设的重要一环。百度推送工具作为一种提高网站收录速度的方式备受关注。在这个信息爆炸的时代&#xff0c;对于网站管理员和站长们来说&#xff0c;了解并使用一些百度推送工具是非常重要的。本文将重点分享百度批量域名推送工具和百度…
阅读更多...
最新文章

Copyright @ 2022~2023