C++stack與queue模擬實作
- 前言
- stack堆疊
- 配接器
- stack的成員函式
- queue佇列
- queue類
- 總結
前言
xxxx無論是當初在學校最先學習C語言版的資料結構，還是現在學習STL，發現大家（包括我）都喜歡將stack（堆疊）和queue（佇列）放在一起，可能是FILO和FIFO兩種資料存盤方式過于相近，更能深入人心，因此兩者經常會被放在一起，但是STL我把他們放在一起更是有原因，因為這兩種容器在模擬實作的時候，都會使用到“配接器”，這個在后面我再具體說明，
stack堆疊
xxxx堆疊的基本知識相信大家都已經了解，在此我就不再贅述，堆疊的邏輯結構如圖
現在我們就要用C++進行實作，我們當初用C語言實作堆疊的時候，最多的情況都是使用的陣列來模擬堆疊，陣列的頭代表陣列的堆疊底；陣列的尾代表堆疊頂，由于堆疊對資料的push、pop都是在堆疊頂操作，所以使用陣列就能在時間復雜度為O(1)的情況下完成操作，十分高效，
xxxx這里有一個很重要的事情，就是C語言中，我們用陣列來模擬堆疊，那C++呢？？陣列的結構特點非常適合來作為堆疊，所以我們能否仍然使用陣列（vector）來作為堆疊的基礎資料結構從而實作堆疊呢？
xxxx答案是肯定的，我們仍然需要使用陣列（不是說只能使用陣列，只不過陣列更普遍，并且STL中的stack就是使用vector來實作的）但是我們知道，堆疊還有鏈堆疊，或者某些特殊要求我們不能使用vector，而是其他的容器更適合當前的操作情況，這時候，為了代碼的通用性，避免代碼冗余，為了面對不同的需要，我們不用每次都要寫一份邏輯相同而使用的容器不同的stack，我們就要引入**“配接器”**的概念，
配接器
提前宣告：我在這里講的配接器，只是配接器的一小部分，對于模擬實作stack和queue所需要的部分，
xxxx什么是配接器？大家現實生活中應該都有許多型別的配接器，比如：家用220V電壓是從高壓輸電線通過電壓轉變過來的、兩孔三孔插頭之間轉化……功能類似于下圖這種，
xxxx簡單來說，就是一種轉變，而在這里是什么的轉變呢？答案是：容器的轉變，
xxxx現在我們的目的是使用各種轉變成stack，我們就需要模板，類模板詳解請點這里，下面我們直接看一下如何使用模板成為配接器，
template<class T, class Container = vector<T>>
class stack
{
private:
Container _con;
};
以上就是它的基本格式，我們最簡單的理解就是，我們將vector進行一次封裝，通過成員函式對他的行為進行約束，讓他變成具有stack屬性的一種新容器，這種容器我們成為stack，
注：STL中使用的是deque，我們使用vector影響不大，使用vector與C語言有很好的聯系，方便理解，否則有些同學剛學到這里，還不知道deque是什么，會影響學習
stack的成員函式
namespace zzk
{
template<class T, class Container = std::deque<T>>
class stack
{
public:
//默認成員函式都不用寫，就直接使用deque的就行
void push(const T x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
T top() const
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}
xxxx我們可以很容易發現，完全就是對vector成員函式進行一次封裝，因為操作邏輯完全一樣，所以只需要對vector的行為封裝成stack即可完成，
queue佇列
xxxx我們在C語言中的佇列可以用鏈表或者陣列，
在C++中，我們仍然要使用配接器這種方式，對某種容器進行封裝，形成佇列，由于vector不支持頭刪，所以我們要使用deque或者鏈表，STL中默認使用的是deque，
經過stack的學習，queue應該比較容易理解，我們直接上代碼！！
queue類
namespace zzk
{
template<class T, class Container = std::deque<int>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
T front()
{
return _con.front();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}
xxxx還是對已有容器的封裝，由于邏輯類似，因此我們直接復用原容器的介面即可，
總結
xxxx堆疊和佇列都使用了“配接器”，在這里，配接器的作用就是對現有容器的一種封裝，由于操作邏輯相同，因此只需要對介面進行一次封裝即可，對于邏輯不相同的，如用vector實作優先佇列priority_queue，由于邏輯不相同，就需要加以其他代碼，使符合priority_queue的功能特點，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/299383.html
標籤：其他
上一篇：2021-09-11
下一篇：【演算法訓練營】(day5)