C++算法
C++ 栈和队列：stack/queue/priority_queue 用法与 STL 实现对比
C++ 中的栈和队列属于容器适配器，底层默认使用 deque。栈遵循后进先出原则，队列遵循先进先出原则，优先队列则基于堆结构实现元素优先级调度。这三种容器的基本接口、使用场景及模拟实现方法，深入分析了 STL 标准库中它们的设计原理，包括为何选择 deque 作为底层容器以及其优缺点，并提供了相关代码示例帮助理解核心逻辑。
C++ 中的栈和队列属于容器适配器，底层默认使用 deque。栈遵循后进先出原则，队列遵循先进先出原则，优先队列则基于堆结构实现元素优先级调度。这三种容器的基本接口、使用场景及模拟实现方法，深入分析了 STL 标准库中它们的设计原理，包括为何选择 deque 作为底层容器以及其优缺点，并提供了相关代码示例帮助理解核心逻辑。
在 C++ 中，栈和队列的设计理念本质是一个底层包含某容器的容器适配器。故要想完全了解 C++ 中栈和队列的设计，需要先补充一下容器适配器的概念。
适配器是一种设计模式，该种模式是将一个类的接口转换成客户希望的另外一个接口，可以理解为将一个底层容器转变为另一个满足实际需求的容器。
结合图片理解：我们有一个欧洲壁式插座，该插座只有三头的，现在我们想要用两头的，用来满足我们的生活需求，所以在三头的基础上创造了一个两头的作为该插座的适配器。
虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器。这是因为 stack 和队列只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque。
deqe(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)。
与 vector 比较，头插效率高，不需要搬移元素；与 list 比较，空间利用率比较高。
vector 的头插需要连续的一片空间的移动，而 deque 的设计是其第一个存储的实际数据在开辟的连续空间的中间某处，list 每次存储数据就要 new Node，而 deque 存储的空间通过迭代器找到的一个个连续的物理空间。
但是 deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个动态的二维数组，其底层结构如下图所示
中控器的设计实在 deque 里，iterator 类里封装了四个指针 cur, first, last, node。 cur: 指向当前存储的一小段空间的下一个将要存储的空间 first: 指向当前存储的一段连续空间的头 last: 指向当前存储的一段连续空间的尾 node: 指向当前存储的一段连续空间，可以简单理解为数组指针 缓冲区 buffer 是内存池，是实际存储数据的一段段连续空间
那 deque 是如何借助其迭代器维护其假想连续的结构呢？
借用图理解：
图里面的 map 即我们所说的 deque。
与 vector 比较，deque 的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是比 vector 高的。vector 扩容调用 new [] 底层本质是 malloc，而该函数会有新开辟空间拷贝数据的行为 -> 相较来说效率低下。
与 list 比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。但是，deque 有一个致命缺陷：不适合遍历，因为在遍历时，deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下。而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list，deque 的应用并不多，而目前能看到的的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构。
deque 的优势
stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 都可以；queue 是先进先出的特殊线性数据结构，只要具有 push_back 和 pop_front 操作的线性结构，都可以作为 queue 的底层容器，比如 list。但是 STL 中对 stack 和 queue 默认选择 deque 作为其底层容器，主要是因为：stack 和 queue 不需要遍历 (因此 stack 和 queue 没有迭代器)，只需要在固定的一端或者两端进行操作。在 stack 中元素增长时，deque 比 vector 的效率高 (扩容时不需要搬移大量数据)；queue 中的元素增长时，deque 不仅效率高，而且内存使用率高。
所以当实际应用的时候，如果有遍历数据的需求，我们一般不会采用 deque，而是普通的线性表 vector / list。但是当只用到一端或者两端接口的数据时，相较 vector / list，我们就可以用 deque，这样就充分发挥了缝合怪 deque 的优点，而完美的避开了其缺陷。
前面我们介绍了容器适配器，而 Stack 就是一个适配器，底层默认容器为 deque，因此 Stack 的使用要充分发挥 deque 的优点，故 Stack 的一般应用场景是对栈顶一段操作。
几道例题
最小栈
#define _CRT_SECURE_NO_WARNINGS
class MinStack {
public:
void push(int x) {
// 只要是压栈，先将元素保存到_elem 中
_elem.push(x);
// 如果 x 小于_min 中栈顶的元素，将 x 再压入_min 中
if (_min.empty() || x <= _min.top()) _min.push(x);
}
void pop() {
// 如果_min 栈顶的元素等于出栈的元素，_min 顶的元素要移除
if (_min.top() == _elem.top()) _min.pop();
_elem.pop();
}
int top() { return _elem.top(); }
int getMin() { return _min.top(); }
private:
// 保存栈中的元素
std::stack<int> _elem;
// 保存栈的最小值
std::stack<int> _min;
};
创立两个栈，一个栈存储所有数据，一个栈存储最小元素。所有元素入 elem 入栈的同时判断该元素是否比_min 栈顶元素小，小的话也入_min。出栈时 elem 直接出，同时判断 elem 的栈顶与_min 栈顶是否相同，相同_min 也出，不同只有 elem 出。
栈的弹出与压入序列
class Solution {
public:
bool IsPopOrder(vector<int> pushV, vector<int> popV) {
// 入栈和出栈的元素个数必须相同
if (pushV.size() != popV.size()) return false;
// 用 s 来模拟入栈与出栈的过程
int outIdx = 0;
int inIdx = 0;
stack<int> s;
while (outIdx < popV.size()) {
// 如果 s 是空，或者栈顶元素与出栈的元素不相等，就入栈
while (s.empty() || s.top() != popV[outIdx]) {
if (inIdx < pushV.size()) s.push(pushV[inIdx++]);
else return false;
}
// 栈顶元素与出栈的元素相等，出栈
s.pop();
outIdx++;
}
return true;
}
};
该题就是模拟进栈出栈的流程：两个指针分别扫描入栈和出栈的序列表。扫描入栈序列表一个个正常入栈，更新入栈序列表指针，接着当栈顶元素与此时指向出栈序列表的数据相同就出栈，更新出栈序列表指针（可能连续出，故是循环）。当出栈序列表指针走完了，代表着可以模拟此次的入栈出栈顺序，即返回 true。
逆波兰表达式
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> s;
for (size_t i = 0; i < tokens.size(); ++i) {
string& str = tokens[i];
// str 为数字
if (!("+" == str || "-" == str || "*" == str || "/" == str)) {
s.push(atoi(str.c_str()));
} else {
// str 为操作符
int right = s.top(); s.pop();
int left = s.top(); s.pop();
switch (str[0]) {
case '+': s.push(left + right); break;
case '-': s.push(left - right); break;
case '*': s.push(left * right); break;
case '/': // 题目说明了不存在除数为 0 的情况
s.push(left / right); break;
}
}
}
return s.top();
}
};
遍历字符数组，当前位是数字就入栈，当前位是字符（加减乘除）就运算，出栈顶和次顶两个元素。
两个栈实现队列
该题自行实现练习。
【代码样例】：从栈的接口中可以看出，栈实际是一种特殊的 vector，因此使用 vector 完全可以模拟实现 stack。
#pragma once
#include <vector>
// stl Stack 栈的模拟实现
// 在 C++stl 中 Stack 是一种适配器 底层是 stl 中的其他容器
namespace twg {
template<class T, class container = vector<T>>
class Stack {
public:
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_back(); }
const T& top() const { return _con.back(); }
bool empty() const { return _con.empty(); }
size_t size() const { return _con.size(); }
private:
container _con; // 底层容器
};
}
stl 中的 Stack 的默认容器时 deque。
翻译：
队列是一种容器适配器，专门用于在 FIFO 上下文 (先进先出) 中操作，其中从容器一端插入元素，另一端提取元素。队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：size：返回队列中有效元素的个数 front：返回队头元素的引用 back：返回队尾元素的引用 push_back：在队列尾部入队列 pop_front：在队列头部出队列。标准容器类 deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 deque。
empty：检测队列是否为空
用 queue 实现栈
该题自行实现练习。
#pragma once
#include <deque>
// 模拟 C++ stl 中的 queue
// 在 C++ 中 queue 是一种适配器设计 底层是其他容器
namespace twg {
template<class T, class Container = deque<T>>
class queue {
public:
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_front(); }
bool empty() const { return _con.empty(); }
const T& back() const { return _con.back(); }
const T& front() const { return _con.front(); }
size_t size() const { return _con.size(); }
private:
Container _con;
};
}
翻译：
优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素 (优先队列中位于顶部的元素)。优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的'尾部'弹出，其称为优先队列的顶部。底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作 empty()：检测容器是否为空 size()：返回容器中有效元素个数 front()：返回容器中第一个元素的引用 push_back()：在容器尾部插入元素 pop_back()：删除容器尾部元素。标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue 类实例化指定容器类，则使用 vector。需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 来自动完成此操作。
优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。注意：默认情况下 priority_queue 是大堆。
【注意】： 1. 默认情况下，priority_queue 是大堆。
#include <vector>
#include <queue>
#include <functional>// greater 算法的头文件
void TestPriorityQueue() {
// 默认情况下，创建的是大堆，其底层按照小于号比较
vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
priority_queue<int> q1;
for (auto& e : v) q1.push(e);
cout << q1.top() << endl;
// 如果要创建小堆，将第三个模板参数换成 greater 比较方式
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
cout << q2.top() << endl;
}
2. 如果在 priority_queue 中放自定义类型的数据，用户需要在自定义类型中提供 > 或者 < 的重载。
class Date {
public:
Date(int year = 1900, int month = 1, int day = 1) :_year(year),_month(month),_day(day) {}
bool operator<(const Date& d) const {
return (_year < d._year) || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d) const {
return (_year > d._year) || (_year == d._year && _month > d._month) || (_year == d._year && _month == d._month && _day > d._day);
}
friend ostream& operator<<(ostream& _cout, const Date& d) {
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
private:
int _year;
int _month;
int _day;
};
void TestPriorityQueue() {
// 大堆，需要用户在自定义类型中提供<的重载
priority_queue<Date> q1;
q1.push(Date(2018,10,29));
q1.push(Date(2018,10,28));
q1.push(Date(,,));
cout << q() << endl;
priority_queue<Date, vector<Date>, greater<Date>> q2;
q((,,));
q((,,));
q((,,));
cout << q() << endl;
}
第 K 大的数
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 将数组中的元素先放入优先级队列中
priority_queue<int> p(nums.begin(), nums.end());
// 将优先级队列中前 k-1 个元素删除掉
for (int i = 0; i < k - 1; ++i) {
p.pop();
}
return p.top();
}
};
#pragma once
#include <assert.h>
#include <vector>
namespace twg {
// 升序比较器
template<class T>
class Less {
public:
bool operator()(const T& x, const T& y) {
return x < y; // 小于：用于构建大根堆
}
};
// 降序比较器
template<class T>
class Greater {
public:
bool operator()(const T& x, const T& y) {
return x > y; // 大于：用于构建小根堆
}
};
// 优先级队列（堆）实现
template<class T, class Container = vector<T>, class Compare = Less<typename Container::value_type>>
class PriorityQueue {
public:
// 向上调整：用于插入元素后维持堆结构
void AdjustUp(int child) {
assert(child >= );
Compare cmp;
parent = (child - ) / ;
(parent >= ) {
((_con[parent], _con[child])) {
(_con[parent], _con[child]);
child = parent;
parent = (child - ) / ;
} {
;
}
}
}
{
Compare cmp;
child = parent * + ;
(child < ()_con.()) {
(child + < ()_con.() && (_con[child], _con[child + ])) {
++child;
}
((_con[parent], _con[child])) {
(_con[parent], _con[child]);
parent = child;
child = parent * + ;
} {
;
}
}
}
{
_con.(x);
(_con.() - );
}
{
(!());
(_con[], _con[_con.() - ]);
_con.();
();
}
{ _con.(); }
{ _con.(); }
{
(!());
_con.();
}
:
Container _con;
};
}
#include <deque>
namespace bite {
template<class T, class Con = deque<T>>//template<class T, class Con = vector<T>>//template<class T, class Con = list<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:
Con _c;
};
}
#include <deque>
#include <list>
namespace bite {
template<class T, class Con = deque<T>>//template<class T, class Con = list<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 { _c.(); }
:
Con _c;
};
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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