一卤档、隊列的鏈?zhǔn)綄崿F(xiàn)概述

隊列本身就是一種特殊的線性表捞高，所以跟線性表一樣，可以使用順序存儲和鏈?zhǔn)酱鎯煞N方式兆沙，順序存儲已經(jīng)在隊列之-循環(huán)隊列中講述了，本文就補充一下鏈?zhǔn)降膶崿F(xiàn)方式莉掂。

鏈?zhǔn)疥犃校涸鰟h的時間復(fù)雜度都是O(1)葛圃，并且基本可以說是無大小限制，但是就是需要額外的存儲空間來存儲每個結(jié)點的指針憎妙。

鏈?zhǔn)疥犃?png

默認(rèn)將front(隊頭指針)指向頭結(jié)點库正，頭結(jié)點本身不存儲值，只是為了方便刪除第一個結(jié)點時的通用操作厘唾。rear指針指向鏈?zhǔn)疥犃械淖詈笠粋€結(jié)點褥符，這樣就方便在隊尾添加結(jié)點。初始狀態(tài)（即空的鏈?zhǔn)疥犃校└Ю琭ront和rear都指向頭結(jié)點喷楣。

二、隊列的鏈?zhǔn)綄崿F(xiàn)-java

public class MyLinkedQueue<E> {
    /**
     * 使用鏈?zhǔn)酱鎯崿F(xiàn)隊列
     */

    /**
     * 鏈?zhǔn)疥犃谐Ｓ玫姆椒ㄈ缦拢?     * 1鹤树、InitLinkedQueue()    初始化一個鏈?zhǔn)疥犃?     * 2铣焊、ClearLinkedQueue()   清空一個鏈?zhǔn)疥犃?     * 3、LinkedQueueEmpty()    判斷鏈?zhǔn)疥犃惺欠駷榭?     * 4罕伯、GetHead()  獲取鏈?zhǔn)疥犃形膊拷Y(jié)點數(shù)據(jù)
     * 5曲伊、EnLinkedQueue()  在鏈?zhǔn)疥犃形膊坎迦胄陆Y(jié)點
     * 6、DeLinkedQueue()  刪除鏈?zhǔn)疥犃蓄^部結(jié)點
     * 7追他、LinkedQueueLength()  返回鏈?zhǔn)疥犃械拈L度
     */
    //定義結(jié)點
    class QueueNode{
        E elem;
        QueueNode next;
    }
    int maxLinkedQueueSize; //當(dāng)前鏈?zhǔn)疥犃械拇笮?    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){
            //說明是空的鏈?zhǔn)疥犃?            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) {
    }
}