隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。在隊列的形成過程中，可以利用線性鏈表的原理，來生成一個隊列，也就是所謂的隊列的鏈式實現。基于鏈表的隊列，要動態創建和刪除節點，效率較低，但是可以動態增長。

隊列采用的FIFO(first in first out)，新元素（等待進入隊列的元素）總是被插入到鏈表的尾部，而讀取的時候總是從鏈表的頭部開始讀取。每次讀取一個元素，釋放一個元素。所謂的動態創建，動態釋放。因而也不存在溢出等問題。由于鏈表由結構體間接而成，遍歷也方便。

維護一個指向隊首的front結點，一個指向隊尾的rear結點，和一個標識隊列大小的count變量：

private LinearNode front,rear;//指示隊首和隊尾

private int count;

構造函數：

public LinkedQueue()

    {

        front = null;

        rear = null;

        count = 0;

    }

在看代碼之前，先注意幾個非空判斷：

可以判斷隊列為空的條件：

head = null

tail = null

head = tail = null

入隊/出隊時需要的非空判斷：

enqueue（入隊）：若為空 tail = head = node

dequeue（出隊）

出隊前空：return null

出隊后空：tail = head = null

鏈式實現：

package Queue;

import Bag.LinearNode;

public class LinkedQueue implements QueueADT {

    private LinearNode front,rear;

    private int count;

    public static void main(String[] args) {

        LinkedQueue queue = new LinkedQueue();

        System.out.println("依次將0到9入隊，然后連續出隊5次");

        for(int i = 0;i < 10;i++)

            queue.enqueue(i);

        for(int i = 0;i < 5;i++)

            queue.dequeue();

        System.out.println("隊列的大小為： " + queue.size());

        System.out.println("隊列為空嗎？： " + queue.isEmpty());

        System.out.println("隊列的頭為： " + queue.first());

    }

    public LinkedQueue()

    {

        front = null;

        rear = null;

        count = 0;

    }

    public int size() {

        return count;

    }

    public boolean isEmpty() {

        return (size() == 0);

    }

    public void enqueue(Object element) {

        LinearNode node = new LinearNode(element);

        if(isEmpty())

            front = rear = node;

        else

        {

            rear.setNext(node);

            rear = node;

        }

        count++;

    }

    public Object dequeue() {

        if(isEmpty())

        {

            System.out.println("隊列中沒有元素");

            System.exit(1);

        }

        Object result = front.getElement();    

        front = front.getNext();

        count--;

        return result;    

    }

    public Object first() {

        return front.getElement();

    }

}

結果：

依次將0到9入隊，然后連續出隊5次

隊列的大小為： 5

隊列為空嗎？： false

隊列的頭為： 5

我們再來看個例子：

public class LinkedQueue<E> {

    class Node<E> {

        E item;

        Node<E> next;

        public Node(E e) {

            this.item = e;

        }

    }

    private Node head; // 隊首

    private Node tail; // 隊尾

    public LinkedQueue() {

     // 隊列為空時 head = tail = null

        head = tail = null;

    }

    public void enqueue(E e) {

        Node node = new Node(e);

        // 隊列為空

        if(tail == null) {

            head = tail = node;

        }else {

            tail.next = node;

            tail = node;

        }

    }

    public E dequeue() {

        // 出隊前為空

        if (head == null) {

            return null;

        }

        E item = (E)head.item;

        // 出隊后空

        if (head.next == null) {

            head = tail = null;

        }

        return item;

    }

    public E peek() {

        return this.head == null ? null : (E)this.head.item;

    }

}

從上面代碼不難看出，鏈式隊列其實就是鏈表的基本操作，所以LinkedList也是Queue的一個實現。隊列的鏈式實現的本質是隊列的形成過程中，利用線性鏈表的原理，來生成一個隊列。想了解更多有趣的數據結構，學習更多的數據結構知識，可以觀看本站的數據結構和算法教程，讓我們的學習實現質的飛躍！