C++算法
C++ STL 栈与队列详解：基础概念、应用及模拟实现
本文详细介绍了 C++ STL 中的栈（Stack）、队列（Queue）和优先队列（Priority Queue）。涵盖基本概念、常用操作、最小栈实现、基于 vector/list/deque 的模拟实现以及容器适配器原理。重点讲解了 deque 作为底层容器的优势及堆的实现逻辑，帮助读者深入理解数据结构在实际开发中的应用。
本文详细介绍了 C++ STL 中的栈（Stack）、队列（Queue）和优先队列（Priority Queue）。涵盖基本概念、常用操作、最小栈实现、基于 vector/list/deque 的模拟实现以及容器适配器原理。重点讲解了 deque 作为底层容器的优势及堆的实现逻辑，帮助读者深入理解数据结构在实际开发中的应用。
栈与队列是常见的数据结构，常被用于不同的算法场景。在本文中，我们将详细探讨栈与队列的基本概念、实际应用及其模拟实现。栈和队列在日常开发中的重要性不言而喻，通过对这两种数据结构的深入理解，将助你更加灵活地应对算法题目和工程开发。
栈 (Stack) 是一种 后进先出 (LIFO, Last In First Out) 的数据结构。这意味着栈中最后一个被插入的元素会第一个被移出。这种特性使得栈在实现某些算法时非常有用，例如函数调用栈、表达式求值以及括号匹配等。
栈提供的基本操作包括：
常见的栈使用场景有表达式求值、深度优先搜索（DFS）以及回溯法。
最小栈 (Min Stack) 是栈的扩展应用，除了提供基本的栈操作外，还能够在常量时间内返回栈中的最小值。下面展示一个最小栈的具体实现。
#include <stack>
using namespace std;
class MinStack {
public:
// 构造函数
MinStack() {}
// 将元素 x 压入栈中
void push(int x) {
_elem.push(x);
// 元素入栈
if (_min.empty() || x <= _min.top()) {
_min.push(x);
// 如果 x 小于等于当前最小值，则将 x 也压入 _min 栈
}
}
// 移除栈顶元素
void pop() {
if (_min.top() == _elem.top()) {
_min.pop();
// 如果当前栈顶元素是最小值，将其从 _min 栈中移除
}
_elem.pop();
}
// 获取栈顶元素
int top() {
return _elem.top();
}
// 获取当前栈中的最小值
int getMin() {
return _min.top();
}
private:
stack<int> _elem; // 存储栈中的所有元素
stack<int> _min; // 存储栈中的最小值
};
int main() {
MinStack minStack;
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
cout << "Current Min: " << minStack.getMin() << endl; // 输出 -3
minStack.pop();
cout << "Top: " << minStack.top() << endl; // 输出 0
cout << "Current Min: " << minStack.getMin() << endl; // 输出 -2
return 0;
}
输出结果：
Current Min: -3
Top: 0
Current Min: -2
在这个例子中，我们实现了一个最小栈，可以在常量时间内获取栈中的最小值。在压栈和弹栈操作时，我们同步更新 _min 栈以维护最小值。
栈的标准实现使用
std::stack容器，但在某些场景下，可以使用std::vector来模拟栈的功能。由于栈的所有操作都围绕末端进行，因此vector的尾插操作与stack类似。
#include <vector>
using namespace std;
template<typename T>
class SimulatedStack {
public:
// 向栈中压入元素
void push(const T& x) {
_data.push_back(x);
}
// 弹出栈顶元素
void pop() {
_data.pop_back();
}
// 获取栈顶元素
T& top() {
return _data.back();
}
// 检查栈是否为空
bool empty() const {
return _data.empty();
}
// 获取栈的大小
size_t size() const {
return _data.size();
}
private:
vector<T> _data; // 用于存储栈元素的容器
};
这种模拟实现使用了 vector 的尾插操作，可以高效地模拟栈的行为。
队列 (Queue) 是一种 先进先出 (FIFO, First In First Out) 的数据结构。这意味着第一个进入队列的元素会第一个被移出。队列通常用于任务调度、广度优先搜索 (BFS) 等场景。
队列的基本操作包括：
以下是队列的基本用法展示，包括插入和删除元素。
#include <queue>
#include <iostream>
using namespace std;
int main() {
queue<int> q;
q.push(1); // 向队尾插入元素 1
q.push(2); // 向队尾插入元素 2
cout << "Front: " << q.front() << endl; // 输出队头元素 1
cout << "Back: " << q.back() << endl; // 输出队尾元素 2
q.pop(); // 移除队头元素
cout << "After pop, Front: " << q.front() << endl; // 输出新的队头元素 2
return 0;
}
输出结果：
Front: 1
Back: 2
After pop, Front: 2
在这个例子中，我们展示了队列的 push()、pop()、front() 和 back() 操作。
在一些场景中，标准库中的
std::queue可能无法满足特定需求，我们可以通过其他容器类来模拟实现队列。由于队列需要支持在头部删除和尾部插入的操作，使用std::list会比std::vector更为高效。list允许在常数时间内进行头部和尾部的插入与删除操作，因此非常适合用于队列的实现。
下面是一个基于 list 的队列模拟实现：
#include <list>
using namespace std;
template<typename T>
class SimulatedQueue {
public:
// 向队尾插入元素
void push(const T& x) {
_data.push_back(x);
}
// 移除队头元素
void pop() {
_data.pop_front();
}
// 获取队头元素
T& front() {
return _data.front();
}
// 获取队尾元素
T& back() {
return _data.back();
}
// 检查队列是否为空
bool empty() const {
return _data.empty();
}
// 获取队列的大小
size_t size() const {
return _data.size();
}
private:
list<T> _data; // 用于存储队列元素的容器
};
int main() {
SimulatedQueue<int> q;
q.push(10); // 向队尾插入元素
q.push(20);
cout << "队头: " << q.front() << endl; // 输出队头元素 10
cout << "队尾: " << q.back() << endl; // 输出队尾元素 20
q.pop(); // 移除队头元素
cout << "新的队头: " << q.front() << endl; // 输出新的队头元素 20
return 0;
}
输出结果：
队头：10
队尾：20
新的队头：20
在这个例子中，SimulatedQueue 模拟了队列的基本功能，包括在队尾插入元素和移除队头元素。
优先队列 (Priority Queue) 是一种特殊类型的队列，其中每个元素都关联有一个优先级。优先队列的特点是元素的弹出顺序不再是按照先进先出，而是按照元素的优先级来决定。通常优先队列可以用来模拟堆结构。
在默认情况下，C++ 标准库中的 std::priority_queue 是一个大顶堆，即优先队列中的最大元素会优先弹出。我们也可以通过自定义比较函数来实现小顶堆，从而使得最小元素优先弹出。
优先队列的常见操作包括：
下面展示了如何使用 std::priority_queue 进行优先队列操作。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
priority_queue<int> pq; // 默认大顶堆
pq.push(10);
pq.push(5);
pq.push(20);
cout << "优先级最高的元素：" << pq.top() << endl; // 输出 20
pq.pop(); // 移除优先级最高的元素
cout << "新的优先级最高的元素：" << pq.top() << endl; // 输出 10
return 0;
}
输出结果：
优先级最高的元素：20
新的优先级最高的元素：10
在这个例子中，priority_queue<int> 实现了一个大顶堆，插入元素后，优先级最高的元素（值最大的元素）会优先弹出。
我们也可以使用 std::greater<T> 来改变默认的比较方式，从而实现小顶堆。下面是一个小顶堆的例子：
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆
pq.push(10);
pq.push(5);
pq.push(20);
cout << "优先级最高的元素（最小值）：" << pq.top() << endl; // 输出 5
pq.pop(); // 移除优先级最高的元素
cout << "新的优先级最高的元素：" << pq.top() << endl; // 输出 10
return 0;
}
输出结果：
优先级最高的元素（最小值）：5
新的优先级最高的元素：10
在这个例子中，priority_queue<int, vector<int>, greater<int>> 实现了一个小顶堆，其中优先级最高的元素是值最小的元素。
优先队列通常是基于堆实现的。在 C++ 中，标准库中的
priority_queue使用std::vector作为底层存储，并通过堆算法管理优先级。在需要自定义优先队列行为时，可以自己实现一个简单的优先队列，利用堆的概念来操作。
下面是一个基于 std::vector 实现的简单优先队列：
#pragma once
#include <iostream>
#include <vector>
using namespace std;
// priority_queue--->堆
namespace W {
// 默认的比较函数为 less，实现大顶堆
template<class T>
struct less {
bool operator()(const T& left, const T& right) {
return left < right;
}
};
// greater 实现小顶堆
template<class T>
struct greater {
bool operator()(const T& left, const T& right) {
return left > right;
}
};
template<class T, class Container = std::vector<T>, class Compare = less<T>>
class priority_queue {
public:
// 创造空的优先级队列
priority_queue() : c() {}
// 构造函数支持从迭代器范围初始化
template<class Iterator>
priority_queue(Iterator first, Iterator last) : c(first, last) {
// 将 c 中的元素调整成堆的结构
int count = c.size();
int root = ((count - 2) >> 1);
for (; root >= 0; root--) AdjustDown(root);
}
// 向队列中插入元素
void push(const T& data) {
c.push_back(data);
AdjustUP(c.size() - 1);
}
// 移除优先级最高的元素
void pop() {
if (empty()) return;
swap(c.front(), c.back());
c.pop_back();
AdjustDown(0);
}
// 获取优先队列的大小
size_t size() const {
return c.size();
}
// 检查优先队列是否为空
bool empty() const {
return c.empty();
}
// 返回优先级最高的元素（不允许修改）
const T& top() const {
return c.front();
}
private:
// 向上调整，维护堆的性质
void AdjustUP(int child) {
// 计算父节点的索引，等同于 (child - 1) / 2，移位操作符效率更快
int parent = ((child - 1) >> 1);
while (child) {
if (Compare()(c[parent], c[child])) {
swap(c[child], c[parent]);
child = parent;
parent = ((child - 1) >> 1);
} else {
return;
}
}
}
// 向下调整，维护堆的性质
void AdjustDown(int parent) {
size_t child = parent * 2 + 1;
while (child < c.size()) {
// 找到父节点较大的孩子
if (child + 1 < c.size() && Compare()(c[child], c[child + 1])) {
child += 1;
}
// 检查双亲是否满足堆的条件
if (Compare()(c[parent], c[child])) {
swap(c[child], c[parent]);
parent = child;
child = parent * 2 + 1;
} else {
return;
}
}
}
private:
Container c; // 底层容器，默认为 vector
};
}
void TestQueuePriority() {
W::priority_queue<int> q1; // 向大顶堆中插入元素
q1.push(5);
q1.push(1);
q1.push(4);
q1.push(2);
q1.push(3);
q1.push(6);
// 输出堆顶元素
cout << "优先级最高的元素：" << q1.top() << endl; // 输出 6
// 弹出两个元素
q1.pop();
q1.pop();
// 再次输出堆顶元素
cout << "新的优先级最高的元素：" << q1.top() << endl; // 输出 4
// 使用 greater 创建小顶堆
vector<int> v{5, 1, 4, 2, 3, 6};
W::priority_queue<int, vector<int>, W::greater<int>> q2(v.begin(), v.end());
// 输出小顶堆的堆顶元素
cout << "优先级最高的元素 (最小值): " << q2.top() << endl; // 输出 1
// 弹出两个元素
q2.pop();
q2.pop();
// 再次输出小顶堆的堆顶元素
cout << "新的优先级最高的元素 (最小值): " << q2.top() << endl; // 输出 3
}
输出结果：
优先级最高的元素：6
新的优先级最高的元素：4
优先级最高的元素 (最小值): 1
新的优先级最高的元素 (最小值): 3
在这个模拟实现中，我们使用 std::vector 作为底层容器，并且通过堆排序算法来维护优先队列的顺序。通过 less 和 greater 函数对象，我们可以分别实现大顶堆和小顶堆。
容器适配器 (Container Adapter) 是一种设计模式，目的是将一种容器包装为另一种接口形式。容器适配器提供了一组特定的成员函数来访问底层的容器。C++ 标准库中，
stack、queue和priority_queue都是容器适配器，它们对容器的操作进行了限制，并定义了特定的访问规则。
容器适配器本质上是对基础容器的封装，它们可以使用
vector、deque、list等作为底层实现，而具体使用哪种容器可以根据需求进行调整。容器适配器只暴露了某些特定的操作，而底层容器的更多操作则被隐藏。
虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为 stack 和队列只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque
常见的容器适配器：
双端队列 (deque, Double-Ended Queue) 是一种可以在头尾两端进行高效插入和删除操作的序列式容器。与 vector 类似，deque 提供了动态数组的功能，但它比 vector 更加灵活，允许在头尾两端都进行元素的添加和删除。
deque 提供了双端操作，即允许在容器的两端进行插入和删除操作。其时间复杂度为常数时间 O(1)，这使得它比 vector 更适合需要频繁在两端插入或删除元素的场景。deque 表面上看起来像是一个连续的数组，但它的底层实现并非真正连续，而是由多块小的连续内存块组合而成，这就允许 deque 在进行元素插入或删除时，不需要像 vector 一样移动大量元素。下面是一张简化的 deque 的内存布局示意图：
-------------------------------- | Block 1 | Block 2 | Block 3 | --------------------------------
每个块表示 deque 底层的一部分内存，插入或删除元素时，只需要操作相应块中的数据，而不需要重新分配整个数组的内存。
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其'整体连续'以及随机访问的假象，落在了 deque 的迭代器身上，因此 deque 的迭代器设计就比较复杂，如下图所示：
那 deque 是如何借助其迭代器维护其假想连续的结构呢？
了解一下即可
虽然 deque 在插入和删除操作上比 vector 更高效，但它也有一些缺点：
deque 的存储结构不是一个连续的内存块，所以在遍历 deque 时，迭代器需要处理内存块之间的跳转，导致遍历性能不如 vector。deque 是由多个小内存块组成的，所以它的内存利用率相比 vector 稍差。不过与 list 比较，deque 的内存效率还是更高。#include <deque>
#include <iostream>
using namespace std;
int main() {
deque<int> d;
// 在队列的两端插入元素
d.push_back(10);
d.push_back(20);
d.push_front(5);
cout << "队头：" << d.front() << endl; // 输出 5
cout << "队尾：" << d.back() << endl; // 输出 20
// 删除队列的两端元素
d.pop_front();
d.pop_back();
cout << "新的队头：" << d.front() << endl; // 输出 10
return 0;
}
输出结果：
队头：5
队尾：20
新的队头：10
这个示例展示了 deque 如何进行两端的插入和删除操作。可以看到，deque 支持同时在队头和队尾进行高效的操作。
C++ 标准库中，stack 和 queue 的底层容器默认使用 deque，这是因为 deque 在元素插入和删除时的性能优势以及空间利用率较高的特点，正好符合 stack 和 queue 对容器的需求。
stack，只需要支持在容器的尾部插入和删除元素，deque 的 push_back() 和 pop_back() 操作可以在常数时间内完成，比 vector 在扩容时效率更高。queue，需要在尾部插入元素、在头部删除元素，deque 同时支持 push_back() 和 pop_front() 操作，效率比 list 高，且不需要存储额外的指针信息。虽然 vector 也可以作为 stack 的底层容器，但它在尾部插入元素时需要在扩容时移动大量元素，因此效率不如 deque。而 list 虽然也支持两端插入删除操作，但由于需要存储额外的指针信息，空间利用率不如 deque 高。因此，deque 被认为是 stack 和 queue 的默认最佳选择。
stack 的模拟实现只需要封装一个可以支持末端插入和删除操作的容器，默认情况下，使用 deque 作为底层容器。
#include <deque>
namespace W {
template<typename T, typename Container = deque<T>>
class stack {
public:
stack() {}
// 向栈中压入元素
void push(const T& x) {
_c.push_back(x);
}
// 弹出栈顶元素
void pop() {
_c.pop_back();
}
// 获取栈顶元素
T& top() {
return _c.back();
}
// 检查栈是否为空
bool empty() const {
return _c.empty();
}
// 获取栈的大小
size_t size() const {
return _c.size();
}
private:
Container _c; // 底层容器，默认使用 deque
};
}
queue 的实现需要支持队尾插入元素、队头删除元素的操作。类似 stack，queue 默认使用 deque 作为底层容器。
#include <deque>
namespace W {
template<typename T, typename Container = deque<T>>
class queue {
public:
queue() {}
// 向队尾插入元素
void push(const T& x) {
_c.push_back(x);
}
// 移除队头元素
void pop() {
_c.pop_front();
}
// 获取队头元素
T& front() {
return _c.front();
}
// 获取队尾元素
T& back() {
return _c.back();
}
// 检查队列是否为空
bool empty() const {
return _c.empty();
}
// 获取队列的大小
size_t size() const {
return _c.size();
}
private:
Container _c; // 底层容器，默认使用 deque
};
}
在本文中，我们详细探讨了 栈 (stack) 和 队列 (queue) 的概念、应用及其实现方式。通过对 deque 和 priority_queue 的深入理解，我们可以更高效地解决实际编程问题。
deque 作为双端队列，支持在头尾两端进行高效的插入和删除操作。stack 和 queue 使用 deque 作为底层容器，利用其高效的插入删除操作实现栈和队列的功能。通过对这些数据结构的深入理解，我们能够在编程中更加灵活、准确地选择合适的工具来解决实际问题。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online