C++学习第二十六课：自适应容器——栈和队列

在C++标准模板库（STL）中，自适应容器提供了一种使用标准容器作为底层数据存储的抽象。std::stack和std::queue是两种常用的自适应容器，它们分别提供了栈和队列这两种线性数据结构的后端实现。本课将详细介绍这两种自适应容器的使用方法，并通过示例代码展示其应用。

1. 自适应容器概述

自适应容器是STL提供的容器适配器，它们定义了一组操作，这些操作限制了底层容器的某些能力。

2. std::stack的使用

std::stack是一个后进先出（LIFO）的容器，只允许在容器的一端进行添加和移除操作。

示例代码

#include <stack>
#include <vector>int main() {std::stack<int> s;s.push(1); // 添加元素到栈顶s.push(2);s.push(3);while (!s.empty()) {std::cout << ' ' << s.top(); // 访问栈顶元素s.pop(); // 移除栈顶元素}return 0;
}

3. std::queue的使用

std::queue是一个先进先出（FIFO）的容器，只允许在容器的两端进行添加和移除操作。

示例代码

#include <queue>
#include <vector>int main() {std::queue<int> q;q.push(1);q.push(2);q.push(3);while (!q.empty()) {std::cout << ' ' << q.front(); // 访问队首元素q.pop(); // 移除队首元素}return 0;
}

4. std::stack和std::queue的底层实现

通常，std::stack和std::queue使用std::vector、std::deque或std::list作为底层容器。

5. 自适应容器的迭代器

与标准容器不同，自适应容器只提供了有限的迭代器功能。

示例代码

// std::stack不支持迭代器
// std::queue只支持输入迭代器

6. 自适应容器的模板参数

std::stack和std::queue可以指定底层容器类型作为模板参数。

示例代码

std::stack<int, std::list<int>> stack; // 使用std::list作为底层容器

除了栈（std::stack）和队列（std::queue）之外，还有其他几个重要的概念和容器值得关注。

7. 优先队列 (`std::priority_queue)

优先队列是一种特殊类型的队列，其中每个元素都有特定的优先级。std::priority_queue通常基于堆数据结构实现。

示例代码

#include <queue>
#include <vector>int main() {std::priority_queue<int> pq;pq.push(30);pq.push(10);pq.push(20);while (!pq.empty()) {std::cout << pq.top() << std::endl; // 输出最高优先级的元素pq.pop();}return 0;
}

8. 双端队列 (`std::deque)

双端队列（std::deque）是一个允许在两端快速添加和移除元素的容器。

示例代码

#include <deque>
#include <iostream>int main() {std::deque<int> dq;dq.push_back(1);dq.push_front(0);dq.push_back(2);for (int num : dq) {std::cout << num << " ";}return 0;
}

9. 集合 (std::set) 和多重集合 (std::multiset)

集合是不允许重复元素的容器，而多重集合允许有重复的元素。

示例代码

#include <set>int main() {std::set<int> s;s.insert(1);s.insert(2);s.insert(1); // 重复元素将被忽略for (int num : s) {std::cout << num << " ";}return 0;
}

10. 映射 (std::map) 和多重映射 (std::multimap)

映射是存储键值对的容器，其中每个键都是唯一的。多重映射允许有重复的键。

示例代码

#include <map>int main() {std::map<int, std::string> m;m[1] = "one";m[2] = "two";m[1] = "uno"; // 更新键为1的元素for (const auto& pair : m) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}

11. 散列容器 (std::unordered_set, std::unordered_map)

散列容器使用哈希表作为底层数据结构，提供平均时间复杂度为O(1)的查找、插入和删除操作。

示例代码

#include <unordered_map>int main() {std::unordered_map<std::string, int> um;um["one"] = 1;um["two"] = 2;for (const auto& pair : um) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}

12. 算法的使用

STL算法与自适应容器和标准容器的结合使用，进行数据操作。

示例代码

#include <algorithm>
#include <vector>int main() {std::vector<int> v = {1, 2, 3, 4, 5};std::sort(v.begin(), v.end()); // 排序std::reverse(v.begin(), v.end()); // 反转int sum = std::accumulate(v.begin(), v.end(), 0); // 求和std::cout << "Sum: " << sum << std::endl;return 0;
}

13. 迭代器的使用

迭代器是STL中非常重要的概念，用于访问容器中的元素。

示例代码

#include <iostream>
#include <vector>int main() {std::vector<int> v = {1, 2, 3};for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {std::cout << *it << " ";}return 0;
}

结语

通过本课的学习，你深入了解了STL中的自适应容器——std::stack和std::queue，包括它们的使用方式、底层实现、模板参数、迭代器功能、与标准容器的比较、实际应用、线程安全性和性能考量。

自适应容器是C++中实现特定数据结构的强大工具，它们在需要栈和队列操作的场景下非常有用。掌握自适应容器的使用对于编写高效、可维护的C++程序至关重要。