当前位置:  首页  >  PHP资讯  >  业界资讯

java链表应用--基于链表实现队列详解(尾指针操作)

这篇文章主要介绍了java链表应用--基于链表实现队列,结合实例形式分析了java基于链表实现队列尾指针相关操作使用技巧,需要的朋友可以参考下

本文实例讲述了java基于链表实现队列。分享给大家供大家参考,具体如下:

在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加、删除、查找操作,时间复杂度均为O(1)。

一、链表改进分析

对于队列这种数据结构,需要在线性结构的一端插入元素,另外一端删除元素。因此此时基于链表来实现队列,则有一端的时间复杂度为O(n)。因此我们不能使用之前已经实现的链表结构,我们需要改进我们的链表。思路如下:

1.参考在链表头部删除、增加元素的时间复杂度为O(1)的思路,我们在链表的尾部设立一个Node型的变量tail来记录链表的尾部在哪,此时再head端和tail端添加元素都是及其简单的,在head端删除元素也是及其简单的,但对于在tail端删除元素时,是无法在时间复杂度为O(1)的情况进行的,也就是从tail端删除元素时不容易的。

2.只在头部head删除元素(队首),在尾部tail端添加元素(队尾)。

3.由于在基于链表实现队列时不涉及到操作链表中间元素,此时我们改进的链表中,不在使用虚拟头节,因此也就可能造成在没有虚拟头节点的情况下,链表为空。

二、链表改进代码

前言,在写本小节之前,我们已经实现了一个基于静态数组的队列,转到查看。此处我们实现基于链表的队列。

在实现基于静态数组的队列的时候,我们已经新建了一个package,此时我们在该package下新建一个LinkedListQueue类,用来实现Queue接口,目录结构为:

1.Queue接口代码

 package Queue; public interface Queue { //获取队列中元素个数 int getSize(); //队列中元素是否为空 boolean isEmpty(); //入队列 void enqueue(E e); //出队列 public E dequeue(); //获取队首元素 public E getFront(); }

2.LinkedListQueue类

 package Queue; public class LinkedListQueue implements Queue { //将Node节点设计成私有的类中类 private class Node { public E e; public Node next; //两个参数的构造函数 public Node(E e, Node next) { this.e = e; this.next = next; } //一个参数的构造函数 public Node(E e) { this.e = e; this.next = null; } //无参构造函数 public Node() { this(null, null); } @Override public String toString() { return e.toString(); } } private Node head, tail; private int size; //显示初始化 public LinkedListQueue() { head = null; tail = null; size = 0; } //获取队列中节点个数 @Override public int getSize() { return size; } //队列中是否为空 @Override public boolean isEmpty() { return size == 0; } //链表尾部进队操作 @Override public void enqueue(E e) { if (tail == null) { tail = new Node(e); head = tail; } else { tail.next = new Node(e); tail = tail.next; } size++; } //链表头部出队操作 @Override public E dequeue() { if (isEmpty()) { throw new IllegalArgumentException("链表为空"); } Node retNode = head; head = head.next; retNode.next = null; if (head == null) {//当链表只有一个元素时 tail = null; } size--; return retNode.e; } //获取队首元素 @Override public E getFront() { if (isEmpty()) { throw new IllegalArgumentException("链表为空"); } return head.e; } //为了便于测试,重写object类toString()方法 @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Queue: front "); Node cur = head; while (cur != null) { res.append(cur + "->"); cur = cur.next; } res.append("NULL tail"); return res.toString(); } }

3.为了便于测试,在LinkedListQueue类中添加一个main函数

 //测试用例 public static void main(String[] args) { LinkedListQueue queue = new LinkedListQueue(); for (int i = 0; i <10; i++) { queue.enqueue(i); System.out.println(queue); if (i % 3 == 2) {//每添加3个元素出队列一个 queue.dequeue(); System.out.println(queue); } } }

4.结果为

结果分析:每进队3个元素出队列一个。

关于本小节,若您觉得还行、还过得去,记得给个推荐哦~,谢谢!!

本节源码 https://github.com/FelixBin/dataStructure/blob/master/src/Queue/LinkedListQueue.java

更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

内容推荐:免费高清PNG素材下载
吐了个 "CAO" !
扫码关注 PHP1 官方微信号
PHP1.CN | 中国最专业的PHP中文社区 | PNG素材下载 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved PHP1.CN 第一PHP社区 版权所有 京ICP备19059560号-4