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

2018-11-22 08:42:14来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

  在上一篇博客【教你如何使用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) + "}";
    }
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Redis

下一篇:Java马士兵高并发编程视频学习笔记(二)