JAVA双向队列实现(链表)-程序员宅基地

技术标签: JAVA  java  链表  双向队列  队列  

队列是很常见的一种数据存储结构,今天,介绍下如何用链表实现双向队列。

首先定义节点接口如下:

public interface Node<E> {
    
    //设置数据元素
    public void setData(E o);
    //获取节点元素
    public E getData();
}

根据需求不同,实现该接口,双向链表节点的实现如下:

public class DLNode<E> implements Node<E> {
    

    private E element;

    private DLNode<E> pre;

    //下一个节点
    private DLNode<E> next;

    //比较策略对象,用于比较两个对象是否相等,在查找,插值等情况下使用
    private Strategy strategy;

    //无参构造函数
    public DLNode() {
    
        this(new DefaultStrategy());
    }

    //有参构造函数
    public DLNode(Strategy strategy) {
    
        this.strategy = strategy;
        this.pre = null;
        this.next = null;
    }

    //赋值
    @Override
    public void setData(E o) {
    
        this.element = o;
    }

    //获取值
    @Override
    public E getData() {
    
        return this.element;
    }

    //比较元素是否相等
    public boolean equal(E o) {
    
        if (this.strategy.equals(o, this.element)) {
    
            return true;
        } else {
    
            return false;
        }
    }

    //设置节点前置节点
    public void setPre(DLNode<E> pre) {
    
        this.pre = pre;
    }

    //设置后续节点
    public void setNext(DLNode<E> next) {
    
        this.next = next;
    }

    //获取前置节点
    public DLNode<E> getPre() {
    
        return this.pre;
    }

    //获取后续节点
    public DLNode<E> getNext() {
    
        return this.next;
    }
}

代码应该没有比较难理解的地方,简单说明一下:双向链表节点DLNode几个属性含义分别为element是数据元素(存储节点数据),pre是前一个节点的引用,next是下一个节点的引用,Strategy是比较策略接口,用来比较两个数据元素是否相等,在后面的例子中会有使用,Strategy和DefaultStrategy代码。

//Strategy接口
public interface Strategy {
    
    //比较两个元素是否相等
    public boolean equals(Object obj1, Object obj2);
}

//DefaultStrategy实现类
public class DefaultStrategy implements Strategy {
    
    @Override
    public boolean equals(Object obj1, Object obj2) {
    
        if (null != obj1 && null != obj2) {
    
            return obj1.equals(obj2);
        }
        return false;
    }
}

接下来就是双向链表的实现了,链表的应该有一下几个功能,查询,删除,插入等等,代码如下:

public class DoubleLinkedList<E> {
    

    //双向链表头结点
    private DLNode<E> header;

    //双向链表尾节点
    private DLNode<E> tail;

    //比较策略对象,用于比较两个对象是否相等,在查找,插值等情况下使用
    private Strategy strategy;

    //链表大小
    private int size;

    public DoubleLinkedList() {
    
        this.size = 0;
        this.header = null;
        this.tail = null;
        this.strategy = null;
    }

    public DoubleLinkedList(Strategy strategy) {
    
        this.size = 0;
        this.header = null;
        this.tail = null;
        this.strategy = strategy;
    }

    //是否是空链表
    public boolean isEmpty() {
    
        return this.size == 0;
    }

    //获取链表大小
    public int getSize() {
    
        return this.size;
    }

    //链表尾加入链表
    public void push(E o) {
    
        DLNode<E> node = this.strategy != null ? new DLNode(this.strategy) : new DLNode();
        node.setData(o);
        if (this.size == 0) {
    
            this.header = node;
            this.tail = node;
            node.setPre(null);
        } else {
    
            node.setPre(this.tail);
            this.tail.setNext(node);
            this.tail = node;
        }
        node.setNext(null);
        this.size++;
    }

    //链表尾加入链表
    public void unshift(E o) {
    
        DLNode<E> node = this.strategy != null ? new DLNode( this.strategy) : new DLNode();
        node.setData(o);
        if (this.size == 0) {
    
            this.header = node;
            this.tail = node;
            node.setNext(null);
        } else {
    
            node.setNext(this.header);
            this.header.setPre(node);
            this.header = node;
        }
        node.setPre(null);
        this.size++;
    }

    //在特定值之前插入值
    public boolean insertBefore(E target, E src) {
    
        if (this.size == 0) {
    
            return false;
        } else {
    
            DLNode<E> headerP = this.header;
            while (headerP != null) {
    
                if (headerP.equal(target)) {
    
                    DLNode<E> node = this.strategy != null ? new DLNode( this.strategy) : new DLNode();
                    node.setData(src);
                    DLNode<E> preNode = headerP.getPre();
                    headerP.setPre(node);
                    node.setPre(preNode);
                    node.setNext(headerP);
                    this.size++;
                    return true;
                }
                headerP = headerP.getNext();
            }
            return false;
        }
    }

    //在特定值之前插入值
    public boolean insertAfter(E target, E src) {
    
        if (this.size == 0) {
    
            return false;
        } else {
    
            DLNode<E> headerP = this.header;
            while (headerP != null) {
    
                if (headerP.equal(target)) {
    
                    DLNode<E> node = this.strategy != null ? new DLNode(this.strategy) : new DLNode();
                    node.setData(src);
                    DLNode<E> nextNode = headerP.getNext();
                    headerP.setNext(node);
                    node.setPre(headerP);
                    node.setNext(nextNode);
                    this.size++;
                    return true;
                }
                headerP = headerP.getNext();
            }
            return false;
        }
    }

    //判断是否存在某个元素
    public boolean isExist(E o) {
    
        if (this.size == 0) {
    
            return false;
        } else {
    
            DLNode<E> headerP = this.header;
            while (headerP != null) {
    
                if (headerP.equal(o)) {
    
                    return true;
                }
                headerP = headerP.getNext();
            }
            return false;
        }
    }

    //判断元素在链表中的位置
    public int indexOf(E o) {
    
        if (this.size == 0) {
    
            return -1;
        } else {
    
            DLNode<E> headerP = this.header;
            int index = 0;
            while (headerP != null) {
    
                if (headerP.equal(o)) {
    
                    return index;
                }
                headerP = headerP.getNext();
                index++;
            }
            return -1;
        }
    }

    public boolean remove(E o) {
    
        if (this.size == 0) {
    
            return false;
        } else {
    
            DLNode<E> headerP = this.header;
            while (headerP != null) {
    
                if (headerP.equal(o)) {
    
                    DLNode<E> pre = headerP.getPre();
                    DLNode<E> next = headerP.getNext();
                    if (pre == null) {
    
                        this.header = next;
                    } else {
    
                        pre.setNext(next);
                    }
                    if (next == null) {
    
                        this.tail = pre;
                    } else {
    
                        next.setPre(pre);
                    }
                    this.size--;
                    return true;
                }
                headerP = headerP.getNext();
            }
            return false;
        }
    }

    //获取头节点
    public DLNode<E> getHeader() {
    
        return this.header;
    }

    //获取尾节点
    public DLNode<E> getTail() {
    
        return this.tail;
    }

    //返回队列尾节点,并将尾节点从链表中删除
    public E pop() {
    
        if (this.size == 0) {
    
            return null;
        } else {
    
            E result = this.tail.getData();
            if (this.tail.getPre() != null) {
    
                this.tail.getPre().setNext(null);
                this.tail = this.tail.getPre();
            } else {
    
                this.tail = null;
                this.header = null;
            }
            this.size--;
            return result;
        }
    }

    //返回队链表首节点数据,并将首节点从链表中删除
    public E shift() {
    
        if (this.size == 0) {
    
            return null;
        } else {
    
            E result = this.header.getData();
            if (this.header.getNext() != null) {
    
                this.header.getNext().setPre(null);
                this.header = this.header.getNext();
            } else {
    
                this.tail = null;
                this.header = null;
            }
            this.size--;
            return result;
        }
    }
}

每个方法属性的含义在代码中已经注释,没有特别需要讲解的地方,如有疑问,请给我留言。

下面测试一下链表功能:
有学生类(Student)如下:

package LinkedNode;

public class Student {
    

    private String name;

    private int age;

    private String stuId;

    public Student(String name, int age, String id) {
    
        this.name = name;
        this.age = age;
        this.stuId = id;
    }

    public String getName() {
    
        return name;
    }

    public void setName(String name) {
    
        this.name = name;
    }

    public int getAge() {
    
        return age;
    }

    public void setAge(int age) {
    
        this.age = age;
    }

    public String getStuId() {
    
        return stuId;
    }

    public void setStuId(String stuId) {
    
        this.stuId = stuId;
    }

    public String toString() {
    
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("姓名:");
        stringBuilder.append(this.name);
        stringBuilder.append(",年龄:");
        stringBuilder.append(this.age);
        stringBuilder.append(",学号:");
        stringBuilder.append(this.stuId);
        return stringBuilder.toString();
    }
}

学生类之间的比较策略实现如下:

public class StudentStrategy implements Strategy {
    

    @Override
    public boolean equals(Object obj1, Object obj2) {
    
        if (obj1 instanceof Student && obj2 instanceof Student) {
    
            Student student1 = (Student)obj1;
            Student student2 = (Student)obj2;
            return student1.getStuId().equals(student2.getStuId());
        } else {
    
            return false;
        }
    }

}

只要两个类的stuId是相等的,就认为类是相等的,可以理解为,每个学生都有一个学号,学号一致,则认为就是同一个人。
测试代码如下,输出在代码下面:

public class TestDLNode {
    
    public static void main(String [] args) {
    
        DoubleLinkedList<Student> doubleLinkedList = new DoubleLinkedList<>(new StudentStrategy());
        for (int i = 0; i < 5; i++){
    
            Student student = new Student("sutdenet" + i, 20, String.valueOf(i));
            doubleLinkedList.push(student);
        }
        DLNode<Student> header = doubleLinkedList.getHeader();
        Student student1 = new Student("", 0, "3");
        Student student2 = new Student("this is insert", 10, "10");
        doubleLinkedList.insertAfter(student1, student2);
        System.out.println(doubleLinkedList.getSize());
        while (header != null) {
    
            System.out.println(header.getData());
            header = header.getNext();
        }
        System.out.println(doubleLinkedList.indexOf(student1));
        System.out.println(doubleLinkedList.pop());
        System.out.println(doubleLinkedList.getSize());
    }
}
/*
输出如下:
6
姓名:sutdenet0,年龄:20,学号:0
姓名:sutdenet1,年龄:20,学号:1
姓名:sutdenet2,年龄:20,学号:2
姓名:sutdenet3,年龄:20,学号:3
姓名:this is insert,年龄:10,学号:10
姓名:sutdenet4,年龄:20,学号:4
3
姓名:sutdenet4,年龄:20,学号:4
5
*/

对比代码和输出,可看到双向队列的基本功能都已经实现。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u011350550/article/details/83210817

智能推荐

2022黑龙江最新建筑八大员(材料员)模拟考试试题及答案_料账的试题-程序员宅基地

文章浏览阅读529次。百分百题库提供建筑八大员(材料员)考试试题、建筑八大员(材料员)考试预测题、建筑八大员(材料员)考试真题、建筑八大员(材料员)证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。310项目经理部应编制机械设备使用计划并报()审批。A监理单位B企业C建设单位D租赁单位答案:B311对技术开发、新技术和新工艺应用等情况进行的分析和评价属于()。A人力资源管理考核B材料管理考核C机械设备管理考核D技术管理考核答案:D312建筑垃圾和渣土._料账的试题

chatgpt赋能python:Python自动打开浏览器的技巧-程序员宅基地

文章浏览阅读614次。本文由chatgpt生成,文章没有在chatgpt生成的基础上进行任何的修改。以上只是chatgpt能力的冰山一角。作为通用的Aigc大模型,只是展现它原本的实力。对于颠覆工作方式的ChatGPT,应该选择拥抱而不是抗拒,未来属于“会用”AI的人。AI职场汇报智能办公文案写作效率提升教程 专注于AI+职场+办公方向。下图是课程的整体大纲下图是AI职场汇报智能办公文案写作效率提升教程中用到的ai工具。_python自动打开浏览器

Linux中安装JDK-RPM_linux 安装jdk rpm-程序员宅基地

文章浏览阅读545次。Linux中安装JDK-RPM方式_linux 安装jdk rpm

net高校志愿者管理系统-73371,计算机毕业设计(上万套实战教程,赠送源码)-程序员宅基地

文章浏览阅读25次。免费领取项目源码,请关注赞收藏并私信博主,谢谢-高校志愿者管理系统主要功能模块包括页、个人资料(个人信息。修改密码)、公共管理(轮播图、系统公告)、用户管理(管理员、志愿用户)、信息管理(志愿资讯、资讯分类)、活动分类、志愿活动、报名信息、活动心得、留言反馈,采取面对对象的开发模式进行软件的开发和硬体的架设,能很好的满足实际使用的需求,完善了对应的软体架设以及程序编码的工作,采取SQL Server 作为后台数据的主要存储单元,采用Asp.Net技术进行业务系统的编码及其开发,实现了本系统的全部功能。

小米宣布用鸿蒙了吗,小米OV对于是否采用鸿蒙保持沉默,原因是中国制造需要它们...-程序员宅基地

文章浏览阅读122次。原标题:小米OV对于是否采用鸿蒙保持沉默,原因是中国制造需要它们目前华为已开始对鸿蒙系统大规模宣传,不过中国手机四强中的另外三家小米、OPPO、vivo对于是否采用鸿蒙系统保持沉默,甚至OPPO还因此而闹出了一些风波,对此柏铭科技认为这是因为中国制造当下需要小米OV几家继续将手机出口至海外市场。 2020年中国制造支持中国经济渡过了艰难的一年,这一年中国进出口贸易额保持稳步增长的势头,成为全球唯一..._小米宣布用鸿蒙系统

Kafka Eagle_kafka eagle git-程序员宅基地

文章浏览阅读1.3k次。1.Kafka Eagle实现kafka消息监控的代码细节是什么?2.Kafka owner的组成规则是什么?3.怎样使用SQL进行kafka数据预览?4.Kafka Eagle是否支持多集群监控?1.概述在《Kafka 消息监控 - Kafka Eagle》一文中,简单的介绍了 Kafka Eagle这款监控工具的作用,截图预览,以及使用详情。今天_kafka eagle git

随便推点

Eva.js是什么(互动小游戏开发)-程序员宅基地

文章浏览阅读1.1k次,点赞29次,收藏19次。Eva.js 是一个专注于开发互动游戏项目的前端游戏引擎。:Eva.js 提供开箱即用的游戏组件供开发人员立即使用。是的,它简单而优雅!:Eva.js 由高效的运行时和渲染管道 (Pixi.JS) 提供支持,这使得释放设备的全部潜力成为可能。:得益于 ECS(实体-组件-系统)架构,你可以通过高度可定制的 API 扩展您的需求。唯一的限制是你的想象力!_eva.js

OC学习笔记-Objective-C概述和特点_objective-c特点及应用领域-程序员宅基地

文章浏览阅读1k次。Objective-C概述Objective-C是一种面向对象的计算机语言,1980年代初布莱德.考斯特在其公司Stepstone发明Objective-C,该语言是基于SmallTalk-80。1988年NeXT公司发布了OC,他的开发环境和类库叫NEXTSTEP, 1994年NExt与Sun公司发布了标准的NEXTSTEP系统,取名openStep。1996_objective-c特点及应用领域

STM32学习笔记6:TIM基本介绍_stm32 tim寄存器详解-程序员宅基地

文章浏览阅读955次,点赞20次,收藏16次。TIM(Timer)定时器定时器可以对输入的时钟进行计数,并在计数值达到设定值时触发中断16位计数器、预分频器、自动重装寄存器的时基单元,在 72MHz 计数时钟下可以实现最大 59.65s 的定时,59.65s65536×65536×172MHz59.65s65536×65536×721​MHz不仅具备基本的定时中断功能,而且还包含内外时钟源选择、输入捕获、输出比较、编码器接口、主从触发模式等多种功能。_stm32 tim寄存器详解

前端基础语言HTML、CSS 和 JavaScript 学习指南_艾编程学习资料-程序员宅基地

文章浏览阅读1.5k次。对于任何有兴趣学习前端 Web 开发的人来说,了解 HTML、CSS 和JavaScript 之间的区别至关重要。这三种前端语言都是您访问过的每个网站的用户界面构建块。而且,虽然每种语言都有不同的功能重点,但它们都可以共同创建令人兴奋的交互式网站,让用户保持参与。因此,您会发现学习所有三种语言都很重要。如果您有兴趣从事前端开发工作,可以通过多种方式学习这些语言——在艾编程就可以参与到学习当中来。在本文中,我们将回顾每种语言的特征、它们如何协同工作以及您可以在哪里学习它们。HTML vs C._艾编程学习资料

三维重构(10):PCL点云配准_局部点云与全局点云配准-程序员宅基地

文章浏览阅读2.8k次。点云配准主要针对点云的:不完整、旋转错位、平移错位。因此要得到完整点云就需要对局部点云进行配准。为了得到被测物体的完整数据模型,需要确定一个合适的坐标系变换,将从各个视角得到的点集合并到一个统一的坐标系下形成一个完整的数据点云,然后就可以方便地进行可视化,这就是点云数据的配准。点云配准技术通过计算机技术和统计学规律,通过计算机计算两个点云之间的错位,也就是把在不同的坐标系下的得到的点云进行坐标变..._局部点云与全局点云配准

python零基础学习书-Python零基础到进阶必读的书藉:Python学习手册pdf免费下载-程序员宅基地

文章浏览阅读273次。提取码:0oorGoogle和YouTube由于Python的高可适应性、易于维护以及适合于快速开发而采用它。如果你想要编写高质量、高效的并且易于与其他语言和工具集成的代码,《Python学习手册:第4 版》将帮助你使用Python快速实现这一点,不管你是编程新手还是Python初学者。本书是易于掌握和自学的教程,根据作者Python专家Mark Lutz的著名培训课程编写而成。《Python学习..._零基础学pythonpdf电子书