一、什么是隊(duì)列？
1.先進(jìn)者先出，這就是典型的“隊(duì)列”結(jié)構(gòu)。
2.支持兩個(gè)操作：入隊(duì)enqueue()，放一個(gè)數(shù)據(jù)到隊(duì)尾；出隊(duì)dequeue()，從隊(duì)頭取一個(gè)元素。
3.所以和棧一樣，隊(duì)列也是一種操作受限的線性表。

1.png

    public class Queue
    {
        private string[] items;
        private int n = 0;

        private int head = 0;
        private int tail = 0;

        public Queue(int capacity)
        {
            items = new string[capacity];
            n = capacity;
        }

        /// <summary>
        /// 入隊(duì)
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        public bool enqueue(string str)
        {
            //表示隊(duì)尾沒有空間了
            if (tail == n)
            {
                //隊(duì)列已滿，
                if (head == 0) return false;
                //當(dāng)隊(duì)尾沒有空間，對(duì)頭有空間時(shí)，將數(shù)據(jù)遷移
                for (int i = head; i < tail; i++)
                {
                    items[i - head] = items[i];
                }
                tail -= head;
                head = 0;
            }
            items[tail] = str;
            tail++;
            return true;
        }

        /// <summary>
        /// 出隊(duì)
        /// </summary>
        /// <returns></returns>
        public string dequeue()
        {
            //隊(duì)列為空
            if (tail == head) return "";
            string s = items[head];
            head++;
            return s;
        }
    }

三、隊(duì)列有哪些常見的應(yīng)用？
1.阻塞隊(duì)列
1）在隊(duì)列的基礎(chǔ)上增加阻塞操作，就成了阻塞隊(duì)列。
2）阻塞隊(duì)列就是在隊(duì)列為空的時(shí)候，從隊(duì)頭取數(shù)據(jù)會(huì)被阻塞，因?yàn)榇藭r(shí)還沒有數(shù)據(jù)可取，直到隊(duì)列中有了數(shù)據(jù)才能返回；如果隊(duì)列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會(huì)被阻塞，直到隊(duì)列中有空閑位置后再插入數(shù)據(jù)，然后在返回。
3）從上面的定義可以看出這就是一個(gè)“生產(chǎn)者-消費(fèi)者模型”。這種基于阻塞隊(duì)列實(shí)現(xiàn)的“生產(chǎn)者-消費(fèi)者模型”可以有效地協(xié)調(diào)生產(chǎn)和消費(fèi)的速度。當(dāng)“生產(chǎn)者”生產(chǎn)數(shù)據(jù)的速度過快，“消費(fèi)者”來不及消費(fèi)時(shí)，存儲(chǔ)數(shù)據(jù)的隊(duì)列很快就會(huì)滿了，這時(shí)生產(chǎn)者就阻塞等待，直到“消費(fèi)者”消費(fèi)了數(shù)據(jù)，“生產(chǎn)者”才會(huì)被喚醒繼續(xù)生產(chǎn)。不僅如此，基于阻塞隊(duì)列，我們還可以通過協(xié)調(diào)“生產(chǎn)者”和“消費(fèi)者”的個(gè)數(shù)，來提高數(shù)據(jù)處理效率，比如配置幾個(gè)消費(fèi)者，來應(yīng)對(duì)一個(gè)生產(chǎn)者。
2.并發(fā)隊(duì)列
1）在多線程的情況下，會(huì)有多個(gè)線程同時(shí)操作隊(duì)列，這時(shí)就會(huì)存在線程安全問題。能夠有效解決線程安全問題的隊(duì)列就稱為并發(fā)隊(duì)列。
2）并發(fā)隊(duì)列簡單的實(shí)現(xiàn)就是在enqueue()、dequeue()方法上加鎖，但是鎖粒度大并發(fā)度會(huì)比較低，同一時(shí)刻僅允許一個(gè)存或取操作。
3）實(shí)際上，基于數(shù)組的循環(huán)隊(duì)列利用CAS原子操作，可以實(shí)現(xiàn)非常高效的并發(fā)隊(duì)列。這也是循環(huán)隊(duì)列比鏈?zhǔn)疥?duì)列應(yīng)用更加廣泛的原因。
3.線程池資源枯竭是的處理
在資源有限的場景，當(dāng)沒有空閑資源時(shí)，基本上都可以通過“隊(duì)列”這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)請(qǐng)求排隊(duì)。