文章目錄
- 前言
- 一、stack的介紹和使用
- 1.1 stack的介紹
- 1.2 stack的使用
- 1.3 stack的模拟實作
- 二、queue的介紹和使用
- 2.1 queue的介紹
- 2.2 queue的使用
- 2.3 queue的模拟實作
- 三、容器擴充卡
- 4.1 什麼是擴充卡
- 4.3 deque的簡單介紹(了解)
- 四、為什麼選擇deque作為stack和queue的底層預設容器
前言
上次寫部落格距今天已有20天了，暑假的休息到今天也就結束了，相信很多朋友和我一樣雖然開學了，但還在家裡上網課中，然後今天我來給大家聊聊關于C++中的stack和queue的知識，還有關于deque的了解知識。
還有給大家一個建議，C++中的容器建議根據文檔來去學習，很多東西腦子是記不住的，附上C++的文檔如下
C++文檔
打開後建議進入舊的版本，比較容易找到我們需要的東西
在方框中搜尋即可
正文開始
一、stack的介紹和使用
1.1 stack的介紹
stack文檔介紹
1.stack是作為容器擴充卡被實作的，容器擴充卡即是對特定類封裝作為其底層的容器，并提供一組特定
的成員函數來通路其元素，将特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。
2.stack的底層容器可以是任何标準的容器類模闆或者一些其他特定的容器類
3. stack的底層容器可以是任何标準的容器類模闆或者一些其他特定的容器類
1.2 stack的使用
| 函數說明 | 接口說明 |
| stack() | 構造空的棧 |
| empty() | 檢測stack是否為空 |
| size() | 傳回stack中元素的個數 |
| top() | 傳回棧頂元素的引用 |
| push() | 将元素val壓入stack中 |
| pop() | 将stack中尾部的元素彈出 |
1.3 stack的模拟實作
從棧的接口中可以看出，棧實際是一種特殊的vector，是以使用vector完全可以模拟實作stack。
namespace hulu
{
//template<class T,class Container= vector<T>>
//template<class T, class Container = list<T>>
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();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
} 因為容器擴充卡中選用的是内置類型vector，是以不用對stack進行初始化和構造函數的實作，由編譯器幫你實作.
二、queue的介紹和使用
2.1 queue的介紹
queue的文檔介紹
- 隊列是一種容器擴充卡，專門用于先進先出中操作，其中從容器一端插入元素，另一端擷取元素。
-
隊列作為容器擴充卡實作，容器擴充卡即将特定容器類封裝作為其底層容器類，queue提供一組特定的
成員函數來通路其元素。元素從隊尾入隊列，從隊頭出隊列。
-
底層容器可以是标準容器類模闆之一，也可以是其他專門設計的容器類。該底層容器應至少支援以下操
作:
empty：檢測隊列是否為空
size：傳回隊列中有效元素的個數
front：傳回隊頭元素的引用
back：傳回隊尾元素的引用
push_back：在隊列尾部入隊列
pop_front：在隊列頭部出隊列
-
标準容器類deque和list滿足了這些要求。預設情況下，如果沒有為queue執行個體化指定容器類，則使用标
準容器deque。
2.2 queue的使用
| 函數聲明 | 接口說明 |
| queue() | 構造空的隊列 |
| empty() | 檢測隊列是否為空，是傳回true，否則傳回false |
| size() | 傳回隊列中有效元素的個數 |
| front() | 傳回隊頭元素的引用 |
| back() | 傳回隊尾元素的引用 |
| push() | 在隊尾将元素val入隊列 |
| pop() | 将隊頭元素出隊列 |
2.3 queue的模拟實作
因為queue的接口中存在頭删和尾插，是以使用vector來封裝效率太低，故可以借助list來模拟實作queue，
具體如下：
namespace hulu
{
//list
template<class T, class Container = list<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
T front()
{
return _con.front();
}
T back()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
} 三、容器擴充卡
4.1 什麼是擴充卡
擴充卡是一種設計模式(設計模式是一套被反複使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總
結)，該種模式是将一個類的接口轉換成客戶希望的另外一個接口。
我們先來看看庫裡對stack和queue容器擴充卡的實作是用什麼來完成的
可以看出庫裡對棧和隊列的實作利用到了deque，deque是一個雙端隊列
4.3 deque的簡單介紹(了解)
deque(雙端隊列)：是一種雙開口的"連續"空間的資料結構，雙開口的含義是：可以在頭尾兩端進行插入和
删除操作，且時間複雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間使用率比
較高。
但是他不是一個真正意義上連續的空間，而是由一小段一小段空間利用指針連接配接而成的一段空間，
實際上deque就類似于一個動态開辟的二維空間
雙端隊列底層是一段假象的連續空間，實際是分段連續的，為了維護其“整體連續”以及随機通路的假象，落
在了deque的疊代器身上，是以deque的疊代器設計就比較複雜，如下圖所示：
四、為什麼選擇deque作為stack和queue的底層預設容器
stack是一種後進先出的特殊線性資料結構，是以隻要具有push_back()和pop_back()操作的線性結構，都可
以作為stack的底層容器，比如vector和list都可以；queue是先進先出的特殊線性資料結構，隻要具有
push_back和pop_front操作的線性結構，都可以作為queue的底層容器，比如list。但是STL中對stack和
queue預設選擇deque作為其底層容器，主要是因為：
1.stack和queue不需要周遊，是以本身也就沒有疊代器，隻需要在容器的一端或者兩端操作數即可
2.stack和deque的元素增長中可能需要擴容，但是deque不需要，容量滿了，繼續開辟一小段空間就好
結合了deque的優點，而完美的避開了其缺陷。