柚子快報(bào)邀請(qǐng)碼778899分享：算法 C++：隊(duì)列的實(shí)現(xiàn)和使用
柚子快報(bào)邀請(qǐng)碼778899分享：算法 C++：隊(duì)列的實(shí)現(xiàn)和使用
目錄
一、隊(duì)列的簡(jiǎn)介
1.隊(duì)列的基本操作
2.隊(duì)列的分類
3.隊(duì)列的應(yīng)用場(chǎng)景
二、順序隊(duì)列的實(shí)現(xiàn)?
三、鏈隊(duì)列的實(shí)現(xiàn)?
四、STL庫(kù)中的隊(duì)列?
?
一、隊(duì)列的簡(jiǎn)介
????????隊(duì)列（Queue）是一種線性數(shù)據(jù)結(jié)構(gòu)，其特點(diǎn)是數(shù)據(jù)的插入和刪除操作分別在不同的兩端進(jìn)行：插入操作在隊(duì)列的尾部，刪除操作在隊(duì)列的頭部。因此，隊(duì)列遵循先進(jìn)先出（FIFO, First In First Out）的原則，即最早進(jìn)入隊(duì)列的元素最先被處理。
1.隊(duì)列的基本操作
enqueue（入隊(duì)）：向隊(duì)列的尾部添加一個(gè)元素。dequeue（出隊(duì)）：返回隊(duì)列頭部的元素，且移除該元素。front（取隊(duì)頭）：返回隊(duì)列頭部的元素，但不移除該元素。empty（判空）：判斷隊(duì)列中是否有元素。
2.隊(duì)列的分類
????????根據(jù)隊(duì)列的不同用途和實(shí)現(xiàn)方式，隊(duì)列可以分為幾類：
普通隊(duì)列（Simple Queue）：最常見的隊(duì)列類型，插入操作在隊(duì)尾，刪除操作在隊(duì)頭，按先進(jìn)先出的順序執(zhí)行。 循環(huán)隊(duì)列（Circular Queue）：在普通隊(duì)列的基礎(chǔ)上，當(dāng)隊(duì)尾到達(dá)隊(duì)列末端時(shí)，如果隊(duì)頭前面有空位，隊(duì)尾可以繞回到隊(duì)列的開頭。這種實(shí)現(xiàn)方式能夠更有效地利用存儲(chǔ)空間，避免“假溢出”問(wèn)題（隊(duì)尾指針到達(dá)末尾但隊(duì)列仍有空間）。 雙端隊(duì)列（Deque, Double-Ended Queue）：允許在隊(duì)列的兩端進(jìn)行插入和刪除操作。根據(jù)操作限制的不同，雙端隊(duì)列可以進(jìn)一步分為以下幾種：
輸入受限雙端隊(duì)列：只能從一端進(jìn)行插入，但可以從兩端刪除。輸出受限雙端隊(duì)列：可以從兩端插入，但只能從一端刪除。 優(yōu)先隊(duì)列（Priority Queue）：隊(duì)列中的每個(gè)元素都有一個(gè)優(yōu)先級(jí)，刪除元素時(shí)并非按照進(jìn)入隊(duì)列的順序，而是按照優(yōu)先級(jí)高低來(lái)決定出隊(duì)的順序。通常，優(yōu)先級(jí)高的元素會(huì)先被處理。
3.隊(duì)列的應(yīng)用場(chǎng)景
????????隊(duì)列作為一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于各種場(chǎng)景中，尤其是在需要按序處理任務(wù)的場(chǎng)景下。常見的應(yīng)用場(chǎng)景有：
操作系統(tǒng)中的任務(wù)調(diào)度：操作系統(tǒng)通過(guò)隊(duì)列管理進(jìn)程或線程的執(zhí)行順序，按時(shí)間片調(diào)度進(jìn)程。廣度優(yōu)先搜索（BFS）：在圖的廣度優(yōu)先遍歷中，使用隊(duì)列來(lái)管理待訪問(wèn)的節(jié)點(diǎn)。緩存（Buffer）系統(tǒng)：隊(duì)列被用于處理生產(chǎn)者-消費(fèi)者問(wèn)題，如輸入輸出緩沖、數(shù)據(jù)流緩沖。消息隊(duì)列（Message Queue）：在分布式系統(tǒng)或異步任務(wù)處理系統(tǒng)中，隊(duì)列用于存儲(chǔ)和分發(fā)消息，保證消息的按序處理。
二、順序隊(duì)列的實(shí)現(xiàn)?
? ? ? ? ?這里介紹循環(huán)隊(duì)列的實(shí)現(xiàn)。
構(gòu)造函數(shù)：將隊(duì)頭指針peek指向數(shù)組低端0，隊(duì)尾指針rear指向-1。析構(gòu)函數(shù)：循環(huán)隊(duì)列是靜態(tài)存儲(chǔ)分配，在循環(huán)隊(duì)列變量退出作用域時(shí)自動(dòng)釋放所占內(nèi)存單元，因此循環(huán)隊(duì)列無(wú)需銷毀，析構(gòu)函數(shù)為空。入隊(duì)操作：隊(duì)尾指針rear循環(huán)意義下+1，然后將待插元素插入隊(duì)尾即可。出隊(duì)操作：取出隊(duì)頭，然后隊(duì)頭指針peek循環(huán)意義下+1即可。取對(duì)頭操作：直接取出對(duì)頭元素即可。判空操作：判斷隊(duì)列元素個(gè)數(shù)是否為0即可。
template
class Cirqueue
{
public:
Cirqueue() //構(gòu)造函數(shù)
{
rear = -1;
peek = 0;
count = 0;
}
~Cirqueue() {} //析構(gòu)函數(shù)
void enqueue(T x) //入隊(duì)
{
if (count==size)
{
throw "上溢"; //隊(duì)滿，防上溢
}
rear = (rear + 1) % size;
//隊(duì)尾指針在循環(huán)意義下+1
data[rear] = x;
//在隊(duì)尾存入數(shù)據(jù)
count++;
//元素個(gè)數(shù)+1
}
T dequeue() //出隊(duì)
{
if (count==0)
{
throw "下溢"; //隊(duì)空，防下溢
}
T temp = data[peek];
//暫存隊(duì)頭數(shù)據(jù)
peek = (peek + 1) % size;
//隊(duì)頭指針在循環(huán)意義下+1
count--;
//元素個(gè)數(shù)-1
return temp;
}
T front() //取隊(duì)頭
{
if (count==0)
{
throw "下溢"; //隊(duì)空，防下溢
}
return data[peek];
}
bool empty() //判空
{
return count == 0;
}
private:
const static int size = 100000; //隊(duì)列長(zhǎng)度
T data[size]; //用于存儲(chǔ)數(shù)據(jù)的數(shù)組
int peek; //隊(duì)頭指針
int rear; //隊(duì)尾指針
int count; //隊(duì)列元素計(jì)數(shù)
};
說(shuō)明：循環(huán)意義下是指在一個(gè)范圍內(nèi)變化，如x%size的值在[0,size-1]之間變化。
三、鏈隊(duì)列的實(shí)現(xiàn)?
? ? ? ? 這里介紹鏈隊(duì)列的實(shí)現(xiàn)。?
構(gòu)造函數(shù) ：將隊(duì)頭指針peek和隊(duì)尾指針rear都初始化為空指針nullptr。析構(gòu)函數(shù)：鏈隊(duì)列是動(dòng)態(tài)存儲(chǔ)分配，需要釋放鏈隊(duì)列的所有結(jié)點(diǎn)的存儲(chǔ)空間。入隊(duì)操作：只考慮在鏈表的尾部進(jìn)行。出隊(duì)操作：只考慮在鏈表的頭部進(jìn)行。取隊(duì)頭操作：直接通過(guò)隊(duì)頭指針取隊(duì)頭元素。判空操作：只需判斷count是否為0。隊(duì)列大小：只需返回count。
template
class LinkQueue
{
public:
LinkQueue() //構(gòu)造函數(shù)
{
peek = nullptr;
rear = nullptr;
count = 0;
}
~LinkQueue() //析構(gòu)函數(shù)
{
while (!empty())
{
dequeue();
//將結(jié)點(diǎn)逐個(gè)釋放
}
}
void enqueue(T x) //入隊(duì)
{
Node* s = new Node;
if (rear == nullptr)
{
s->data = x;
s->next = nullptr;
peek = rear = s;
// 如果隊(duì)列為空，peek和rear都指向新結(jié)點(diǎn)
}
else
{
s->data = x;
s->next = nullptr;
rear->next = s;
rear = s;
//如果隊(duì)列非空，新結(jié)點(diǎn)插入隊(duì)尾
}
count++;
}
T dequeue() //出隊(duì)
{
if (count == 0)
{
throw "隊(duì)列下溢";
}
Node* p = peek;
// 暫存當(dāng)前的隊(duì)頭節(jié)點(diǎn)
T temp = peek->data;
// 獲取隊(duì)頭節(jié)點(diǎn)的數(shù)據(jù)
peek = peek->next;
// 更新隊(duì)頭指針，指向下一個(gè)節(jié)點(diǎn)
if (peek == nullptr)
{
rear = nullptr;
// 如果隊(duì)列變?yōu)榭眨瑒t將rear也設(shè)置為nullptr
}
delete p;
// 釋放原隊(duì)頭節(jié)點(diǎn)的內(nèi)存
count--;
return temp;
}
T front() const //取隊(duì)頭
{
if (count == 0)
{
throw "隊(duì)列下溢";
}
return peek->data;
}
bool empty() const //判空
{
return count == 0;
}
int size() const //查元素個(gè)數(shù)
{
return count;
}
private:
struct Node
{
T data; // 數(shù)據(jù)域
Node* next; // 指針域
};
Node* peek; // 隊(duì)頭指針
Node* rear; // 隊(duì)尾指針
int count; // 隊(duì)列元素計(jì)數(shù)
};
四、STL庫(kù)中的隊(duì)列?
????????隊(duì)列這樣的數(shù)據(jù)結(jié)構(gòu)已經(jīng)在STL庫(kù)中定義好了，如果沒(méi)有自行設(shè)計(jì)隊(duì)列的要求，可以直接使用庫(kù)中定義好的隊(duì)列。STL庫(kù)中有單端隊(duì)列和雙端隊(duì)列，現(xiàn)簡(jiǎn)單介紹其用法如下：?
#include
queue
q.push('a'); //入隊(duì)
q.pop(); //出隊(duì)
q.back(); //取隊(duì)尾
q.front(); //取隊(duì)頭
q.empty(); //判空，返回bool值
q.size(); //查詢隊(duì)列元素個(gè)數(shù)
/***************************************************************************/
#include
deque
d.push_front('a'); //在隊(duì)頭入隊(duì)
d.push_back('b'); //在隊(duì)尾入隊(duì)
d.pop_front(); //在隊(duì)頭出隊(duì)
d.pop_back(); //在隊(duì)尾出隊(duì)
d.back(); //取隊(duì)尾
d.front(); //取隊(duì)頭
d.empty(); //判空，返回bool值
d.size(); //查看隊(duì)列元素個(gè)數(shù)
柚子快報(bào)邀請(qǐng)碼778899分享：算法 C++：隊(duì)列的實(shí)現(xiàn)和使用
精彩文章
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Bunnings外貿(mào)家居園
