如何手写一个Java基于链表的队列？

作者:课课家教育更新于： 2018-11-23 15:03:43

　　教你如何使用java手写一个基于链表的队列

　　这篇博客主要讲解的是如何使用单链表实现一个简单版的队列。单向链表队列是属于非循环队列，同时队列的长度是不受限制的，也就是说添加数据的速度比拉取数据的速度快时，队列的长度是无限增长的。单链队列其本质就是一个链表，只不过是在获取或添加数据的时候跟普通的链表有所区别，队列在获取数据的同时也将该节点删除，并且每次获取数据都是从表头获取，普通链表可以获取任意节点的数据;队列在增加数据时总是添加到链表的尾部，而普通的链表则是可以在链表的任意地方插入一个节点。

       下面就和课课家小编一起学习掌握用Java手写基本链表的队列吧！

　　一、队列数据结构

　　该队列的结构够多个节点构成，每个节点都有一个指向下一个节点的指针，使得所有的节点都能够相连，形成一个链表。

　　Java实现：

　　static class Node{

　　Object item;

　　Node next;

　　public Node(Object item, Node next) {

　　this.item = item;

　　this.next = next;

　　}

　　}

　　其实就创建一个静态内部类即可，类中item是用来存储数据的，next是指向下一个node节点，最后一个节点的next为空。

　　二、属性

　　head：链表表头，拉取或遍历数据都是从这里开始的。

　　tail：链表表尾，每次添加数据都添加到tail的后面，变成新的tail

　　size：队列长度

　　//表头

　　private Node head;

　　//表尾

　　private Node tail;

　　//队列长度

　　private int size;

　　三、添加数据

　　public void offer(Object item){

　　Node n = new Node(item,null);

　　if (tail == null){

　　head = tail = n;

　　}else {

　　tail.next = n;

　　tail = n;

　　}

　　size++;

　　}

　　用代码实现队列的添加操作看起是很简单的，无非就是将新节点添加到表尾，然后把新节点设置成新的表尾。

　　四、拉取数据

　　public Object poll(){

　　if (head == null) return null;

　　Node h = head;

　　//将拉取的节点的下一个节点变成新的表头

　　head = head.next;

　　//把旧的表头的下一个节点指向设置为null，让gc回收

　　h.next = null;

　　//队列为空

　　if (head == null)

　　tail = null;

　　size--;

　　return h.item;

　　}

　　五、查看数据

　　public Object peek(){

　　return head == null ? null : head.item;

　　}

　　查看数据看的是表头的数据，但是跟poll方法的区别是该方法不会删除表头的数据。

　　六、清空列表

　　public void clear(){

　　size = 0;

　　Node h = head;

　　while (h != null){

　　Node temp = h.next;

　　h.next = null;

　　h = temp;

　　}

　　head = tail = null;

　　}

　　七、基于数组的队列和链表的队列的区别

　　1、前者是有边界的循环队列，后者则是没有边界的非循环队列。

　　2、前者在添加数据时无需创建新对象，性能消耗相对较小，后者每次添加数据都需要创建新对象。

　　3、后者每个节点都维护了一个链，所以所需内存也相对较大。

　　4、如果添加速度大于拉取速度，前者在达到边界后可能会无法添加数据，后者则没有这个问题。

　　八、完整代码

　　/**

　　* 基于链表实现的队列

　　*/

　　public class LinkQueue {

　　//表头

　　private Node head;

　　//表尾

　　private Node tail;

　　//队列长度

　　private int size;

　　public LinkQueue(){}

　　public void offer(Object item){

　　Node n = new Node(item,null);

　　if (tail == null){

　　head = tail = n;

　　}else {

　　tail.next = n;

　　tail = n;

　　}

　　size++;

　　}

　　public Object poll(){

　　if (head == null) return null;

　　Node h = head;

　　//将拉取的节点的下一个节点变成新的表头

　　head = head.next;

　　//把旧的表头的下一个节点指向设置为null，让gc回收

　　h.next = null;

　　//队列为空

　　if (head == null)

　　tail = null;

　　size--;

　　return h.item;

　　}

　　public Object peek(){

　　return head == null ? null : head.item;

　　}

　　public void clear(){

　　size = 0;

　　Node h = head;

　　while (h != null){

　　Node temp = h.next;

　　h.next = null;

　　h = temp;

　　}

　　head = tail = null;

　　}

　　public int size(){return size;}

　　static class Node{

　　Object item;

　　Node next;

　　public Node(Object item, Node next) {

　　this.item = item;

　　this.next = next;

　　}

　　}

　　@Override

　　public String toString() {

　　if (size == 0) return "{}";

　　StringBuilder builder = new StringBuilder(size + 2);

　　Node h = head;

　　builder.append("{");

　　while (h != null){

　　builder.append(h.item);

　　builder.append(", ");

　　h = h.next;

　　}

　　return builder.substring(0,builder.length() -2) + "}";

　　}

　　}

      小编：更多相关内容请点击课课家提供的链接，也可以选择课课家教育，获得Java的专业知识点。