一、队列的链式实现概述

队列本身就是一种特殊的线性表，所以跟线性表一样，可以使用顺序存储和链式存储两种方式，顺序存储已经在队列之-循环队列中讲述了，本文就补充一下链式的实现方式。

链式队列：增删的时间复杂度都是O(1)，并且基本可以说是无大小限制，但是就是需要额外的存储空间来存储每个结点的指针。

链式队列.png

默认将front(队头指针)指向头结点，头结点本身不存储值，只是为了方便删除第一个结点时的通用操作。rear指针指向链式队列的最后一个结点，这样就方便在队尾添加结点。初始状态（即空的链式队列），front和rear都指向头结点。

二、队列的链式实现-java

public class MyLinkedQueue<E> {
    /**
     * 使用链式存储实现队列
     */

    /**
     * 链式队列常用的方法如下：
     * 1、InitLinkedQueue()    初始化一个链式队列
     * 2、ClearLinkedQueue()   清空一个链式队列
     * 3、LinkedQueueEmpty()    判断链式队列是否为空
     * 4、GetHead()  获取链式队列尾部结点数据
     * 5、EnLinkedQueue()  在链式队列尾部插入新结点
     * 6、DeLinkedQueue()  删除链式队列头部结点
     * 7、LinkedQueueLength()  返回链式队列的长度
     */
    //定义结点
    class QueueNode{
        E elem;
        QueueNode next;
    }
    int maxLinkedQueueSize; //当前链式队列的大小
    QueueNode front;
    QueueNode rear;
    public MyLinkedQueue(){
        //初始化一个头结点
        this.front = new QueueNode();
        front.elem = (E)null;
        front.next = null;
        this.rear = front;
        this.maxLinkedQueueSize = 0;
    }
    public void ClearLinkedQueue(){
        if (this.maxLinkedQueueSize == 0){return;}
        while(this.maxLinkedQueueSize != 0){
            DeLinkedQueue();
        }
    }

    public Boolean LinkedQueueEmpty(){
        return this.maxLinkedQueueSize == 0 ? true : false;
    }

    public E GetHead(){
        if (this.maxLinkedQueueSize == 0){return null;}
        return front.next.elem;
    }

    public void EnLinkedQueue(E elem){
        QueueNode insertNode = new QueueNode();
        insertNode.elem = elem;
        insertNode.next = null;
        rear.next = insertNode;
        rear = rear.next;
        this.maxLinkedQueueSize++;
    }

    public E DeLinkedQueue(){
        if (this.maxLinkedQueueSize == 0){
            //说明是空的链式队列
            return null;
        }
        if (front.next == rear){
            //说明只有一个结点
            E returnElem = front.next.elem;
            rear = front;
            this.maxLinkedQueueSize = 0;
            return returnElem;
        }
        E returnElem = front.next.elem;
        QueueNode temp = front.next;
        front.next = front.next.next;
        temp.next = null;
        this.maxLinkedQueueSize--;
        return returnElem;
    }

    public int LinkedQueueLength(){
        return this.maxLinkedQueueSize;
    }

    public String toString(){
        if (front == rear){
            return null;
        }
        StringBuffer stringBuffer = new StringBuffer();
        QueueNode currNode = null;
        for (currNode = front.next;currNode != rear;currNode = currNode.next){
            stringBuffer.append(currNode.elem);
            stringBuffer.append(",");
        }
        stringBuffer.append(currNode.elem);
        return stringBuffer.toString();
    }
    
    public static void main(String[] args) {
    }
}