算法系列15天速成第九天隊列

2024-09-08 23:18:40

字體：大中小

來源：轉載

供稿：網友

一：概念

隊列是一個”先進先出“的線性表，牛X的名字就是“First in First Out(FIFO)”，生活中有很多這樣的場景，比如讀書的時候去食堂打飯時的”排隊“。當然我們拒絕插隊。

二：存儲結構

前幾天也說過，線性表有兩種”存儲結構“，① 順序存儲,②鏈式存儲。當然“隊列”也脫離不了這兩種服務，這里我就分享一下“順序存儲”。

順序存儲時，我們會維護一個叫做”head頭指針“和”tail尾指針“，分別指向隊列的開頭和結尾。

代碼段如下：

復制代碼代碼如下:

#region 隊列的數據結構
    /// <summary>
/// 隊列的數據結構
/// </summary>
/// <typeparam name="T"></typeparam>
    public class SeqQueue<T>
    {
        private const int maxSize = 100;

        public int MaxSize
        {
            get { return maxSize; }
        }

/// <summary>
/// 順序隊列的存儲長度
/// </summary>
public T[] data = new T[maxSize];

//頭指針
public int head;

//尾指針
public int tail;

}
#endregion

三：常用操作

隊列的操作一般分為：

①：初始化隊列。

②: 出隊。

③：入隊。

④：獲取隊頭。

⑤：獲取隊長。

1：初始化隊列

這個很簡單，剛才也說過了，隊列是用一個head和tail的指針來維護。分別設置為0即可。

2：出隊

看著“隊列”的結構圖，大家都知道，出隊肯定跟head指針有關，需要做兩件事情，

第一：判斷隊列是否為空，這個我想大家都知道。
第二：將head頭指針向后移動一位，返回head移動前的元素，時間復雜度為O(1)。

代碼段如下：

復制代碼代碼如下:

#region 隊列元素出隊
        /// <summary>
/// 隊列元素出隊
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public T SeqQueueOut<T>(SeqQueue<T> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("隊列已空，不能進行出隊操作");

var single = seqQueue.data[seqQueue.head];

//head指針自增
seqQueue.data[seqQueue.head++] = default(T);

return single;

}
#endregion

3：入隊

這個跟”出隊“的思想相反，同樣也是需要做兩件事情。

第一：判斷隊列是否已滿。

第二：將tail指針向后移動一位，時間復雜度為O(1)。

代碼段如下：

復制代碼代碼如下:

#region 隊列元素入隊
        /// <summary>
/// 隊列元素入隊
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <param name="data"></param>
/// <returns></returns>
        public SeqQueue<T> SeqQueueIn<T>(SeqQueue<T> seqQueue, T data)
        {
            //如果隊列已滿，則不能進行入隊操作
            if (SeqQueueIsFull(seqQueue))
                throw new Exception("隊列已滿,不能入隊操作");

//入隊操作
seqQueue.data[seqQueue.tail++] = data;

            return seqQueue;
        }
        #endregion

4：獲取隊頭

知道”出隊“和”入隊“的原理，相信大家都懂的如何進行”獲取隊頭“操作，唯一不一樣的就是

他是只讀操作，不會破壞”隊列“結構，時間復雜度為O（1）。

代碼段如下：

復制代碼代碼如下:

#region 獲取隊頭元素
        /// <summary>
        /// 獲取隊頭元素
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="seqQueue"></param>
        /// <returns></returns>
        public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("隊列已空，不能進行出隊操作");

            return seqQueue.data[seqQueue.head];
        }
        #endregion

5: 獲取隊長

大家都知道，我們是用數組來實現隊列，所以千萬不要想當然的認為數組長度是XXX，

我們維護的是一個head和tail的指針，所以長度自然就是tail-head咯，時間復雜度為O(1)。

代碼段如下：

復制代碼代碼如下:

/// <summary>
/// 獲取隊列長度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
        {
            return seqQueue.tail - seqQueue.head;
        }

然后上一下總的運行代碼：

復制代碼代碼如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SeqQueue
{
    public class Program
    {
        static void Main(string[] args)
        {
            SeqQueue<Student> seqQueue = new SeqQueue<Student>();

SeqQueueClass queueManage = new SeqQueueClass();

Console.WriteLine("目前隊列是否為空：" + queueManage.SeqQueueIsEmpty(seqQueue) + "/n");

            Console.WriteLine("將ID=1和ID=2的實體加入隊列");
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 1, Name = "hxc520", Age = 23 });
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 2, Name = "一線碼農", Age = 23 });

Display(seqQueue);

            Console.WriteLine("將隊頭出隊");
            //將隊頭出隊
            var student = queueManage.SeqQueueOut(seqQueue);

Display(seqQueue);

//獲取隊頂元素
student = queueManage.SeqQueuePeek(seqQueue);

            Console.Read();
        }
        //展示隊列元素
        static void Display(SeqQueue<Student> seqQueue)
        {
            Console.WriteLine("******************* 鏈表數據如下 *******************");

            for (int i = seqQueue.head; i < seqQueue.tail; i++)
                Console.WriteLine("ID:" + seqQueue.data[i].ID +
                                  ",Name:" + seqQueue.data[i].Name +
                                  ",Age:" + seqQueue.data[i].Age);

            Console.WriteLine("******************* 鏈表數據展示完畢 *******************/n");
        }
    }

    #region 學生數據實體
    /// <summary>
/// 學生數據實體
/// </summary>
    public class Student
    {
        public int ID { get; set; }

public string Name { get; set; }

        public int Age { get; set; }
    }
    #endregion

        public int MaxSize
        {
            get { return maxSize; }
        }

/// <summary>
/// 順序隊列的存儲長度
/// </summary>
public T[] data = new T[maxSize];

//頭指針
public int head;

//尾指針
public int tail;

}
#endregion

    #region 隊列的基本操作
    /// <summary>
/// 隊列的基本操作
/// </summary>
    public class SeqQueueClass
    {
        #region 隊列的初始化操作
        /// <summary>
/// 隊列的初始化操作
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
        public SeqQueue<T> SeqQueueInit<T>(SeqQueue<T> seqQueue)
        {
            seqQueue.head = 0;
            seqQueue.tail = 0;

            return seqQueue;
        }
        #endregion

        #region 隊列是否為空
        /// <summary>
/// 隊列是否為空
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public bool SeqQueueIsEmpty<T>(SeqQueue<T> seqQueue)
        {
            //如果兩指針重合，說明隊列已經清空
            if (seqQueue.head == seqQueue.tail)
                return true;
            return false;
        }
        #endregion

        #region 隊列是否已滿
        /// <summary>
/// 隊列是否已滿
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public bool SeqQueueIsFull<T>(SeqQueue<T> seqQueue)
        {
            //如果尾指針到達數組末尾，說明隊列已經滿
            if (seqQueue.tail == seqQueue.MaxSize)
                return true;
            return false;
        }
        #endregion

//入隊操作
seqQueue.data[seqQueue.tail++] = data;

            return seqQueue;
        }
        #endregion

var single = seqQueue.data[seqQueue.head];

//head指針自增
seqQueue.data[seqQueue.head++] = default(T);

return single;

}
#endregion

        #region 獲取隊頭元素
        /// <summary>
/// 獲取隊頭元素
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("隊列已空，不能進行出隊操作");

            return seqQueue.data[seqQueue.head];
        }
        #endregion

        /// <summary>
/// 獲取隊列長度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
        {
            return seqQueue.tail - seqQueue.head;
        }
    }
    #endregion
}

三：順序隊列的缺陷

大家看這張圖，不知道可有什么異樣的感覺，在這種狀態下，我入隊操作，發現程序提示隊列

已滿，但是tnd我這個數組還有一個空間啊，是的，這就是所謂的“假溢出”。

四：循環隊列

俗話說的好啊，“沒有跨不過的坎”。

1: 概念

之所以叫“循環”，得益于神奇的“%”。他讓隊列的首位進行相連，形成了一個我們思維中的

“圈圈”。

2：循環公式

tail=(tail+1)%array.Length;

多看幾眼，大家就看通了其中循環的道理，我要做成如下的圖:

3：對循環的改造

先前看了一些資料，有的壓根就是錯的，有的說想要循環，就要犧牲一個單位的空間。

我覺得沒必要。我既要循環又不犧牲空間，所以反射了一下framework中的Queue類。

改造后代碼如下：

復制代碼代碼如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SeqQueue
{
    public class Program
    {
        static void Main(string[] args)
        {
            SeqQueue<Student> seqQueue = new SeqQueue<Student>();

SeqQueueClass queueManage = new SeqQueueClass();

Console.WriteLine("目前隊列是否為空：" + queueManage.SeqQueueIsEmpty(seqQueue) + "/n");

            Console.WriteLine("將ID=1，2，3的實體加入隊列/n");
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 1, Name = "hxc520", Age = 23 });
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 2, Name = "一線碼農", Age = 23 });
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 3, Name = "51cto", Age = 23 });

Console.WriteLine("/n當前隊列個數：" + queueManage.SeqQueueLen(seqQueue) + "");

Console.WriteLine("/n*********************************************/n");

Console.WriteLine("我要出隊了/n");
queueManage.SeqQueueOut(seqQueue);

            Console.WriteLine("哈哈，看看跟順序隊列異樣之處，我再入隊，看是否溢出/n");
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 4, Name = "博客園", Age = 23 });
            Console.WriteLine("/n....一切正常，入隊成功");

Console.WriteLine("/n當前隊列個數：" + queueManage.SeqQueueLen(seqQueue) + "");

            Console.Read();
        }
    }

    #region 學生數據實體
    /// <summary>
/// 學生數據實體
/// </summary>
    public class Student
    {
        public int ID { get; set; }

public string Name { get; set; }

        public int Age { get; set; }
    }
    #endregion

    #region 隊列的數據結構
    /// <summary>
/// 隊列的數據結構
/// </summary>
/// <typeparam name="T"></typeparam>
    public class SeqQueue<T>
    {
        private const int maxSize = 3;

        public int MaxSize
        {
            get { return maxSize; }
        }

/// <summary>
/// 順序隊列的存儲長度
/// </summary>
public T[] data = new T[maxSize];

//頭指針
public int head;

//尾指針
public int tail;

        //隊列中有效的數字個數
        public int size;
    }
    #endregion

            return seqQueue;
        }
        #endregion

        #region 隊列是否為空
        /// <summary>
/// 隊列是否為空
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public bool SeqQueueIsEmpty<T>(SeqQueue<T> seqQueue)
        {
            //如果兩指針重合，說明隊列已經清空
            if (seqQueue.size == 0)
                return true;
            return false;
        }
        #endregion

        #region 隊列是否已滿
        /// <summary>
/// 隊列是否已滿
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public bool SeqQueueIsFull<T>(SeqQueue<T> seqQueue)
        {
            //采用循環隊列后，頭指針
            if (seqQueue.size == seqQueue.MaxSize)
                return true;
            return false;
        }
        #endregion

            //采用循環隊列,必須先賦值，在自增tail指針
            seqQueue.data[seqQueue.tail] = data;
            seqQueue.tail = (seqQueue.tail + 1) % seqQueue.MaxSize;

//隊列實際元素增加
seqQueue.size++;

            return seqQueue;
        }
        #endregion

//循環隊列出隊，展現的是head的靈活性
seqQueue.head = (seqQueue.head + 1) % seqQueue.MaxSize;

//隊列實際元素遞減
seqQueue.size--;

            return seqQueue.data[seqQueue.head];
        }
        #endregion

        #region 獲取隊頭元素
        /// <summary>
/// 獲取隊頭元素
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("隊列已空，不能進行出隊操作");

            return seqQueue.data[seqQueue.head];
        }
        #endregion

        #region 獲取隊列長度
        /// <summary>
/// 獲取隊列長度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
        {
            return seqQueue.size;
        }
        #endregion
    }
    #endregion
}