目錄

一、Stack（棧）

1.1 Stack的介紹

1.2 Stack的使用

1.3 Stack的模擬實現

二、Queue（隊列）

2.1 Queue的介紹

2.2 Queue的使用

2.3 Queue的模擬實現

三、容器適配器

3.1 什么是適配器

3.2 為什么選擇deque作為stack和queue的底層默認容器

?編輯

總結

---

?

專欄：C++學習筆記?

上一卷：C++—list容器

在C++中，stack和queue是兩種非常重要的數據結構，廣泛應用于各種算法和系統中。本文將詳細介紹這兩種數據結構的基本概念、使用方法及其底層實現，并結合代碼示例和運行結果進行詳細講解。

一、Stack（棧）

1.1 Stack的介紹

stack（棧）是一種容器適配器，專門用于后進先出（LIFO, Last In First Out）的操作環境中。棧的元素插入和刪除操作只能在容器的一端進行，即棧頂。

棧的底層容器可以是任何標準的容器類模板或一些其他特定的容器類，這些容器類應支持以下操作：

• empty(): 判空操作
• back(): 獲取尾部元素操作
• push_back(): 尾部插入元素操作
• pop_back(): 尾部刪除元素操作

標準容器vector、deque、list均符合這些需求，默認情況下，如果沒有為stack指定特定的底層容器，默認情況下使用deque。

小李的理解：
棧就像是一疊盤子，你只能從頂部添加或移除盤子。這就意味著最后添加的盤子最先被移除（后進先出）。在C++中，棧的底層可以用多種容器實現，但一般默認用deque，因為它支持高效的尾部操作。

1.2 Stack的使用

stack的常用操作包括：

• stack(): 構造空的棧
• empty(): 檢測stack是否為空
• size(): 返回stack中元素的個數
• top(): 返回棧頂元素的引用
• push(val): 將元素val壓入stack中
• pop(): 將stack中尾部的元素彈出

示例代碼：

#include <stack>
#include <iostream>int main() {std::stack<int> s;s.push(1);s.push(2);s.push(3);std::cout << "Stack top: " << s.top() << std::endl; // 輸出3s.pop();std::cout << "Stack top after pop: " << s.top() << std::endl; // 輸出2return 0;
}

首先我們壓入了三個元素1, 2, 3，棧頂元素是3。然后我們彈出了棧頂元素，棧頂變成了2。

小李的理解：
就像把三個盤子按順序疊起來（1在最底下，3在最上面）。當我們移走最上面的盤子時，下面的盤子就成了新的頂部。

1.3 Stack的模擬實現

從棧的接口中可以看出，棧實際是一種特殊的vector，因此使用vector完全可以模擬實現stack。

示例代碼：

#include <vector>
#include <iostream>namespace bite {template<class T>class stack {public:stack() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_back(); }T& top() { return _c.back(); }const T& top() const { return _c.back(); }size_t size() const { return _c.size(); }bool empty() const { return _c.empty(); }private:std::vector<T> _c;};
}int main() {bite::stack<int> s;s.push(1);s.push(2);s.push(3);std::cout << "Custom stack top: " << s.top() << std::endl; // 輸出3s.pop();std::cout << "Custom stack top after pop: " << s.top() << std::endl; // 輸出2return 0;
}

這表明我們的自定義stack實現與標準庫中的行為一致。

小李的理解：
我們自己實現了一個簡單的棧，用vector來存儲元素。每次添加元素時，將它們推到vector的尾部；每次移除元素時，從vector的尾部移除。這和我們平時用的棧行為完全一樣。

二、Queue（隊列）

2.1 Queue的介紹

queue（隊列）是一種容器適配器，專門用于先進先出（FIFO, First In First Out）的操作環境中。隊列的元素插入操作在容器的一端進行，即隊尾，而提取操作在容器的另一端進行，即隊頭。

隊列的底層容器可以是標準容器類模板之一，也可以是其他專門設計的容器類。這些容器類應支持以下操作：

• empty(): 檢測隊列是否為空
• size(): 返回隊列中有效元素的個數
• front(): 返回隊頭元素的引用
• back(): 返回隊尾元素的引用
• push_back(): 在隊列尾部插入元素
• pop_front(): 在隊列頭部刪除元素

標準容器deque和list滿足這些要求。默認情況下，如果沒有為queue指定特定的底層容器，則使用deque。

小李的理解：
隊列就像排隊買票，最早來的人最先買到票（先進先出）。在C++中，隊列的底層可以用多種容器實現，但一般默認用deque，因為它支持高效的頭尾操作。

2.2 Queue的使用

queue的常用操作包括：

• queue(): 構造空的隊列
• empty(): 檢測隊列是否為空
• size(): 返回隊列中有效元素的個數
• front(): 返回隊頭元素的引用
• back(): 返回隊尾元素的引用
• push(val): 在隊尾將元素val入隊列
• pop(): 將隊頭元素出隊列

示例代碼：

#include <queue>
#include <iostream>int main() {std::queue<int> q;q.push(1);q.push(2);q.push(3);std::cout << "Queue front: " << q.front() << std::endl; // 輸出1q.pop();std::cout << "Queue front after pop: " << q.front() << std::endl; // 輸出2return 0;
}

首先我們壓入了三個元素1, 2, 3，隊頭元素是1。然后我們彈出了隊頭元素，隊頭變成了2。

小李的理解：
就像排隊買票，第一個人買了票離開，第二個人就成了最前面的人。

2.3 Queue的模擬實現

因為queue的接口中存在頭刪和尾插，因此使用vector來封裝效率太低，故可以借助list來模擬實現queue。

示例代碼：

#include <list>
#include <iostream>namespace bite {template<class T>class queue {public:queue() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_front(); }T& back() { return _c.back(); }const T& back() const { return _c.back(); }T& front() { return _c.front(); }const T& front() const { return _c.front(); }size_t size() const { return _c.size(); }bool empty() const { return _c.empty(); }private:std::list<T> _c;};
}int main() {bite::queue<int> q;q.push(1);q.push(2);q.push(3);std::cout << "Custom queue front: " << q.front() << std::endl; // 輸出1q.pop();std::cout << "Custom queue front after pop: " << q.front() << std::endl; // 輸出2return 0;
}

?

這表明我們的自定義queue實現與標準庫中的行為一致。

小李的理解：
我們自己實現了一個簡單的隊列，用list來存儲元素。每次添加元素時，將它們推到list的尾部；每次移除元素時，從list的頭部移除。這和我們平時用的隊列行為完全一樣。

三、容器適配器

3.1 什么是適配器

適配器是一種設計模式，該模式是將一個類的接口轉換成客戶希望的另外一個接口。在STL中，stack和queue就是通過適配器模式將deque、vector等容器類的接口轉換成特定的LIFO或FIFO操作。

3.2 為什么選擇deque作為stack和queue的底層默認容器

雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配器，這是因為stack和queue只是對其他容器的接口進行了包裝，STL中stack和queue默認使用deque。主要原因如下：

1. stack和queue不需要遍歷（因此stack和queue沒有迭代器），只需要在固定的一端或者兩端進行操作。
2. 在stack中元素增長時，deque比vector的效率高（擴容時不需要搬移大量數據）；queue中的元素增長時，deque不僅效率高，而且內存使用率高。

結合了deque的優點，而完美地避開了其缺陷，使其成為stack和queue的理想底層容器。

總結

C++中的stack和queue通過容器適配器實現，分別用于LIFO和FIFO操作。stack和queue的底層容器默認使用deque，但也可以根據需求選擇其他標準容器。理解并靈活運用這些數據結構，對于高效編寫算法和處理復雜數據具有重要意義。