龙空技术网

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

字里藏宝 212

前言:

当前看官们对“java如何写一个队列”大约比较关注,我们都需要了解一些“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如何写一个队列