數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)溫故-3.隊列

在日常生活中，隊列的例子比比皆是，例如在車展排隊買票，排在隊頭的處理完離開，后來的必須在隊尾排隊等候。在程序設(shè)計中，隊列也有著廣泛的應(yīng)用，例如計算機的任務(wù)調(diào)度系統(tǒng)、為了削減高峰時期訂單請求的消息隊列等等。與棧類似，隊列也是屬于操作受限的線性表，不過隊列是只允許在一端進行插入，在另一端進行刪除。在其他數(shù)據(jù)結(jié)構(gòu)如樹的一些基本操作中（比如樹的廣度優(yōu)先遍歷）也需要借助隊列來實現(xiàn)，因此這里我們來看看隊列。

一、隊列的概念及操作

1.1 隊列的基本特征

隊列（queue）是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。它是一種先進先出（First In First Out）的線性表，簡稱FIFO。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。

1.2 隊列的基本操作

　　（1）入隊（Enqueue）：將一個數(shù)據(jù)元素插入隊尾；

　　（2）出隊（Dequeue）：讀取隊頭節(jié)點數(shù)據(jù)并刪除該節(jié)點；

二、隊列的基本實現(xiàn)

　　既然隊列也屬于特殊的線性表，那么其實現(xiàn)也會有兩種形式：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。首先，對于Queue，我們希望能夠提供以下幾個方法供調(diào)用：

Queue<T>()	創(chuàng)建一個空的隊列
void Enqueue(T s)	往隊列中添加一個新的元素
T Dequeue()	移除隊列中最早添加的元素
bool IsEmpty()	隊列是否為空
int Size()	隊列中元素的個數(shù)

2.1 隊列的順序存儲實現(xiàn)

　　與Stack不同，在隊列中我們需要定義一個head隊頭“指針”和tail隊尾“指針”，當新元素入隊時tail+1，當老元素出隊時head+1。下面重點來看看Enqueue和Dequeue兩個方法的代碼實現(xiàn)。

　　（1）入隊：Enqueue

        public void EnQueue(T item)
        {
            if (Size == items.Length)
            {
                // 擴大數(shù)組容量
                ResizeCapacity(items.Length * 2);
            }

            items[tail] = item;
            tail++;
            size++;
        }

　　新元素入隊后，tail隊尾指針向前移動指向下一個新元素要插入的位置；這里仍然模仿.NET中的實現(xiàn)，在數(shù)組容量不足時及時進行擴容以容納新元素入隊。

　　（2）出隊：Dequeue

        public T DeQueue()
        {
            if (Size == 0)
            {
                return default(T);
            }

            T item = items[head];
            items[head] = default(T);
            head++;

            if (head > 0 && Size == items.Length / 4)
            {
                // 縮小數(shù)組容量
                ResizeCapacity(items.Length / 2);
            }

            size--;
            return item;
        }

　　在對老元素進行出隊操作時，首先取得head指針所指向的老元素，然后將head指針向前移動一位指向下一個將出隊的老元素。這里將要出隊的元素所在數(shù)組中的位置重置為默認值。最后判斷容量是否過小，如果是則進行數(shù)組容量的縮小。

　　下面是完整的隊列模擬實現(xiàn)代碼，僅供參考，這里就不再做基本功能測試了，有興趣的讀者可以自行測試：

    /// <summary>
    /// 基于數(shù)組的隊列實現(xiàn)
    /// </summary>
    /// <typeparam name="T">類型</typeparam>
    public class MyArrayQueue<T>
    {
        private T[] items;
        private int size;
        private int head;
        private int tail;

        public MyArrayQueue(int capacity)
        {
            this.items = new T[capacity];
            this.size = 0;
            this.head = this.tail = 0;
        }

        /// <summary>
        /// 入隊
        /// </summary>
        /// <param name="item">入隊元素</param>
        public void EnQueue(T item)
        {
            if (Size == items.Length)
            {
                // 擴大數(shù)組容量
                ResizeCapacity(items.Length * 2);
            }

            items[tail] = item;
            tail++;
            size++;
        }

        /// <summary>v 
        /// 出隊
        /// </summary>
        /// <returns>出隊元素</returns>
        public T DeQueue()
        {
            if (Size == 0)
            {
                return default(T);
            }

            T item = items[head];
            items[head] = default(T);
            head++;

            if (head > 0 && Size == items.Length / 4)
            {
                // 縮小數(shù)組容量
                ResizeCapacity(items.Length / 2);
            }

            size--;
            return item;
        }

        /// <summary>
        /// 重置數(shù)組大小
        /// </summary>
        /// <param name="newCapacity">新的容量</param>
        private void ResizeCapacity(int newCapacity)
        {
            T[] newItems = new T[newCapacity];
            int index = 0;
            if (newCapacity > items.Length)
            {
                for (int i = 0; i < items.Length; i++)
                {
                    newItems[index++] = items[i];
                }
            }
            else
            {
                for (int i = 0; i < items.Length; i++)
                {
                    if (!items[i].Equals(default(T)))
                    {
                        newItems[index++] = items[i];
                    }
                }

                head = tail = 0;
            }

            items = newItems;
        }

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

        /// <summary>
        /// 棧中節(jié)點個數(shù)
        /// </summary>
        public int Size
        {
            get
            {
                return this.size;
            }
        }
    }

View Code

2.2 隊列的鏈式存儲實現(xiàn)

　　跟Stack鏈式存儲結(jié)構(gòu)不同，在Queue鏈式存儲結(jié)構(gòu)中需要設(shè)置兩個節(jié)點：一個head隊頭節(jié)點，一個tail隊尾節(jié)點。現(xiàn)在我們來看看在鏈式存儲結(jié)構(gòu)中，如何實現(xiàn)Enqueue與Dequeue兩個方法。

　　（1）入隊：Enqueue

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

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

            size++;
        }

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

　　（2）出隊：Dequeue

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

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

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

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

    /// <summary>
    /// 基于鏈表的隊列節(jié)點
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class Node<T>
    {
        public T Item { get; set; }
        public Node<T> Next { get; set; }

        public Node(T item)
        {
            this.Item = item;
        }

        public Node()
        { }
    }

    /// <summary>
    /// 基于鏈表的隊列實現(xiàn)
    /// </summary>
    /// <typeparam name="T">類型</typeparam>
    public class MyLinkQueue<T>
    {
        private Node<T> head;
        private Node<T> tail;
        private int size;

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

        /// <summary>
        /// 入隊操作
        /// </summary>
        /// <param name="node">節(jié)點元素</param>
        public void EnQueue(T item)
        {
            Node<T> oldLastNode = tail;
            tail = new Node<T>();
            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>
        /// 隊列中節(jié)點個數(shù)
        /// </summary>
        public int Size
        {
            get
            {
                return this.size;
            }
        }
    }

View Code

2.3 循環(huán)隊列

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

圖1

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

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

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

　　這里我們可以借助%運算對head和tail兩個指針進行位置確定，實現(xiàn)方式如下所示：

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

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

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

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

圖2

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

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

　　當tail>head時，此時隊列的長度為tail-head。但當tail<head時，隊列長度分為兩段，一段是QueueSize-head，另一段是0+tail，加在一起，隊列長度為tail-head+QueueSize。因此通用的計算隊列長度公式為：(tail-head+QueueSize)%QueueSize。

三、隊列的應(yīng)用場景

　　隊列在實際開發(fā)中應(yīng)用得非常廣泛，這里來看看在互聯(lián)網(wǎng)系統(tǒng)中常見的一個應(yīng)用場景：消息隊列。“消息”是在兩臺計算機間傳送的數(shù)據(jù)單位。消息可以非常簡單，例如只包含文本字符串；也可以更復(fù)雜，可能包含嵌入對象。消息被發(fā)送到隊列中，“消息隊列”是在消息的傳輸過程中保存消息的容器。

　　在目前廣泛的Web應(yīng)用中，都會出現(xiàn)一種場景：在某一個時刻，網(wǎng)站會迎來一個用戶請求的高峰期（比如：淘寶的雙十一購物狂歡節(jié)，12306的春運搶票節(jié)等），一般的設(shè)計中，用戶的請求都會被直接寫入數(shù)據(jù)庫或文件中，在高并發(fā)的情形下會對數(shù)據(jù)庫服務(wù)器或文件服務(wù)器造成巨大的壓力，同時呢，也使響應(yīng)延遲加劇。這也說明了，為什么我們當時那么地抱怨和吐槽這些網(wǎng)站的響應(yīng)速度了。當時2011年的京東圖書促銷，曾一直出現(xiàn)在購物車中點擊“購買”按鈕后一直是“Service is too busy”，其實就是因為當時的并發(fā)訪問量過大，超過了系統(tǒng)的最大負載能力。當然，后邊，劉強東臨時購買了不少服務(wù)器進行擴展以求增強處理并發(fā)請求的能力，還請了信息部的人員“喝茶”，現(xiàn)在京東已經(jīng)是超大型的網(wǎng)上商城了，我也有同學在京東成都研究院工作了。

service is too busy!

　　從京東當年的“Service is too busy”不難看出，高并發(fā)的用戶請求是網(wǎng)站成長過程中必不可少的過程，也是一個必須要解決的難題。在眾多的實踐當中，除了增加服務(wù)器數(shù)量配置服務(wù)器集群實現(xiàn)伸縮性架構(gòu)設(shè)計之外，異步操作也被廣泛采用。而異步操作中最核心的就是使用消息隊列，通過消息隊列，將短時間高并發(fā)產(chǎn)生的事務(wù)消息存儲在消息隊列中，從而削平高峰期的并發(fā)事務(wù)，改善網(wǎng)站系統(tǒng)的性能。在京東之類的電子商務(wù)網(wǎng)站促銷活動中，合理地使用消息隊列，可以有效地抵御促銷活動剛開始就開始大量涌入的訂單對系統(tǒng)造成的沖擊。

message queue

四、.NET中的Queue<T>

　　雖然隊列有順序存儲和鏈式存儲兩種存儲方式，但在.NET中使用的是順序存儲，它所對應(yīng)的集合類是System.Collections.Queue與System.Collections.Generic.Queue<T>，兩者結(jié)構(gòu)相同，不同之處僅在于前者是非泛型版本，后者是泛型版本的隊列。它們都屬于循環(huán)隊列，這里我們通過Reflector來重點看看泛型版本的實現(xiàn)。

　　我們來看看在.NET中的Queue<T>是如何實現(xiàn)入隊和出隊操作的。首先來看看入隊Enqueue方法：

public void Enqueue(T item)
{
    if (this._size == this._array.Length)
    {
        int capacity = (this._array.Length * 200) / 100;
        if (capacity < (this._array.Length + 4))
        {
            capacity = this._array.Length + 4;
        }
        this.SetCapacity(capacity);
    }
    this._array[this._tail] = item;
    this._tail = (this._tail + 1) % this._array.Length;
    this._size++;
    this._version++;
}

　　可以看出，與我們之前所實現(xiàn)的Enqueue方法類似，首先判斷了隊列是否滿了，如果滿了則進行擴容，不同之處在我們是直接*2倍，這里是在原有容量基礎(chǔ)上+4。由于是循環(huán)隊列，對tail指針使用了%運算來確定下一個入隊位置。

　　我們再來看看Dequeue方法時怎么實現(xiàn)的：

public T Dequeue()
{
    if (this._size == 0)
    {
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);
    }
    T local = this._array[this._head];
    this._array[this._head] = default(T);
    this._head = (this._head + 1) % this._array.Length;
    this._size--;
    this._version++;
    return local;
}

　　同樣，與之前類似，不同之處在于判斷隊空時這里直接拋了異常，其次由于是循環(huán)隊列，head指針也使用了%運算來確定下一個出隊元素的位置。

參考資料

（1）程杰，《大話數(shù)據(jù)結(jié)構(gòu)》

（2）陳廣，《數(shù)據(jù)結(jié)構(gòu)（C#語言描述）》

（3）段恩澤，《數(shù)據(jù)結(jié)構(gòu)（C#語言版）》

（4）yangecnu，《淺談算法與數(shù)據(jù)結(jié)構(gòu)：—棧和隊列》

（5）李智慧，《大型網(wǎng)站技術(shù)架構(gòu)：核心原理與案例分析》

（6）Edison Chou，《Redis初探：消息隊列》

作者：周旭龍

出處：http://edisonchou.cnblogs.com

本文版權(quán)歸作者和博客園共有，歡迎轉(zhuǎn)載，但未經(jīng)作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文鏈接。

posted @ 2015-07-05 10:27 EdisonZhou 閱讀(2791) 評論(3) 收藏舉報

刷新頁面返回頂部

Edison Zhou

To be a happy Developer and Blogger!