1 隊列的鏈式存儲實現

跟Stack鏈式存儲結構不同，在Queue鏈式存儲結構中需要設置兩個節點：一個head隊頭節點，一個tail隊尾節點。現在我們來看看在鏈式存儲結構中，如何實現Enqueue與Dequeue兩個方法。

（1）入隊：Enqueue

<code>public void EnQueue(T item)
{
    Node oldLastNode = tail;
    tail = new Node();
    tail.Item = item;

    if(IsEmpty())
    {
        head = tail;
    }
    else
    {
        oldLastNode.Next = tail;
    }

    size++;
}/<code>

入隊操作就是在鏈表的末尾插入一個新節點，將原來的尾節點的Next指針指向新節點。

（2）出隊：Dequeue

<code>public T DeQueue()
{
    T result = head.Item;
    head = head.Next;
    size--;

    if(IsEmpty())
    {
        tail = null;
    }
    return result;
}/<code>

出隊操作本質就是返回鏈表中的第一個元素即頭結點，這裡可以考慮到如果隊列為空，將tail和head設為null以加快垃圾回收。

模擬的隊列鏈式存儲結構的完整代碼如下，這裡就不再做基本功能測試了，有興趣的讀者可以自行測試：

<code>/// <summary>
/// 基於鏈表的隊列節點
/// /<summary>
/// <typeparam>
public class Node
{
    public T Item { get; set; }
    public Node Next { get; set; }

    public Node(T item) 

    {
        this.Item = item;
    }

    public Node()
    { }
}

/// <summary>
/// 基於鏈表的隊列實現
/// /<summary>
/// <typeparam>類型/<typeparam>
public class MyLinkQueue
{
    private Node head;
    private Node tail;
    private int size;

    public MyLinkQueue()
    {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /// <summary>
    /// 入隊操作
    /// /<summary>
    /// <param>節點元素
    public void EnQueue(T item)
    {
        Node oldLastNode = tail;
        tail = new Node();
        tail.Item = item;

        if(IsEmpty())
        {
            head = tail;
        }
        else
        {
            oldLastNode.Next = tail;
        }
 

        size++;
    }

    /// <summary>
    /// 出隊操作
    /// /<summary>
    /// <returns>出隊元素/<returns>
    public T DeQueue()
    {
        T result = head.Item;
        head = head.Next;
        size--;

        if(IsEmpty())
        {
            tail = null;
        }
        return result;
    }

    /// <summary>
    /// 是否為空隊列
    /// /<summary>
    /// <returns>true/false/<returns>
    public bool IsEmpty()
    {
        return this.size == 0;
    }

    /// <summary>
    /// 隊列中節點個數
    /// /<summary>
    public int Size
    {
        get
        {
            return this.size;
        }
    }
}/<code>

2 循環隊列

首先，我們來看看下面的情景，在數組容量固定的情況下，隊頭指針之前有空閒的位置，而隊尾指針卻已經指向了末尾，這時再插入一個元素時，隊尾指針會指向哪裡？

圖1

從圖中可以看出，目前如果接著入隊的話，因數組末尾元素已經佔用，再向後加，就會產生數組越界的錯誤，可實際上，我們的隊列在下標為0和1的地方還是空閒的。我們把這種現象叫做“假溢出”。現實當中，你上了公交車，發現前排有兩個空座位，而後排所有座位都已經坐滿，你會怎麼做？立馬下車，並對自己說，後面沒座了，我等下一輛？沒有這麼笨的人，前面有座位，當然也是可以坐的，除非坐滿了，才會考慮下一輛。

所以解決假溢出的辦法就是後面滿了，就再從頭開始，也就是頭尾相接的循環。我們把隊列的這種頭尾相接的順序存儲結構稱為循環隊列。在循環隊列中需要注意的幾個問題是：

（1）入隊與出隊的索引位置如何確定？

這裡我們可以藉助%運算對head和tail兩個指針進行位置確定，實現方式如下所示：

<code>// 移動隊尾指針 

tail = (tail + 1) % items.Length;
// 移動隊頭指針
head = (head + 1) % items.Length;/<code>

（2）在隊列容量固定時如何判斷隊列空還是隊列滿？

① 設置一個標誌變量flag，當head==tail，且flag=0時為隊列空，當head==tail，且flag=1時為隊列滿。

② 當隊列空時，條件就是head=tail，當隊列滿時，我們修改其條件，保留一個元素空間。也就是說，隊列滿時，數組中還有一個空閒單元。如下圖所示：

圖2

從上圖可以看出，由於tail可能比head大，也可能比head小，所以儘管它們只相差一個位置時就是滿的情況，但也可能是相差整整一圈。所以若隊列的最大尺寸為QueueSize，那麼隊列滿的條件是 (tail+1)%QueueSize==head（取模“%”的目的就是為了整合tail與head大小為一個問題）。比如上面這個例子，QueueSize=5，圖中的左邊front=0，而rear=4，(4+1)%5=0，所以此時隊列滿。再比如圖中的右邊，front=2而rear=1。(1+1)%5=2，所以此時隊列也是滿的。

（3）由於tail可能比head大，也可能比head小，那麼隊列的長度如何計算？

當tail>head時，此時隊列的長度為tail-head。但當tail

(tail-head+QueueSize)%QueueSize。