?文章來源地址http://www.zghlxwxcb.cn/news/detail-789928.html
?
文章目錄
- 前言
- 一.棧和隊列的模擬實現(xiàn)
- 二.優(yōu)先級隊列
- 總結(jié)
?
前言
棧的介紹和使用：
?
一、棧和隊列的模擬實現(xiàn)
容器適配器：
前面我們說過stack和queue是一種容器適配器，同樣也是作為容器適配器被實現(xiàn)的，所以我們可以直接使用一個公共的容器來當(dāng)stack的適配器，適配器是用來轉(zhuǎn)換的，將已有的東西進行轉(zhuǎn)換，比如將vector當(dāng)我們棧的容器實現(xiàn)棧的功能，我們先看一下庫中如何描述棧的：
?可以看到庫中是用的deque來當(dāng)stack的容器，并且stack的接口非常簡單，所以我們現(xiàn)在就開始實現(xiàn)：
#include <vector>
#include <iostream>
using namespace std;
namespace sxy
{
template<class T,class Container = vector<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();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
void test3()
{
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
}
}?因為我們要使用vector做適配器所以包含了vector的頭文件，然后我們所有的函數(shù)直接使用容器的公共接口即可，比如vector的push_back等等。在模板中我們用了vector的缺省容器，如果你不想用vector，你也可以使用list作為stack的容器，只需要：stack<int,list<int>>?我們的第一步是創(chuàng)建一個容器的對象_con.
void push(const T& x)
{
_con.push_back(x);
}?對于push我們直接使用容器的尾插即可。
void pop()
{
_con.pop_back();
}?對于pop直接使用尾刪即可，因為棧本來就是后進先出的。
T& top()
{
return _con.back();
}
const T& top() const
{
return _con.back();
}?top是返回棧頂元素，容器中的back（）接口返回的就是棧頂元素。
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}?size()和empty與上述同理，都使用容器的公共接口就能解決。
隊列的模擬實現(xiàn)
我們先看一下庫中的實現(xiàn)，同樣也是用deque作為queue的容器。
?在這里我們要說明一下，由于vector的頭刪效率極低，所以vector是不能作為queue的容器的。這里可以用list作為queue的容器，也可以用deque作為queue的容器。第一步是創(chuàng)建一個容器的對象_con.
#include <deque>
#include <iostream>
using namespace std;
namespace sxy
{
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& front()
{
return _con.front();
}
const T& front() const
{
return _con.front();
}
T& back()
{
return _con.back();
}
const T& back() const
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
void test2()
{
queue<int> qe;
qe.push(1);
qe.push(2);
qe.push(3);
qe.push(4);
while (!qe.empty())
{
cout << qe.front() << " ";
qe.pop();
}
}
}?隊列的實現(xiàn)與棧不同的是隊尾插入隊頭出，所以對于pop接口和top接口而言是不一樣的：
void pop()
{
_con.pop_front();
}?隊列要頭刪所以用頭刪的接口。
T& front()
{
return _con.front();
}
const T& front() const
{
return _con.front();
}
T& back()
{
return _con.back();
}
const T& back() const
{
return _con.back();
}?這里提供了隊頭元素的返回和隊尾元素的返回，因為庫中也是實現(xiàn)的。
?這樣棧和隊列的模擬實現(xiàn)就完成了，對于棧和隊列我們只需要明白適配器的使用，只要學(xué)到了這個后面很多的實現(xiàn)都變簡單了。
二、優(yōu)先級隊列
什么是優(yōu)先級隊列呢？
下面我們來看看庫中的優(yōu)先級隊列：
?我們可以看到優(yōu)先級隊列的實現(xiàn)除了容器外還多了一個Compare,這個是什么呢？這個其實是一個仿函數(shù)，這里的仿函數(shù)是來解決優(yōu)先級隊列是小的優(yōu)先級高還是大的優(yōu)先級高，我們默認是大的優(yōu)先級高也就是大堆。
#include <deque>
using namespace std;
#include <iostream>
namespace sxy
{
template<class T>
struct less
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
struct greater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
template<class T,class Container = deque<T>,class Compare = less<T>>
class priority_queue
{
public:
void adjust_up(int child)
{
Compare com;
size_t parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[parent] < _con[child])
if (com(_con[parent],_con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjust_down(int parent)
{
Compare com;
size_t child = 2 * parent + 1;
while (child < _con.size())
{
//if ((child + 1) < _con.size() && _con[child] < _con[child + 1])
if ((child+1)<_con.size()&&com(_con[child],_con[child+1]))
{
++child;
}
//if (_con[parent] < _con[child])
if (com(_con[parent],_con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
T& top()
{
return _con.front();
}
const T& top() const
{
return _con.front();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
void test1()
{
priority_queue<int> pq;
pq.push(1);
pq.push(16);
pq.push(14);
pq.push(19);
pq.push(17);
pq.push(12);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
}
}第一步是創(chuàng)建一個容器的對象_con.?
?我們一個函數(shù)一個函數(shù)依次來分析：
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}?首先是push，由于優(yōu)先級隊列本質(zhì)還是一個隊列，所以遵循先進先出的原則。插入的時候在隊尾插入即可，這個時候我們不能結(jié)束，因為要排優(yōu)先級，所以我們要將最后插入的這個數(shù)依次向前調(diào)整。聽到這里是不是很熟悉呢？沒錯！這其實就是我們之前講過的堆，而這個adjust_up函數(shù)也和我們當(dāng)時實現(xiàn)的向上調(diào)整一模一樣，所以在這里我們就不在詳細的介紹如何調(diào)整了，具體的可以去看我的那篇關(guān)于堆的文章。
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}?對于一個已經(jīng)排好序的隊列我們是不可以直接出數(shù)據(jù)的，為了保證數(shù)據(jù)的有序性我們先講第一個元素和最后一個元素交換，這樣我們就把要刪除的第一個隊頂元素移到了隊尾，然后直接尾刪就刪掉了原先的隊頭元素，剛剛我們將最后一個元素換到了對頭，所以我們要讓對頭這個數(shù)據(jù)依次向下調(diào)整來保持有序性。
T& top()
{
return _con.front();
}
const T& top() const
{
return _con.front();
}?由于優(yōu)先級隊列只提供對頭元素的返回所以我們只用容器的front接口即可。
想要看明白向上調(diào)整接口需要先介紹一下仿函數(shù)：
template<class T>
struct less
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
struct greater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};?我們可以看到仿函數(shù)的實現(xiàn)其實就是創(chuàng)建一個類然后里面封裝一個()的運算符重載，比如我們的less小于，對于一個數(shù)是否小于另一個數(shù)我們可以直接寫為：Compare com com(x,y),這時候肯定會有人說有什么用呢，用其他方式也能替代。如果這樣想那就錯了，仿函數(shù)作為STL的六大接口之一又怎么會沒用呢？下面我們就能見識到仿函數(shù)的重要性：
void adjust_up(int child)
{
Compare com;
size_t parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[parent] < _con[child])
if (com(_con[parent],_con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}?對于向上調(diào)整函數(shù)的實現(xiàn)我們先創(chuàng)建一個仿函數(shù)對象，然后計算孩子節(jié)點的父節(jié)點，當(dāng)孩子節(jié)點大于0時進入循環(huán)，在這里我們是不用判斷child>=0的，因為等于0這個孩子就變成所有節(jié)點的祖先了還哪有父節(jié)點呢？然后我們直接用仿函數(shù)判斷如果父親小于孩子（因為默認是大堆）節(jié)點就進行向上調(diào)整，向上調(diào)整就是將父節(jié)點和孩子節(jié)點交換，然后讓孩子節(jié)點到以前父節(jié)點的位置上，在重新算父節(jié)點這樣就能依次向上連續(xù)調(diào)整，一旦發(fā)現(xiàn)父節(jié)點大于孩子節(jié)點滿足大堆的條件我們就break即可。在這里如果沒有這個仿函數(shù)，我們該如何隨意控制優(yōu)先級隊列是大堆還是小堆呢？所以仿函數(shù)真的很重要。
void adjust_down(int parent)
{
Compare com;
size_t child = 2 * parent + 1;
while (child < _con.size())
{
//if ((child + 1) < _con.size() && _con[child] < _con[child + 1])
if ((child+1)<_con.size()&&com(_con[child],_con[child+1]))
{
++child;
}
//if (_con[parent] < _con[child])
if (com(_con[parent],_con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}?向下調(diào)整函數(shù)是將父節(jié)點依次和左右孩子節(jié)點相比較，默認是大堆，如果父節(jié)點小于孩子節(jié)點就交換，由于向下調(diào)整的時候我們需要看孩子節(jié)點哪個更大，父節(jié)點與大的那個孩子節(jié)點交換，所以我們先默認孩子節(jié)點是左孩子，由于孩子節(jié)點是依次向下調(diào)整的，所以循環(huán)條件為孩子小于size()就進入循環(huán)，進入循環(huán)后我們首先判斷右孩子是否存在，因為一個完全二叉樹是有可能沒有右孩子的。如果右孩子存在并且左孩子小于右孩子我們就讓孩子節(jié)點++變成右孩子。當(dāng)父節(jié)點小于孩子節(jié)點的時候我們就進行調(diào)整，先交換父節(jié)點和孩子節(jié)點，然后讓父節(jié)點到剛剛孩子節(jié)點的位置上去，再重新計算孩子節(jié)點。當(dāng)父節(jié)點不小于孩子節(jié)點時就不需要調(diào)整直接break即可。
下面我們驗證一下我們寫的優(yōu)先級隊列：
?因為默認是大堆所以我們看到確實排序完成了，下面我們換個適配器驗證一下小堆。
?下面我們簡單的介紹一下什么是deque：
?deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實際deque類似于一個動態(tài)的二維數(shù)組，其底層結(jié)構(gòu)如下圖所示：
那deque是如何借助其迭代器維護其假想連續(xù)的結(jié)構(gòu)呢？看下圖：
我們可以看到deque的實現(xiàn)非常的復(fù)雜，雖然插入刪除比vector方便了不少并且對于空間的擴容也優(yōu)于vector，但卻沒有極致的優(yōu)點，所以只能淪為容器適配器。
?
總結(jié)
本節(jié)相對比較簡單，因為很多都是我們之前學(xué)過的知識，本篇文章的重點在于了解并且會熟悉的使用適配器，我們會發(fā)現(xiàn)有了適配器是非常方便的，之前我們用C語言寫棧和隊列的時候隨便就一兩百行代碼，而用c++實現(xiàn)棧和隊列不到60行就能搞定。deque的出現(xiàn)本來是為了替代vector和list的，結(jié)果卻成為了stack和queue的容器適配器，這是因為deque沒有一個極致的優(yōu)點，不像vector那樣可以隨意訪問元素，也不能像list那樣任意位置插入刪除的效率高。下一篇要講的內(nèi)容是反向迭代器的實現(xiàn)與適配（干貨滿滿哦~）。文章來源：http://www.zghlxwxcb.cn/news/detail-789928.html
?
到了這里，關(guān)于【c++】:“無敵的適配器來咯“棧和隊列模擬實現(xiàn)以及優(yōu)先級隊列的模擬實現(xiàn)。的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C++] STL_priority_queue(優(yōu)先級隊列) 的使用及底層的模擬實現(xiàn)，容器適配器，deque的原理介紹](https://imgs.yssmx.com/Uploads/2024/02/761687-1.png)
