一:概念
隊列是一個”先進(jìn)先出“的線性表,牛X的名字就是“First in First Out(FIFO)”,生活中有很多這樣的場景,比如讀書的時候去食堂打飯時的”排隊“。當(dāng)然我們拒絕插隊。
二:存儲結(jié)構(gòu)
前幾天也說過,線性表有兩種”存儲結(jié)構(gòu)“,① 順序存儲,②鏈?zhǔn)酱鎯?。?dāng)然“隊列”也脫離不了這兩種服務(wù),這里我就分享一下“順序存儲”。
順序存儲時,我們會維護(hù)一個叫做”head頭指針“和”tail尾指針“,分別指向隊列的開頭和結(jié)尾。
代碼段如下:
復(fù)制代碼 代碼如下:
#region 隊列的數(shù)據(jù)結(jié)構(gòu)
/// summary>
/// 隊列的數(shù)據(jù)結(jié)構(gòu)
/// /summary>
/// typeparam name="T">/typeparam>
public class SeqQueueT>
{
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的指針來維護(hù)。分別設(shè)置為0即可。
2:出隊
看著“隊列”的結(jié)構(gòu)圖,大家都知道,出隊肯定跟head指針有關(guān),需要做兩件事情,
第一: 判斷隊列是否為空,這個我想大家都知道。
第二: 將head頭指針向后移動一位,返回head移動前的元素,時間復(fù)雜度為O(1)。
代碼段如下:
復(fù)制代碼 代碼如下:
#region 隊列元素出隊
/// summary>
/// 隊列元素出隊
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
public T SeqQueueOutT>(SeqQueueT> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("隊列已空,不能進(jìn)行出隊操作");
var single = seqQueue.data[seqQueue.head];
//head指針自增
seqQueue.data[seqQueue.head++] = default(T);
return single;
}
#endregion
3:入隊
這個跟”出隊“的思想相反,同樣也是需要做兩件事情。
第一:判斷隊列是否已滿。
第二:將tail指針向后移動一位,時間復(fù)雜度為O(1)。
代碼段如下:
復(fù)制代碼 代碼如下:
#region 隊列元素入隊
/// summary>
/// 隊列元素入隊
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// param name="data">/param>
/// returns>/returns>
public SeqQueueT> SeqQueueInT>(SeqQueueT> seqQueue, T data)
{
//如果隊列已滿,則不能進(jìn)行入隊操作
if (SeqQueueIsFull(seqQueue))
throw new Exception("隊列已滿,不能入隊操作");
//入隊操作
seqQueue.data[seqQueue.tail++] = data;
return seqQueue;
}
#endregion
4: 獲取隊頭
知道”出隊“和”入隊“的原理,相信大家都懂的如何進(jìn)行”獲取隊頭“操作,唯一不一樣的就是
他是只讀操作,不會破壞”隊列“結(jié)構(gòu),時間復(fù)雜度為O(1)。
代碼段如下:
復(fù)制代碼 代碼如下:
#region 獲取隊頭元素
/// summary>
/// 獲取隊頭元素
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
public T SeqQueuePeekT>(SeqQueueT> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("隊列已空,不能進(jìn)行出隊操作");
return seqQueue.data[seqQueue.head];
}
#endregion
5: 獲取隊長
大家都知道,我們是用數(shù)組來實現(xiàn)隊列,所以千萬不要想當(dāng)然的認(rèn)為數(shù)組長度是XXX,
我們維護(hù)的是一個head和tail的指針,所以長度自然就是tail-head咯,時間復(fù)雜度為O(1)。
代碼段如下:
復(fù)制代碼 代碼如下:
/// summary>
/// 獲取隊列長度
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
public int SeqQueueLenT>(SeqQueueT> seqQueue)
{
return seqQueue.tail - seqQueue.head;
}
然后上一下總的運行代碼:
復(fù)制代碼 代碼如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SeqQueue
{
public class Program
{
static void Main(string[] args)
{
SeqQueueStudent> seqQueue = new SeqQueueStudent>();
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 = "一線碼農(nóng)", Age = 23 });
Display(seqQueue);
Console.WriteLine("將隊頭出隊");
//將隊頭出隊
var student = queueManage.SeqQueueOut(seqQueue);
Display(seqQueue);
//獲取隊頂元素
student = queueManage.SeqQueuePeek(seqQueue);
Console.Read();
}
//展示隊列元素
static void Display(SeqQueueStudent> seqQueue)
{
Console.WriteLine("******************* 鏈表數(shù)據(jù)如下 *******************");
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("******************* 鏈表數(shù)據(jù)展示完畢 *******************\n");
}
}
#region 學(xué)生數(shù)據(jù)實體
/// summary>
/// 學(xué)生數(shù)據(jù)實體
/// /summary>
public class Student
{
public int ID { get; set; }
public string Name { get; set; }
public int Age { get; set; }
}
#endregion
#region 隊列的數(shù)據(jù)結(jié)構(gòu)
/// summary>
/// 隊列的數(shù)據(jù)結(jié)構(gòu)
/// /summary>
/// typeparam name="T">/typeparam>
public class SeqQueueT>
{
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
#region 隊列的基本操作
/// summary>
/// 隊列的基本操作
/// /summary>
public class SeqQueueClass
{
#region 隊列的初始化操作
/// summary>
/// 隊列的初始化操作
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
public SeqQueueT> SeqQueueInitT>(SeqQueueT> 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 SeqQueueIsEmptyT>(SeqQueueT> seqQueue)
{
//如果兩指針重合,說明隊列已經(jīng)清空
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 SeqQueueIsFullT>(SeqQueueT> seqQueue)
{
//如果尾指針到達(dá)數(shù)組末尾,說明隊列已經(jīng)滿
if (seqQueue.tail == seqQueue.MaxSize)
return true;
return false;
}
#endregion
#region 隊列元素入隊
/// summary>
/// 隊列元素入隊
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// param name="data">/param>
/// returns>/returns>
public SeqQueueT> SeqQueueInT>(SeqQueueT> seqQueue, T data)
{
//如果隊列已滿,則不能進(jìn)行入隊操作
if (SeqQueueIsFull(seqQueue))
throw new Exception("隊列已滿,不能入隊操作");
//入隊操作
seqQueue.data[seqQueue.tail++] = data;
return seqQueue;
}
#endregion
#region 隊列元素出隊
/// summary>
/// 隊列元素出隊
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
public T SeqQueueOutT>(SeqQueueT> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("隊列已空,不能進(jìn)行出隊操作");
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 SeqQueuePeekT>(SeqQueueT> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("隊列已空,不能進(jìn)行出隊操作");
return seqQueue.data[seqQueue.head];
}
#endregion
/// summary>
/// 獲取隊列長度
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
public int SeqQueueLenT>(SeqQueueT> seqQueue)
{
return seqQueue.tail - seqQueue.head;
}
}
#endregion
}
三:順序隊列的缺陷
大家看這張圖,不知道可有什么異樣的感覺,在這種狀態(tài)下,我入隊操作,發(fā)現(xiàn)程序提示隊列
已滿,但是tnd我這個數(shù)組還有一個空間啊,是的,這就是所謂的“假溢出”。
四:循環(huán)隊列
俗話說的好啊,“沒有跨不過的坎”。
1: 概念
之所以叫“循環(huán)”,得益于神奇的“%”。他讓隊列的首位進(jìn)行相連,形成了一個我們思維中的
“圈圈”。
2:循環(huán)公式
tail=(tail+1)%array.Length;
多看幾眼,大家就看通了其中循環(huán)的道理,我要做成如下的圖:
3:對循環(huán)的改造
先前看了一些資料,有的壓根就是錯的,有的說想要循環(huán),就要犧牲一個單位的空間。
我覺得沒必要。我既要循環(huán)又不犧牲空間,所以反射了一下framework中的Queue類。
改造后代碼如下:
復(fù)制代碼 代碼如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SeqQueue
{
public class Program
{
static void Main(string[] args)
{
SeqQueueStudent> seqQueue = new SeqQueueStudent>();
SeqQueueClass queueManage = new SeqQueueClass();
Console.WriteLine("目前隊列是否為空:" + queueManage.SeqQueueIsEmpty(seqQueue) + "\n");
Console.WriteLine("將ID=1,2,3的實體加入隊列\(zhòng)n");
queueManage.SeqQueueIn(seqQueue, new Student() { ID = 1, Name = "hxc520", Age = 23 });
queueManage.SeqQueueIn(seqQueue, new Student() { ID = 2, Name = "一線碼農(nóng)", Age = 23 });
queueManage.SeqQueueIn(seqQueue, new Student() { ID = 3, Name = "51cto", Age = 23 });
Console.WriteLine("\n當(dāng)前隊列個數(shù):" + 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當(dāng)前隊列個數(shù):" + queueManage.SeqQueueLen(seqQueue) + "");
Console.Read();
}
}
#region 學(xué)生數(shù)據(jù)實體
/// summary>
/// 學(xué)生數(shù)據(jù)實體
/// /summary>
public class Student
{
public int ID { get; set; }
public string Name { get; set; }
public int Age { get; set; }
}
#endregion
#region 隊列的數(shù)據(jù)結(jié)構(gòu)
/// summary>
/// 隊列的數(shù)據(jù)結(jié)構(gòu)
/// /summary>
/// typeparam name="T">/typeparam>
public class SeqQueueT>
{
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;
//隊列中有效的數(shù)字個數(shù)
public int size;
}
#endregion
#region 隊列的基本操作
/// summary>
/// 隊列的基本操作
/// /summary>
public class SeqQueueClass
{
#region 隊列的初始化操作
/// summary>
/// 隊列的初始化操作
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
public SeqQueueT> SeqQueueInitT>(SeqQueueT> seqQueue)
{
seqQueue.size = seqQueue.head = seqQueue.tail = 0;
return seqQueue;
}
#endregion
#region 隊列是否為空
/// summary>
/// 隊列是否為空
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
public bool SeqQueueIsEmptyT>(SeqQueueT> seqQueue)
{
//如果兩指針重合,說明隊列已經(jīng)清空
if (seqQueue.size == 0)
return true;
return false;
}
#endregion
#region 隊列是否已滿
/// summary>
/// 隊列是否已滿
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
public bool SeqQueueIsFullT>(SeqQueueT> seqQueue)
{
//采用循環(huán)隊列后,頭指針
if (seqQueue.size == seqQueue.MaxSize)
return true;
return false;
}
#endregion
#region 隊列元素入隊
/// summary>
/// 隊列元素入隊
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// param name="data">/param>
/// returns>/returns>
public SeqQueueT> SeqQueueInT>(SeqQueueT> seqQueue, T data)
{
//如果隊列已滿,則不能進(jìn)行入隊操作
if (SeqQueueIsFull(seqQueue))
throw new Exception("隊列已滿,還入啥隊列??!");
//采用循環(huán)隊列,必須先賦值,在自增tail指針
seqQueue.data[seqQueue.tail] = data;
seqQueue.tail = (seqQueue.tail + 1) % seqQueue.MaxSize;
//隊列實際元素增加
seqQueue.size++;
return seqQueue;
}
#endregion
#region 隊列元素出隊
/// summary>
/// 隊列元素出隊
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
public T SeqQueueOutT>(SeqQueueT> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("隊列已空,大哥,不要在出隊了!");
//循環(huán)隊列出隊,展現(xiàn)的是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 SeqQueuePeekT>(SeqQueueT> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("隊列已空,不能進(jìn)行出隊操作");
return seqQueue.data[seqQueue.head];
}
#endregion
#region 獲取隊列長度
/// summary>
/// 獲取隊列長度
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
public int SeqQueueLenT>(SeqQueueT> seqQueue)
{
return seqQueue.size;
}
#endregion
}
#endregion
}
您可能感興趣的文章:- 算法系列15天速成 第十四天 圖【上】
- 算法系列15天速成——第十三天 樹操作【下】
- 算法系列15天速成 第十二天 樹操作【中】
- 算法系列15天速成 第十一天 樹操作(上)
- 算法系列15天速成 第十天 棧
- 算法系列15天速成 第八天 線性表【下】
- 算法系列15天速成 第七天 線性表【上】
- 算法系列15天速成 第六天 五大經(jīng)典查找【下】
- 算法系列15天速成 第五天 五大經(jīng)典查找【中】
- 算法系列15天速成 第四天 五大經(jīng)典查找【上】
- 算法系列15天速成 第三天 七大經(jīng)典排序【下】
- 算法系列15天速成 第二天 七大經(jīng)典排序【中】
- 算法系列15天速成 第一天 七大經(jīng)典排序【上】
- 算法系列15天速成——第十五天 圖【下】(大結(jié)局)