1. 前言
今天我們來(lái)學(xué)習(xí)C++stl六大組件的其中一種，容器適配器，stack、queue及priority_queue都是容器適配器。我們循序漸進(jìn)，接下來(lái)讓我們先認(rèn)識(shí)一下什么是容器適配器。
2. 容器適配器
2.1 容器適配器的介紹
適配器是一種設(shè)計(jì)模式(設(shè)計(jì)模式是一套被反復(fù)使用的、多數(shù)人知曉的、經(jīng)過(guò)分類編目的、代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié))，該種模式是將一個(gè)類的接口轉(zhuǎn)換成客戶希望的另外一個(gè)接口。
2.2 STL標(biāo)準(zhǔn)庫(kù)中stack和queue的底層結(jié)構(gòu)
雖然stack和queue中也可以存放元素，但在STL中并沒(méi)有將其劃分在容器的行列，而是將其稱為容器適配器，這是因?yàn)閟tack和隊(duì)列只是對(duì)其他容器的接口進(jìn)行了包裝，STL中stack和queue默認(rèn)使用deque。比如：
2.3 deque的簡(jiǎn)單介紹
deque(雙端隊(duì)列)：是一種雙開(kāi)口的"連續(xù)"空間的數(shù)據(jù)結(jié)構(gòu)，雙開(kāi)口的含義是：可以在頭尾兩端進(jìn)行插入和刪除操作，且時(shí)間復(fù)雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。
deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實(shí)際deque類似于一個(gè)動(dòng)態(tài)的二維數(shù)組,雙端隊(duì)列底層是一段假象的連續(xù)空間，實(shí)際是分段連續(xù)的，為了維護(hù)其“整體連續(xù)”以及隨機(jī)訪問(wèn)的假象，落在了deque的迭代器身上，因此deque的迭代器設(shè)計(jì)就比較復(fù)雜。
2.4 deque的缺陷
與vector比較：
deque的優(yōu)勢(shì)是：頭部插入和刪除時(shí)，不需要搬移元素，效率特別高，而且在擴(kuò)容時(shí)，也不需要搬移大量的元素，因此其效率是必vector高的。
與list比較：
其底層是連續(xù)空間，空間利用率比較高，不需要存儲(chǔ)額外字段。
但是，deque有一個(gè)致命缺陷：
不適合遍歷，因?yàn)樵诒闅v時(shí)，deque的迭代器要頻繁的去檢測(cè)其是否移動(dòng)到某段小空間的邊界，導(dǎo)致效率低下，而序列式場(chǎng)景中，可能需要經(jīng)常遍歷，因此在實(shí)際中，需要線性結(jié)構(gòu)時(shí)，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應(yīng)用并不多，而目前能看到的一個(gè)應(yīng)用就是，STL用其作為stack和queue的底層數(shù)據(jù)結(jié)構(gòu)。
2.5 為什么選擇deque作為stack和queue的底層默認(rèn)容器
stack是一種后進(jìn)先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，因此只要具有push_back()和pop_back()操作的線性結(jié)構(gòu)，都可以作為stack的底層容器，比如vector和list都可以；queue是先進(jìn)先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，只要具有push_back和pop_front操作的線性結(jié)構(gòu)，都可以作為queue的底層容器，比如list。但是STL中對(duì)stack和queue默認(rèn)選擇deque作為其底層容器，主要是因?yàn)椋?br> 1.stack和queue不需要遍歷(因此stack和queue沒(méi)有迭代器)，只需要在固定的一端或者兩端進(jìn)行操作。
2.在stack中元素增長(zhǎng)時(shí)，deque比vector的效率高(擴(kuò)容時(shí)不需要搬移大量數(shù)據(jù))；queue中的元素增長(zhǎng)
時(shí)，deque不僅效率高，而且內(nèi)存使用率高。
3. stack
3.1 stack的介紹
1.stack是一種容器適配器，專門用在具有后進(jìn)先出操作的上下文環(huán)境中，其刪除只能從容器的一端進(jìn)行元素的插入與提取操作。
2.stack是作為容器適配器被實(shí)現(xiàn)的，容器適配器即是對(duì)特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來(lái)訪問(wèn)其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。
3.stack的底層容器可以是任何標(biāo)準(zhǔn)的容器類模板或者一些其他特定的容器類，這些容器類應(yīng)該支持以下操作：
empty：判空操作
back：獲取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部刪除元素操作
4.標(biāo)準(zhǔn)容器vector、deque、list均符合這些需求，默認(rèn)情況下，如果沒(méi)有為stack指定特定的底層容器，默認(rèn)情況下使用deque。
3.2 stack的使用
| 函數(shù)名稱 | 功能說(shuō)明 |
|---|---|
| stack() | 構(gòu)造空的棧 |
| empty() | 檢測(cè)stack是否為空 |
| size() | 返回stack中元素的個(gè)數(shù) |
| top() | 返回棧頂元素的引用 |
| push() | 將元素val壓入stack中 |
| pop() | 將stack中尾部的元素彈出 |
void Test1()
{
//fiora::stack<int,vector<int>> st;
//fiora::stack<int, list<int>> st;
//fiora::stack<int> st;
//stack<int,vector<int>> st;
//stack<int, list<int>> st;
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
}
3.3 stack模擬實(shí)現(xiàn)
namespace fiora
{
template<class T, class Container = deque<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
T& top()
{
return _con.back();
}
const T& top() const
{
return _con.back();
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
private:
Container _con;
};
}
測(cè)試：
void Test1()
{
//fiora::stack<int,vector<int>> st;
fiora::stack<int, list<int>> st1;
fiora::stack<int> st;
//stack<int,vector<int>> st;
//stack<int, list<int>> st;
//stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
}
4. queue
4.1 queue的介紹
1.隊(duì)列是一種容器適配器，專門用于在FIFO上下文(先進(jìn)先出)中操作，其中從容器一端插入元素，另一端提取元素。
2.隊(duì)列作為容器適配器實(shí)現(xiàn)，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來(lái)訪問(wèn)其元素。元素從隊(duì)尾入隊(duì)列，從隊(duì)頭出隊(duì)列。
3.底層容器可以是標(biāo)準(zhǔn)容器類模板之一，也可以是其他專門設(shè)計(jì)的容器類。該底層容器應(yīng)至少支持以下操作:
empty：檢測(cè)隊(duì)列是否為空
size：返回隊(duì)列中有效元素的個(gè)數(shù)
front：返回隊(duì)頭元素的引用
back：返回隊(duì)尾元素的引用
push_back：在隊(duì)列尾部入隊(duì)列
pop_front：在隊(duì)列頭部出隊(duì)列
4.標(biāo)準(zhǔn)容器類deque和list滿足了這些要求。默認(rèn)情況下，如果沒(méi)有為queue實(shí)例化指定容器類，則使用標(biāo)準(zhǔn)容器deque。
4.2 queue的使用
| 函數(shù)名稱 | 功能說(shuō)明 |
|---|---|
| queue() | 構(gòu)造空的隊(duì)列 |
| empty() | 檢測(cè)隊(duì)列是否為空 |
| size() | 返回隊(duì)列中有效元素的個(gè)數(shù) |
| front() | 返回隊(duì)頭元素的引用 |
| back() | 返回隊(duì)尾元素的引用 |
| push() | 在隊(duì)尾將元素val入隊(duì) |
| pop() | 將隊(duì)頭元素出隊(duì) |
void Test2()
{
//fiora::queue<int> q;
//fiora::queue<int, list<int>> q;
//fiora::queue<int, vector<int>> q;錯(cuò)誤，vector不支持頭刪
queue<int> q;
//queue<int, list<int>> q;
//queue<int, vector<int>> q;錯(cuò)誤，vector不支持頭刪
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
}
4.3 queue模擬實(shí)現(xiàn)
namespace fiora
{
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
T& back()
{
return _con.back();
}
T& front()
{
return _con.front();
}
const T& back() const
{
return _con.back();
}
const T& front() const
{
return _con.front();
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
private:
Container _con;
};
}
測(cè)試：
void Test2()
{
fiora::queue<int> q;
fiora::queue<int, list<int>> q1;
//fiora::queue<int, vector<int>> q;錯(cuò)誤，vector不支持頭刪
//queue<int> q;
//queue<int, list<int>> q;
//queue<int, vector<int>> q;錯(cuò)誤，vector不支持頭刪
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
}
5. priority_queue（優(yōu)先隊(duì)列）
5.1 優(yōu)先隊(duì)列的介紹
優(yōu)先級(jí)隊(duì)列默認(rèn)使用vector作為其底層存儲(chǔ)數(shù)據(jù)的容器，在vector上又使用了堆算法將vector中元素構(gòu)造成堆的結(jié)構(gòu)，因此priority_queue就是堆，所有需要用到堆的位置，都可以考慮使用priority_queue。注意：默認(rèn)情況下priority_queue是大堆。
1.優(yōu)先隊(duì)列是一種容器適配器，根據(jù)嚴(yán)格的弱排序標(biāo)準(zhǔn)，它的第一個(gè)元素總是它所包含的元素中最大的。
2.此上下文類似于堆，在堆中可以隨時(shí)插入元素，并且只能檢索最大堆元素(優(yōu)先隊(duì)列中位于頂部的元素)。
3.優(yōu)先隊(duì)列被實(shí)現(xiàn)為容器適配器，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來(lái)訪問(wèn)其元素。元素從特定容器的“尾部”彈出，其稱為優(yōu)先隊(duì)列的頂部。
4.底層容器可以是任何標(biāo)準(zhǔn)容器類模板，也可以是其他特定設(shè)計(jì)的容器類。容器應(yīng)該可以通過(guò)隨機(jī)訪問(wèn)迭代器訪問(wèn)，并支持以下操作：
empty()：檢測(cè)容器是否為空
size()：返回容器中有效元素個(gè)數(shù)
front()：返回容器中第一個(gè)元素的引用
push_back()：在容器尾部插入元素
pop_back()：刪除容器尾部元素
5.標(biāo)準(zhǔn)容器類vector和deque滿足這些需求。默認(rèn)情況下，如果沒(méi)有為特定的priority_queue類實(shí)例化指定容器類，則使用vector。
6.需要支持隨機(jī)訪問(wèn)迭代器，以便始終在內(nèi)部保持堆結(jié)構(gòu)。容器適配器通過(guò)在需要時(shí)自動(dòng)調(diào)用算法函數(shù)make_heap、push_heap和pop_heap來(lái)自動(dòng)完成此操作。
5.2 優(yōu)先隊(duì)列的使用
| 函數(shù)名稱 | 功能說(shuō)明 |
|---|---|
| priority_queue()/priority_queue(first,last) | 構(gòu)造空的優(yōu)先隊(duì)列 |
| empty() | 檢測(cè)優(yōu)先隊(duì)列是否為空 |
| top() | 返回優(yōu)先級(jí)隊(duì)列中最大(最小元素)，即堆頂元素 |
| push() | 在優(yōu)先級(jí)隊(duì)列中插入元素val |
| pop() | 刪除優(yōu)先級(jí)隊(duì)列中最大(最小)元素，即堆頂元素 |
void Test3()
{
priority_queue<int> pq;
//fiora::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(2);
pq.push(5);
pq.push(1);
pq.push(4);
pq.push(0);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
void Test4()
{
int a[] = { 5,4,6,9,1,2,3,0,8,7 };
//fiora::priority_queue<int> heap(a, a + sizeof(a) / sizeof(int));
//fiora::priority_queue<int> heap(a, a + sizeof(a) / sizeof(int));
//fiora::priority_queue<int, vector<int>, greater<int>> heap(a, a + sizeof(a) / sizeof(int));
priority_queue<int, vector<int>, greater<int>> heap(a, a + sizeof(a) / sizeof(int));
while (!heap.empty())
{
cout << heap.top() << " ";
heap.pop();
}
cout << endl;
}
5.3 優(yōu)先隊(duì)列模擬實(shí)現(xiàn)
namespace fiora
{
//大堆
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
priority_queue()
{}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
_con.push_back(*first);
first++;
}
//建堆
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
adjust_down(i);
}
}
void adjust_up(size_t child)
{
Compare com;
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjust_down(size_t parent)
{
Compare com;
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
{
child++;
}
if (com(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
const T& top()
{
return _con[0];
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
private:
Container _con;
};
}
測(cè)試：
void Test3()
{
//priority_queue<int> pq;
fiora::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(2);
pq.push(5);
pq.push(1);
pq.push(4);
pq.push(0);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
int a[] = { 5,4,6,9,1,2,3,0,8,7 };
//fiora::priority_queue<int> heap(a, a + sizeof(a) / sizeof(int));
fiora::priority_queue<int> heap1(a, a + sizeof(a) / sizeof(int));
fiora::priority_queue<int, vector<int>, greater<int>> heap(a, a + sizeof(a) / sizeof(int));
//priority_queue<int, vector<int>, greater<int>> heap(a, a + sizeof(a) / sizeof(int));
while (!heap.empty())
{
cout << heap.top() << " ";
heap.pop();
}
cout << endl;
}
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-479364.html
6. 結(jié)尾
關(guān)于棧和隊(duì)列的學(xué)習(xí)我們就告一段落了，棧和隊(duì)列和之前學(xué)習(xí)的容器一樣，使用方法都非常簡(jiǎn)單，最重要的是要能夠理解它們的底層原理，以便靈活使用。
最后，感謝各位大佬的耐心閱讀和支持，覺(jué)得本篇文章寫的不錯(cuò)的朋友可以三連關(guān)注支持一波，如果有什么問(wèn)題或者本文有錯(cuò)誤的地方大家可以私信我，也可以在評(píng)論區(qū)留言討論，再次感謝各位。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-479364.html
到了這里，關(guān)于【C++】——棧和隊(duì)列（stack、queue）及優(yōu)先隊(duì)列（priority_queue）的介紹和模擬實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
