一、隊列的鏈式實現(xiàn)概述

隊列本身就是一種特殊的線性表，所以跟線性表一樣，可以使用順序存儲和鏈式存儲兩種方式，順序存儲已經(jīng)在隊列之-循環(huán)隊列中講述了，本文就補充一下鏈式的實現(xiàn)方式。

鏈式隊列：增刪的時間復雜度都是O(1)，并且基本可以說是無大小限制，但是就是需要額外的存儲空間來存儲每個結(jié)點的指針。

鏈式隊列.png

默認將front(隊頭指針)指向頭結(jié)點，頭結(jié)點本身不存儲值，只是為了方便刪除第一個結(jié)點時的通用操作。rear指針指向鏈式隊列的最后一個結(jié)點，這樣就方便在隊尾添加結(jié)點。初始狀態(tài)（即空的鏈式隊列），front和rear都指向頭結(jié)點。

二、隊列的鏈式實現(xiàn)-java

public class MyLinkedQueue<E> {
    /**
     * 使用鏈式存儲實現(xiàn)隊列
     */

    /**
     * 鏈式隊列常用的方法如下：
     * 1、InitLinkedQueue()    初始化一個鏈式隊列
     * 2、ClearLinkedQueue()   清空一個鏈式隊列
     * 3、LinkedQueueEmpty()    判斷鏈式隊列是否為空
     * 4、GetHead()  獲取鏈式隊列尾部結(jié)點數(shù)據(jù)
     * 5、EnLinkedQueue()  在鏈式隊列尾部插入新結(jié)點
     * 6、DeLinkedQueue()  刪除鏈式隊列頭部結(jié)點
     * 7、LinkedQueueLength()  返回鏈式隊列的長度
     */
    //定義結(jié)點
    class QueueNode{
        E elem;
        QueueNode next;
    }
    int maxLinkedQueueSize; //當前鏈式隊列的大小
    QueueNode front;
    QueueNode rear;
    public MyLinkedQueue(){
        //初始化一個頭結(jié)點
        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){
            //說明只有一個結(jié)點
            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) {
    }
}