跳转至

容器適配器

棧

STL 棧(std::stack) 是一種後進先出 (Last In, First Out) 的容器適配器，僅支持查詢或刪除最後一個加入的元素（棧頂元素），不支持隨機訪問，且為了保證數據的嚴格有序性，不支持迭代器。

頭文件

1
#include <stack>

定義

1
2
3
std::stack<TypeName> s;  // 使用默認底層容器 deque，數據類型為 TypeName
std::stack<TypeName, Container> s;  // 使用 Container 作為底層容器
std::stack<TypeName> s2(s1);        // 將 s1 複製一份用於構造 s2

成員函數

以下所有函數均為常數複雜度

  • top() 訪問棧頂元素（如果棧為空，此處會出錯）
  • push(x) 向棧中插入元素 x
  • pop() 刪除棧頂元素
  • size() 查詢容器中的元素數量
  • empty() 詢問容器是否為空

簡單示例

1
2
3
4
5
6
7
8
9
std::stack<int> s1;
s1.push(2);
s1.push(1);
std::stack<int> s2(s1);
s1.pop();
std::cout << s1.size() << " " << s2.size() << std::endl;  // 1 2
std::cout << s1.top() << " " << s2.top() << std::endl;    // 2 1
s1.pop();
std::cout << s1.empty() << " " << s2.empty() << std::endl;  // 1 0

隊列

STL 隊列(std::queue) 是一種先進先出 (First In, First Out) 的容器適配器，僅支持查詢或刪除第一個加入的元素（隊首元素），不支持隨機訪問，且為了保證數據的嚴格有序性，不支持迭代器。

頭文件

1
#include <queue>

定義

1
2
3
4
std::queue<TypeName> q;  // 使用默認底層容器 deque，數據類型為 TypeName
std::queue<TypeName, Container> q;  // 使用 Container 作為底層容器

std::queue<TypeName> q2(q1);  // 將 s1 複製一份用於構造 q2

成員函數

以下所有函數均為常數複雜度

  • front() 訪問隊首元素（如果隊列為空，此處會出錯）
  • push(x) 向隊列中插入元素 x
  • pop() 刪除隊首元素
  • size() 查詢容器中的元素數量
  • empty() 詢問容器是否為空

簡單示例

1
2
3
4
5
6
7
8
9
std::queue<int> q1;
q1.push(2);
q1.push(1);
std::queue<int> q2(q1);
q1.pop();
std::cout << q1.size() << " " << q2.size() << std::endl;    // 1 2
std::cout << q1.front() << " " << q2.front() << std::endl;  // 1 2
q1.pop();
std::cout << q1.empty() << " " << q2.empty() << std::endl;  // 1 0

優先隊列

優先隊列 std::priority_queue 是一種 堆，一般為 二叉堆。

頭文件

1
#include <queue>

定義

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
std::priority_queue<TypeName> q;             // 數據類型為 TypeName
std::priority_queue<TypeName, Container> q;  // 使用 Container 作為底層容器
std::priority_queue<TypeName, Container, Compare> q;
// 使用 Container 作為底層容器，使用 Compare 作為比較類型

// 默認使用底層容器 vector
// 比較類型 less<TypeName>（此時為它的 top() 返回為最大值）
// 若希望 top() 返回最小值，可令比較類型為 greater<TypeName>
// 注意：不可跳過 Container 直接傳入 Compare

// 從 C++11 開始，如果使用 lambda 函數自定義 Compare
// 則需要將其作為構造函數的參數代入，如：
auto cmp = [](const std::pair<int, int> &l, const std::pair<int, int> &r) {
  return l.second < r.second;
};
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >,
                    decltype(cmp)>
    pq(cmp);

成員函數

以下所有函數均為常數複雜度

  • top() 訪問堆頂元素（此時優先隊列不能為空）
  • empty() 詢問容器是否為空
  • size() 查詢容器中的元素數量

以下所有函數均為對數複雜度

  • push(x) 插入元素，並對底層容器排序
  • pop() 刪除堆頂元素（此時優先隊列不能為空）

簡單示例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
std::priority_queue<int> q1;
std::priority_queue<int, std::vector<int> > q2;
// C++11 後空格可省略
std::priority_queue<int, std::deque<int>, std::greater<int> > q3;
// q3 為小根堆
for (int i = 1; i <= 5; i++) q1.push(i);
// q1 中元素 :  [1, 2, 3, 4, 5]
std::cout << q1.top() << std::endl;
// 輸出結果 : 5
q1.pop();
// 堆中元素 : [1, 2, 3, 4]
std::cout << q1.size() << std::endl;
// 輸出結果 ：4
for (int i = 1; i <= 5; i++) q3.push(i);
// q3 中元素 :  [1, 2, 3, 4, 5]
std::cout << q3.top() << std::endl;
// 輸出結果 : 1
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Xeonacid, ksyx, Early0v0
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用