算法系列15天速成 第九天 隊(duì)列
一：概念
隊(duì)列是一個(gè)”先進(jìn)先出“的線性表，牛X的名字就是“First in First Out(FIFO)”，生活中有很多這樣的場(chǎng)景，比如讀書的時(shí)候去食堂打飯時(shí)的”排隊(duì)“。當(dāng)然我們拒絕插隊(duì)。
二：存儲(chǔ)結(jié)構(gòu)
前幾天也說過，線性表有兩種”存儲(chǔ)結(jié)構(gòu)“，① 順序存儲(chǔ),②鏈?zhǔn)酱鎯?chǔ)。當(dāng)然“隊(duì)列”也脫離不了這兩種服務(wù)，這里我就分享一下“順序存儲(chǔ)”。
順序存儲(chǔ)時(shí)，我們會(huì)維護(hù)一個(gè)叫做”head頭指針“和”tail尾指針“，分別指向隊(duì)列的開頭和結(jié)尾。
代碼段如下：
#region 隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
/// <summary>
/// 隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
/// </summary>
/// <typeparam name="T"></typeparam>
public class SeqQueue<T>
{
private const int maxSize = 100;
public int MaxSize
{
get { return maxSize; }
}
/// <summary>
/// 順序隊(duì)列的存儲(chǔ)長(zhǎng)度
/// </summary>
public T[] data = new T[maxSize];
//頭指針
public int head;
//尾指針
public int tail;
}
#endregion
三：常用操作
隊(duì)列的操作一般分為：
①： 初始化隊(duì)列。
②: 出隊(duì)。
③： 入隊(duì)。
④： 獲取隊(duì)頭。
⑤： 獲取隊(duì)長(zhǎng)。
1：初始化隊(duì)列
這個(gè)很簡(jiǎn)單，剛才也說過了，隊(duì)列是用一個(gè)head和tail的指針來維護(hù)。分別設(shè)置為0即可。
2：出隊(duì)
看著“隊(duì)列”的結(jié)構(gòu)圖，大家都知道，出隊(duì)肯定跟head指針有關(guān)，需要做兩件事情，
第一： 判斷隊(duì)列是否為空，這個(gè)我想大家都知道。
第二： 將head頭指針向后移動(dòng)一位，返回head移動(dòng)前的元素，時(shí)間復(fù)雜度為O(1)。
代碼段如下：
#region 隊(duì)列元素出隊(duì)
/// <summary>
/// 隊(duì)列元素出隊(duì)
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public T SeqQueueOut<T>(SeqQueue<T> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("隊(duì)列已空，不能進(jìn)行出隊(duì)操作");
var single = seqQueue.data[seqQueue.head];
//head指針自增
seqQueue.data[seqQueue.head++] = default(T);
return single;
}
#endregion
3：入隊(duì)
這個(gè)跟”出隊(duì)“的思想相反，同樣也是需要做兩件事情。
第一：判斷隊(duì)列是否已滿。
第二：將tail指針向后移動(dòng)一位，時(shí)間復(fù)雜度為O(1)。
代碼段如下：
#region 隊(duì)列元素入隊(duì)
/// <summary>
/// 隊(duì)列元素入隊(duì)
/// </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)
{
//如果隊(duì)列已滿，則不能進(jìn)行入隊(duì)操作
if (SeqQueueIsFull(seqQueue))
throw new Exception("隊(duì)列已滿,不能入隊(duì)操作");
//入隊(duì)操作
seqQueue.data[seqQueue.tail++] = data;
return seqQueue;
}
#endregion
4： 獲取隊(duì)頭
知道”出隊(duì)“和”入隊(duì)“的原理，相信大家都懂的如何進(jìn)行”獲取隊(duì)頭“操作，唯一不一樣的就是
他是只讀操作，不會(huì)損壞”隊(duì)列“結(jié)構(gòu)，時(shí)間復(fù)雜度為O（1）。
代碼段如下：
#region 獲取隊(duì)頭元素
/// <summary>
/// 獲取隊(duì)頭元素
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("隊(duì)列已空，不能進(jìn)行出隊(duì)操作");
return seqQueue.data[seqQueue.head];
}
#endregion
5: 獲取隊(duì)長(zhǎng)
大家都知道，我們是用數(shù)組來實(shí)現(xiàn)隊(duì)列，所以千萬不要想當(dāng)然的認(rèn)為數(shù)組長(zhǎng)度是XXX，
我們維護(hù)的是一個(gè)head和tail的指針，所以長(zhǎng)度自然就是tail-head咯，時(shí)間復(fù)雜度為O(1)。
代碼段如下：
/// <summary>
/// 獲取隊(duì)列長(zhǎng)度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
{
return seqQueue.tail - seqQueue.head;
}
然后上一下總的運(yùn)行代碼：
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("目前隊(duì)列是否為空：" + queueManage.SeqQueueIsEmpty(seqQueue) + "\n");
Console.WriteLine("將ID=1和ID=2的實(shí)體加入隊(duì)列");
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("將隊(duì)頭出隊(duì)");
//將隊(duì)頭出隊(duì)
var student = queueManage.SeqQueueOut(seqQueue);
Display(seqQueue);
//獲取隊(duì)頂元素
student = queueManage.SeqQueuePeek(seqQueue);
Console.Read();
}
//展示隊(duì)列元素
static void Display(SeqQueue<Student> 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ù)實(shí)體
/// <summary>
/// 學(xué)生數(shù)據(jù)實(shí)體
/// </summary>
public class Student
{
public int ID { get; set; }
public string Name { get; set; }
public int Age { get; set; }
}
#endregion
#region 隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
/// <summary>
/// 隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
/// </summary>
/// <typeparam name="T"></typeparam>
public class SeqQueue<T>
{
private const int maxSize = 100;
public int MaxSize
{
get { return maxSize; }
}
/// <summary>
/// 順序隊(duì)列的存儲(chǔ)長(zhǎng)度
/// </summary>
public T[] data = new T[maxSize];
//頭指針
public int head;
//尾指針
public int tail;
}
#endregion
#region 隊(duì)列的基本操作
/// <summary>
/// 隊(duì)列的基本操作
/// </summary>
public class SeqQueueClass
{
#region 隊(duì)列的初始化操作
/// <summary>
/// 隊(duì)列的初始化操作
/// </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 隊(duì)列是否為空
/// <summary>
/// 隊(duì)列是否為空
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public bool SeqQueueIsEmpty<T>(SeqQueue<T> seqQueue)
{
//如果兩指針重合，說明隊(duì)列已經(jīng)清空
if (seqQueue.head == seqQueue.tail)
return true;
return false;
}
#endregion
#region 隊(duì)列是否已滿
/// <summary>
/// 隊(duì)列是否已滿
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public bool SeqQueueIsFull<T>(SeqQueue<T> seqQueue)
{
//如果尾指針到達(dá)數(shù)組末尾，說明隊(duì)列已經(jīng)滿
if (seqQueue.tail == seqQueue.MaxSize)
return true;
return false;
}
#endregion
#region 隊(duì)列元素入隊(duì)
/// <summary>
/// 隊(duì)列元素入隊(duì)
/// </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)
{
//如果隊(duì)列已滿，則不能進(jìn)行入隊(duì)操作
if (SeqQueueIsFull(seqQueue))
throw new Exception("隊(duì)列已滿,不能入隊(duì)操作");
//入隊(duì)操作
seqQueue.data[seqQueue.tail++] = data;
return seqQueue;
}
#endregion
#region 隊(duì)列元素出隊(duì)
/// <summary>
/// 隊(duì)列元素出隊(duì)
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public T SeqQueueOut<T>(SeqQueue<T> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("隊(duì)列已空，不能進(jìn)行出隊(duì)操作");
var single = seqQueue.data[seqQueue.head];
//head指針自增
seqQueue.data[seqQueue.head++] = default(T);
return single;
}
#endregion
#region 獲取隊(duì)頭元素
/// <summary>
/// 獲取隊(duì)頭元素
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("隊(duì)列已空，不能進(jìn)行出隊(duì)操作");
return seqQueue.data[seqQueue.head];
}
#endregion
/// <summary>
/// 獲取隊(duì)列長(zhǎng)度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
{
return seqQueue.tail - seqQueue.head;
}
}
#endregion
}
三：順序隊(duì)列的缺陷
大家看這張圖，不知道可有什么異樣的感覺，在這種狀態(tài)下，我入隊(duì)操作，發(fā)現(xiàn)程序提示隊(duì)列
已滿，但是tnd我這個(gè)數(shù)組還有一個(gè)空間啊，是的，這就是所謂的“假溢出”。
四：循環(huán)隊(duì)列
俗話說的好啊，“沒有跨不過的坎”。
1: 概念
之所以叫“循環(huán)”，得益于神奇的“%”。他讓隊(duì)列的首位進(jìn)行相連，形成了一個(gè)我們思維中的
“圈圈”。
2：循環(huán)公式
tail=(tail+1)%array.Length;
多看幾眼，大家就看通了其中循環(huán)的道理，我要做成如下的圖:
3：對(duì)循環(huán)的改造
先前看了一些資料，有的壓根就是錯(cuò)的，有的說想要循環(huán)，就要犧牲一個(gè)單位的空間。
我覺得沒必要。我既要循環(huán)又不犧牲空間，所以下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("目前隊(duì)列是否為空：" + queueManage.SeqQueueIsEmpty(seqQueue) + "\n");
Console.WriteLine("將ID=1，2，3的實(shí)體加入隊(duì)列\(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)前隊(duì)列個(gè)數(shù)：" + queueManage.SeqQueueLen(seqQueue) + "");
Console.WriteLine("\n*********************************************\n");
Console.WriteLine("我要出隊(duì)了\n");
queueManage.SeqQueueOut(seqQueue);
Console.WriteLine("哈哈，看看跟順序隊(duì)列異樣之處，我再入隊(duì)，看是否溢出\n");
queueManage.SeqQueueIn(seqQueue, new Student() { ID = 4, Name = "博客園", Age = 23 });
Console.WriteLine("\n....一切正常，入隊(duì)成功");
Console.WriteLine("\n當(dāng)前隊(duì)列個(gè)數(shù)：" + queueManage.SeqQueueLen(seqQueue) + "");
Console.Read();
}
}
#region 學(xué)生數(shù)據(jù)實(shí)體
/// <summary>
/// 學(xué)生數(shù)據(jù)實(shí)體
/// </summary>
public class Student
{
public int ID { get; set; }
public string Name { get; set; }
public int Age { get; set; }
}
#endregion
#region 隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
/// <summary>
/// 隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
/// </summary>
/// <typeparam name="T"></typeparam>
public class SeqQueue<T>
{
private const int maxSize = 3;
public int MaxSize
{
get { return maxSize; }
}
/// <summary>
/// 順序隊(duì)列的存儲(chǔ)長(zhǎng)度
/// </summary>
public T[] data = new T[maxSize];
//頭指針
public int head;
//尾指針
public int tail;
//隊(duì)列中有效的數(shù)字個(gè)數(shù)
public int size;
}
#endregion
#region 隊(duì)列的基本操作
/// <summary>
/// 隊(duì)列的基本操作
/// </summary>
public class SeqQueueClass
{
#region 隊(duì)列的初始化操作
/// <summary>
/// 隊(duì)列的初始化操作
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
public SeqQueue<T> SeqQueueInit<T>(SeqQueue<T> seqQueue)
{
seqQueue.size = seqQueue.head = seqQueue.tail = 0;
return seqQueue;
}
#endregion
#region 隊(duì)列是否為空
/// <summary>
/// 隊(duì)列是否為空
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public bool SeqQueueIsEmpty<T>(SeqQueue<T> seqQueue)
{
//如果兩指針重合，說明隊(duì)列已經(jīng)清空
if (seqQueue.size == 0)
return true;
return false;
}
#endregion
#region 隊(duì)列是否已滿
/// <summary>
/// 隊(duì)列是否已滿
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public bool SeqQueueIsFull<T>(SeqQueue<T> seqQueue)
{
//采用循環(huán)隊(duì)列后，頭指針
if (seqQueue.size == seqQueue.MaxSize)
return true;
return false;
}
#endregion
#region 隊(duì)列元素入隊(duì)
/// <summary>
/// 隊(duì)列元素入隊(duì)
/// </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)
{
//如果隊(duì)列已滿，則不能進(jìn)行入隊(duì)操作
if (SeqQueueIsFull(seqQueue))
throw new Exception("隊(duì)列已滿，還入啥隊(duì)列??！");
//采用循環(huán)隊(duì)列,必須先賦值，在自增tail指針
seqQueue.data[seqQueue.tail] = data;
seqQueue.tail = (seqQueue.tail + 1) % seqQueue.MaxSize;
//隊(duì)列實(shí)際元素增加
seqQueue.size++;
return seqQueue;
}
#endregion
#region 隊(duì)列元素出隊(duì)
/// <summary>
/// 隊(duì)列元素出隊(duì)
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public T SeqQueueOut<T>(SeqQueue<T> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("隊(duì)列已空，大哥，不要在出隊(duì)了！");
//循環(huán)隊(duì)列出隊(duì)，展現(xiàn)的是head的靈活性
seqQueue.head = (seqQueue.head + 1) % seqQueue.MaxSize;
//隊(duì)列實(shí)際元素遞減
seqQueue.size--;
return seqQueue.data[seqQueue.head];
}
#endregion
#region 獲取隊(duì)頭元素
/// <summary>
/// 獲取隊(duì)頭元素
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
{
if (SeqQueueIsEmpty(seqQueue))
throw new Exception("隊(duì)列已空，不能進(jìn)行出隊(duì)操作");
return seqQueue.data[seqQueue.head];
}
#endregion
#region 獲取隊(duì)列長(zhǎng)度
/// <summary>
/// 獲取隊(duì)列長(zhǎng)度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
{
return seqQueue.size;
}
#endregion
}
#endregion
}
相關(guān)文章
一些數(shù)據(jù)庫系統(tǒng)或者某些數(shù)據(jù)表只允許用戶添加數(shù)據(jù)，而不能修改或者刪除以往的記錄，此時(shí)我們就必須在程序進(jìn)行控制。有些程序員通過不顯示以往的數(shù)據(jù)來保證，下面我們介紹一種既可以看到原始記錄，有不容許用戶修改這些記錄的方法2008-11-11
這篇文章主要介紹了windows下gitbash安裝教程(小白教程)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
計(jì)算機(jī)網(wǎng)絡(luò)日常練習(xí)題,每天進(jìn)步一點(diǎn)點(diǎn)
下面小編就為大家?guī)硪黄?jì)算機(jī)網(wǎng)絡(luò)的幾道練習(xí)題(分享)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧，希望可以幫到你2021-09-09
隨著互聯(lián)網(wǎng)的普及和發(fā)展,爬蟲技術(shù)也越來越多地被應(yīng)用到各個(gè)領(lǐng)域,然而,在實(shí)際使用中,爬蟲可能會(huì)遇到各種問題導(dǎo)致無法正常工作,本文將探討導(dǎo)致爬蟲無法使用的原因,并給出相應(yīng)的解決方法2023-10-10
這篇文章主要介紹了WebStorm 遇到的問題總結(jié)的相關(guān)資料,需要的朋友可以參考下2017-03-03
永恒之藍(lán)實(shí)戰(zhàn)教程之Mac通過Metasploit攻擊Server2008的詳細(xì)過程
這篇文章主要介紹了永恒之藍(lán)實(shí)戰(zhàn)教程?Mac通過Metasploit攻擊Server2008,首先準(zhǔn)備一個(gè)Server2008，主要功能是使網(wǎng)絡(luò)上的機(jī)器能夠共享計(jì)算機(jī)文件、打印機(jī)、串行端口和通訊等資源，需要的朋友可以參考下2022-08-08
關(guān)于IE11修改User-agent不再支持document.all等
這篇文章主要介紹了關(guān)于IE11修改User-agent不再支持document.all等,需要的朋友可以參考下2015-12-12
這篇文章主要介紹了在ubuntu18.04版本安裝vscode，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05
這篇文章主要介紹了在github上怎樣修改語言設(shè)置問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-09-09
使用Postman測(cè)試需要授權(quán)的接口問題
Postman是一款免費(fèi)的http模擬請(qǐng)求工具，常用來測(cè)試開發(fā)接口。實(shí)際場(chǎng)景中，很多接口是需要授權(quán)才能使用,這篇文章主要介紹了用Postman測(cè)試需要授權(quán)的接口,需要的朋友可以參考下2022-06-06