文章介绍了 C++ STL 中的三种容器适配器：Stack（栈）、Queue（队列）和 Priority Queue（优先队列）。详细阐述了它们的定义、底层实现原理（如 Stack 基于 deque 实现 LIFO，Queue 基于 deque 实现 FIFO）、核心成员函数接口（push、pop、top/front/back 等）以及模拟实现方法。通过最小栈、用栈实现队列等经典 OJ 题目示例，展示了这些数据结构在实际场景中的应用，并对比了 deque 作为底层容器的优势。
这是 C++ 标准库中 std::stack 的官方文档说明。Stack 是 C++ STL（标准模板库）中的容器适配器（不是独立容器），它封装了底层容器（默认是 deque），并强制遵循后进先出（LIFO, Last In First Out）的访问规则 —— 只能从栈顶插入、删除和读取元素，无法随机访问栈中的其他元素，也不支持迭代器遍历。
1️⃣ 模板定义
template <class T, class Container = deque> class stack;
stack 是一个模板类，有两个参数：
T: 栈中存储的元素类型（比如 int、string）。Container: 底层用来存储数据的容器类型，默认是 deque<T>。你也可以手动指定为 vector 或 list。2️⃣ LIFO Stack（后进先出栈） 核心规则：栈是后进先出（Last-In-First-Out）的容器，元素只能从栈顶（容器的一端）插入和取出，不能随机访问中间元素。
3️⃣ 容器适配器的本质
stack 不是一个独立的容器，而是一个容器适配器（container adaptor）。它的底层是封装了一个普通容器（比如默认的 deque），然后只暴露符合栈规则的接口。入栈（push）和出栈（pop）操作，本质是在底层容器的尾部（back）进行插入和删除，这个尾部就是栈的顶部（top）。
4️⃣ 底层容器的要求
要作为 stack 的底层容器，必须支持以下操作：
empty(): 判断容器是否为空size(): 返回容器元素数量back(): 访问容器尾部元素push_back(): 在容器尾部插入元素pop_back(): 删除容器尾部元素标准库中的 vector、deque、list 都满足这些要求，因此都可以作为 stack 的底层容器。默认情况下，stack 会使用 deque，因为它在两端插入/删除的效率很高，是最优选择。
这是 C++ 标准库中
std::stack构造函数的官方文档说明。
1️⃣ 构造函数签名
explicit stack (const container_type& ctnr = container_type());
explicit 关键字: 表示这个构造函数不能用于隐式类型转换，必须显式调用，避免意外的类型转换。ctnr: 是底层容器的对象（比如默认的 deque<T>），默认值是 container_type()，也就是默认构造一个空的底层容器。C++98 和 C++11 标签说明这个构造函数在 C++98 就已存在，并在 C++11 中继续支持。2️⃣ 核心功能
这个构造函数的作用是创建一个 stack 容器适配器对象。因为 stack 是容器适配器，它内部会维护一个底层容器来存储数据：如果构造时传入了 ctnr 参数，内部底层容器会是这个参数的副本；如果没有传参数，就默认创建一个空的底层容器（比如默认的 deque）。
3️⃣ 参数详解
ctnr: 这是底层容器的对象，container_type 是 stack 模板的第二个参数 Container 的类型别名（比如默认是 deque<T>）。你可以通过这个参数，用一个已有的容器来初始化栈。alloc: 这是分配器对象，用于底层容器的内存分配。这个参数仅在分配器类型满足 uses_allocator::value == true 时才会生效，一般日常开发中很少用到。stack 来构造新的栈（即拷贝构造）。这是 C++ 标准库中
std::stack::empty成员函数的官方文档说明。
1️⃣ 函数签名
bool empty() const;
bool: 返回值是布尔类型，表示栈是否为空。const: 这是一个只读成员函数，调用时不会修改栈的任何内容。2️⃣ 核心功能
这个函数的作用是判断栈是否为空（即栈中元素的数量是否为 0）。因为 stack 是容器适配器，它的 empty() 本质上是调用了底层容器（比如默认的 deque）的 empty() 方法来实现的。
3️⃣ 参数与返回值
true: 栈为空（底层容器的大小为 0）。false: 栈不为空（底层容器包含至少一个元素）。这是 C++ 标准库中
std::stack::size成员函数的官方文档说明。
1️⃣ 函数签名
size_type size() const;
size_type: 返回值类型，是一个无符号整数类型（通常和 size_t 等价）。const: 这是一个只读成员函数，调用时不会修改栈的内容。2️⃣ 核心功能
这个函数的作用是返回栈中当前的元素数量。因为 stack 是容器适配器，它的 size() 本质上是调用了底层容器（比如默认的 deque）的 size() 方法来实现的。
3️⃣ 参数与返回值
size_type。这是 C++ 标准库中
std::stack::top成员函数的官方文档说明。
1️⃣ 函数签名 (两个重载版本)
value_type& top();
const value_type& top() const;
value_type& top();: 返回栈顶元素的可读写引用，用于修改栈顶元素。const value_type& top() const;: 返回栈顶元素的只读引用，仅用于读取，不能修改。2️⃣ 核心功能
这个函数的作用是返回栈顶元素的引用。因为栈是后进先出（LIFO）的容器，栈顶元素就是最后插入的那个元素。它本质上是调用了底层容器（比如默认的 deque）的 back() 方法来实现的。
3️⃣ 关键注意事项
调用 top() 前，必须先用 empty() 判断栈是否为空！如果栈为空时调用 top()，会触发未定义行为（通常导致程序崩溃）。
这是 C++ 标准库中
std::stack::push成员函数的官方文档说明。
1️⃣ 函数签名
void push (const value_type& val);
void: 无返回值，执行入栈操作后不返回任何内容。const value_type& val: 参数是要入栈的元素的const 引用，避免拷贝开销，同时保证不会修改传入的原始值。2️⃣ 核心功能
这个函数的作用是在栈顶插入一个新元素，新元素的内容是参数 val 的副本。因为 stack 是容器适配器，它的 push() 本质上是调用了底层容器（比如默认的 deque）的 push_back() 方法，在容器的尾部（也就是栈的顶部）插入元素。
3️⃣ 关键对比
push() 是通过拷贝元素入栈，如果你想更高效地直接在栈顶构造元素（避免拷贝），可以使用 emplace() 方法。
这是 C++ 标准库中
std::stack::emplace成员函数的官方文档说明。
1️⃣ 函数签名
template <class... Args> void emplace (Args&&... args);
class... Args 和 Args&&... args 是 C++11 引入的可变参数模板和完美转发语法，用来接收任意数量、任意类型的参数，并原封不动地转发给元素的构造函数。2️⃣ 核心功能
这个函数的作用是在栈顶原地构造并插入一个新元素。和 push() 不同：
push() 是先构造一个临时元素，再将其拷贝/移动到栈顶；emplace() 则直接在栈顶的内存位置上，用传入的参数构造元素，完全避免了拷贝或移动的开销，效率更高。这是 C++ 标准库中
std::stack::pop成员函数的官方文档说明。
1️⃣ 函数签名
void pop();
void: 无返回值，执行出栈操作后不返回任何内容。2️⃣ 核心功能
这个函数的作用是移除栈顶的元素，并将栈的大小减 1。被移除的元素是最后一个入栈的元素（符合后进先出规则），它的值可以在调用 pop() 前通过 stack::top() 获取。
3️⃣ 关键注意事项
pop() 不返回被删除的元素：新手常误以为 pop() 会返回栈顶值，实际它仅删除元素。如果需要获取被删除的值，必须先调用 top() 读取，再调用 pop() 删除。pop() 会崩溃：调用 pop() 前，必须先用 empty() 判断栈是否为空，否则会触发未定义行为（通常导致程序崩溃）。这是 C++ 标准库中
std::stack::swap成员函数的官方文档说明。
1️⃣ 函数签名
void swap (stack& x) noexcept(/*see below*/);
noexcept: 该函数是否抛出异常，取决于底层容器的 swap 操作是否是 noexcept（比如默认底层容器 deque 的 swap 是 noexcept，因此 stack 的 swap 也会是 noexcept）。2️⃣ 核心功能
这个函数的作用是交换当前栈和参数栈 x 的全部内容。因为 stack 是容器适配器，它的 swap 本质上是调用了底层容器的非成员 swap 函数，直接交换两个栈的底层容器（比如默认的 deque），这个过程通常是 O(1) 时间复杂度（仅交换底层容器的内部指针，不拷贝元素），效率非常高。
class MinStack {
public:
MinStack() {}
void push(int val) {
_st.push(val);
if (_minst.empty() || val <= _minst.top()) _minst.push(val);
}
void pop() {
if (_st.top() == _minst.top()) _minst.pop();
_st.pop();
}
int top() { return _st.top(); }
int getMin() { return _minst.top(); }
private:
stack<int> _st;
stack<int> _minst;
};
class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
stack<int> st;
size_t pushi = 0, popi = 0;
while (pushi < pushV.size()) {
st.push(pushV[pushi++]);
while (!st.empty() && st.top() == popV[popi]) {
popi++;
st.pop();
}
}
return st.empty();
}
};
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> st;
int j = 0;
for (int num : pushed) {
st.push(num);
while (!st.empty() && st.top() == popped[j]) {
st.pop();
j++;
}
}
return st.empty();
}
};
class Solution {
public:
vector<string> buildArray(vector<int>& target, int n) {
vector<string> res;
int i = 0;
for (int num = 1; num <= n && i < target.size(); num++) {
res.push_back("Push");
if (num == target[i]) {
i++;
} else {
res.push_back("Pop");
}
}
return res;
}
};
class SortedStack {
private:
stack<int> _main; // 主栈：保存有序元素（栈顶最小）
stack<int> _temp; // 临时栈：辅助排序
public:
SortedStack() {}
void push(int val) {
while (!_main.empty() && _main.top() < val) {
_temp.push(_main.top());
_main.pop();
}
_main.push(val);
while (!_temp.empty()) {
_main.push(_temp.top());
_temp.pop();
}
}
void pop() {
if (!_main.empty()) {
_main.pop();
}
}
int peek() { return _main.empty() ? -1 : _main.top(); }
bool isEmpty() { return _main.empty(); }
};
#include<iostream>
#include<deque>
#include<vector>
using namespace std;
template<class T, class Container = deque<T>>
class Stack {
public:
bool empty() const { return _con.empty(); }
size_t size() const { return _con.size(); }
T& top() { return _con.back(); }
const T& top() const { return _con.back(); }
void push(const T& val) { _con.push_back(val); }
void push(T&& val) { _con.push_back(move(val)); }
void pop() {
if (!()) {
_con.();
}
}
:
Container _con;
};
{
Stack<> st1;
st(); st(); st();
cout << << st() << endl;
cout << << st() << endl;
st();
cout << << st() << endl;
;
}
1️⃣ 核心定义: FIFO 队列
std::queue 是一个先进先出（FIFO, First-In First-Out）的容器适配器，元素从一端（队尾）插入，从另一端（队首）取出，符合'先入队的元素先出队'的规则。
2️⃣ 本质: 容器适配器
和 std::stack 一样，queue 本身不直接存储数据，而是封装了一个底层容器（默认是 std::deque），所有操作都通过调用底层容器的接口实现：
push）→ 底层容器的 push_back()（队尾插入）pop）→ 底层容器的 pop_front()（队首删除）front）→ 底层容器的 front()back）→ 底层容器的 back()3️⃣ 底层容器的要求 底层容器必须支持以下操作：
empty(), size(), front(), back(), push_back(), pop_front()。
标准库中，std::deque 和 std::list 都满足这些要求，因此 queue 默认使用 std::deque 作为底层容器。4️⃣ 模板定义
template <class T, class Container = deque> class queue;
| Queue 接口 | 底层容器接口 | 说明 |
|---|---|---|
push(val) | _con.push_back(val) | 入队：队尾插入元素 |
pop() | _con.pop_front() | 出队：删除队首元素（无返回值） |
front() | _con.front() | 获取队首元素 |
back() | _con.back() | 获取队尾元素 |
empty() | _con.empty() | 判断队列是否为空 |
size() | _con.size() | 获取队列元素个数 |
这是 C++ 标准库中
std::queue构造函数的官方文档。
1️⃣ 构造函数签名
explicit queue (const container_type& ctnr = container_type());
explicit: 表示这个构造函数不能用于隐式类型转换，必须显式调用。container_type: 是底层容器的类型别名，对应模板参数 Container（默认是 std::deque<T>）。ctnr: 可选参数，是一个底层容器对象的引用。如果传入，队列的内部容器会是这个对象的副本；如果不传入，默认会创建一个空的底层容器。bool empty() const;
用于判断队列是否为空。本质是检查队列的大小是否为 0。时间复杂度为 O(1)。
size_type size() const;
用于获取队列中当前的元素数量。时间复杂度为 O(1)。
value_type& front();
const value_type& front() const;
用于访问队列的队首元素。注意：如果队列为空时调用 front()，会触发未定义行为。
value_type& back();
const value_type& back() const;
用于访问队列的队尾元素。注意：如果队列为空时调用 back()，会触发未定义行为。
void push (const value_type& val);
用于在队列的队尾插入一个新元素。时间复杂度为 O(1)。
template <class... Args> void emplace (Args&&... args);
用于在队列的队尾原地构造一个新元素。比 push 更高效。
void pop();
用于移除队列的队首元素。注意：pop() 仅删除队首元素，不会返回被删除的元素值。
void swap (queue& x) noexcept;
用于交换当前队列与另一个同类型队列的全部内容。时间复杂度通常为 O(1)。
class MyQueue {
private:
stack<int> inStack;
stack<int> outStack;
void transfer() {
if (outStack.empty()) {
while (!inStack.empty()) {
outStack.push(inStack.top());
inStack.pop();
}
}
}
public:
MyQueue() {}
void push(int x) { inStack.push(x); }
int pop() {
transfer();
int val = outStack.top();
outStack.pop();
return val;
}
int peek() {
transfer();
return outStack.top();
}
bool empty() { return inStack.empty() && outStack.empty(); }
};
class MyStack {
private:
queue<int> q1;
queue<int> q2;
public:
MyStack() {}
void push(int x) {
q2.push(x);
while (!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
swap(q1, q2);
}
int pop() {
int val = q1.front();
q1.pop();
return val;
}
int top() { return q1.front(); }
bool empty() { return q1.empty(); }
};
class MyCircularDeque {
private:
vector<int> data;
int front;
int rear;
int capacity;
public:
MyCircularDeque(int k) {
capacity = k + 1;
data.resize(capacity);
front = 0; rear = 0;
}
bool insertFront(int value) {
if (isFull()) return false;
front = (front - 1 + capacity) % capacity;
data[front] = value;
return true;
}
bool insertLast(int value) {
if (isFull()) return false;
data[rear] = value;
rear = (rear + 1) % capacity;
return true;
}
bool deleteFront() {
if (isEmpty()) return false;
front = (front + 1) % capacity;
return true;
}
bool deleteLast() {
(()) ;
rear = (rear - + capacity) % capacity;
;
}
{ () ? : data[front]; }
{ () ? : data[(rear - + capacity) % capacity]; }
{ front == rear; }
{ (rear + ) % capacity == front; }
};
class FrontMiddleBackQueue {
private:
deque<int> left;
deque<int> right;
void balance() {
if (left.size() > right.size() + 1) {
right.push_front(left.back());
left.pop_back();
} else if (right.size() > left.size()) {
left.push_back(right.front());
right.pop_front();
}
}
public:
FrontMiddleBackQueue() {}
void pushFront(int val) { left.push_front(val); balance(); }
void pushMiddle(int val) {
if (left.size() > right.size()) {
right.push_front(left.back());
left.pop_back();
}
left.push_back(val);
balance();
}
void pushBack(int val) { right.push_back(val); balance(); }
{
(left.() && right.()) ;
val;
(!left.()) { val = left.(); left.(); }
{ val = right.(); right.(); }
();
val;
}
{
(left.() && right.()) ;
val = left.();
left.();
();
val;
}
{
(left.() && right.()) ;
val;
(!right.()) { val = right.(); right.(); }
{ val = left.(); left.(); }
();
val;
}
};
核心解题思路：
k == 1: 只能生成循环移位，遍历所有结果选字典序最小。k >= 2: 能实现字符的任意重排，直接对字符串排序即可。class Solution {
public:
string orderlyQueue(string s, int k) {
if (k == 1) {
string res = s;
int n = s.size();
for (int i = 1; i < n; ++i) {
string temp = s.substr(i) + s.substr(0, i);
if (temp < res) res = temp;
}
return res;
} else {
sort(s.begin(), s.end());
return s;
}
}
};
#include<iostream>
#include<deque>
#include<list>
using namespace std;
template<class T, class Container = deque<T>>
class Queue {
public:
bool empty() const { return _con.empty(); }
size_t size() const { return _con.size(); }
T& front() { return _con.front(); }
const T& front() const { return _con.front(); }
T& back() { return _con.back(); }
const T& back() const { return _con.back(); }
void push(const T& val) { _con.push_back(val); }
{ _con.((val)); }
{
(!()) {
_con.();
}
}
{ _con.(other._con); }
:
Container _con;
};
{
Queue<> q1;
q(); q(); q();
cout << << q() << endl;
cout << << qront() << endl;
cout << << q() << endl;
q();
cout << << qront() << endl;
;
}
1️⃣ 本质: 带优先级的容器适配器
std::priority_queue 是一个容器适配器，它不直接存储数据，而是封装了一个底层容器（默认是 std::vector），并通过堆（heap）算法维护元素的优先级顺序，保证队首（堆顶）始终是优先级最高的元素（默认是最大的元素）。
2️⃣ 模板定义
template <class T, class Container = vector, class Compare = less> class priority_queue;
T: 队列存储的元素类型。Container: 底层容器类型（默认是 std::vector），需要支持随机访问迭代器。Compare: 优先级比较规则（默认是 less<T>，即构建大顶堆；若改为 greater<T>，则构建小顶堆）。3️⃣ 核心特性
O(log n)。这是 C++ 标准库中
std::priority_queue构造函数的官方文档。
1️⃣ 构造函数的核心版本
explicit priority_queue (const Compare& comp = Compare(), const Container& ctnr = Container());template <class InputIterator> priority_queue (InputIterator first, InputIterator last, ...)2️⃣ 参数详细解释
comp: 堆的排序比较对象。默认是 less<T>（大顶堆），若传入 greater<T> 则构建小顶堆。ctnr: 底层容器对象。默认是 vector<T>。first, last: 输入迭代器，指向要插入的元素范围。3️⃣ 底层实现逻辑 无论哪个版本的构造函数，最终都会执行以下步骤：
make_heap 算法，将底层容器转换为堆结构。bool empty() const;
用于判断优先队列是否为空。时间复杂度为 O(1)。
size_type size() const;
用于获取优先队列中当前的元素总数。时间复杂度为 O(1)。
const value_type& top() const;
用于访问优先队列的队首（堆顶）元素。注意：如果队列为空时调用 top()，会触发未定义行为。
void push (const value_type& val);
用于向优先队列中插入一个新元素。插入后会自动维护堆的结构。时间复杂度为 O(log n)。
template <class... Args> void emplace (Args&&... args);
用于在优先队列的底层容器中原地构造一个新元素。效率高于 push。
void pop();
用于删除优先队列的队首（堆顶）元素。时间复杂度为 O(log n)。
void swap (priority_queue& x) noexcept;
用于完整交换当前优先队列与另一个同类型队列的全部内容。时间复杂度通常为 O(1)。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> p(nums.begin(), nums.end());
for (int i = 0; i < k - 1; ++i) {
p.pop();
}
return p.top();
}
};
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> count;
for (int num : nums) count[num]++;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (auto& [num, freq] : count) {
pq.push({freq, num});
if (pq.size() > k) pq.pop();
}
vector<int> res;
while (!pq.empty()) {
res.push_back(pq.top().second);
pq.pop();
}
return res;
}
};
class KthLargest {
private:
priority_queue<int, vector<int>, greater<int>> min_heap;
int k_;
public:
KthLargest(int k, vector<int>& nums): k_(k) {
for (int num : nums) {
min_heap.push(num);
if (min_heap.size() > k_) min_heap.pop();
}
}
int add(int val) {
if (min_heap.size() < k_) min_heap.push(val);
else if (val > min_heap.top()) {
min_heap.pop();
min_heap.push(val);
}
return min_heap.top();
}
};
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
priority_queue<pair<long long, vector<int>>> max_heap;
for (auto& point : points) {
long long dist_sq = (long long)point[0]*point[0] + (long long)point[1]*point[1];
max_heap.push({dist_sq, point});
if (max_heap.size() > k) max_heap.pop();
}
vector<vector<int>> res;
while (!max_heap.empty()) {
res.push_back(max_heap.top().second);
max_heap.pop();
}
return res;
}
};
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
template<class T, class Container = vector<T>, class Compare = less<T>>
class PriorityQueue {
public:
PriorityQueue(): _con(), _comp() {}
template<class InputIterator>
PriorityQueue(InputIterator first, InputIterator last): _con(first, last), _comp() {
make_heap(_con.begin(), _con.end(), _comp);
}
bool empty() const { return _con.empty(); }
size_t size() const { return _con.size(); }
const T& top() const {
if (empty()) abort();
return _con.front();
}
void push {
_con.(val);
(_con.(), _con.(), _comp);
}
{
(()) ();
(_con.(), _con.(), _comp);
_con.();
}
{
std::swap;
(_con, other._con);
(_comp, other._comp);
}
:
Container _con;
Compare _comp;
};
{
PriorityQueue<> pq1;
pq(); pq(); pq();
cout << << pq() << endl;
pq();
cout << << pq() << endl;
;
}
适配器是一种设计模式,核心作用是接口转换:它将一个已有类/对象的接口，转换成另一个符合业务需求的接口，让原本接口不兼容的组件可以协同工作。
在 C++ 标准库中，最常见的是容器适配器（如 queue、stack、priority_queue），此外还有迭代器适配器（如 reverse_iterator）、函数适配器（如 bind）等。
1️⃣ 核心特点: 以容器适配器为例
C++ 中的容器适配器不直接管理存储,而是封装一个底层容器（如 vector、deque），并通过接口适配，对外提供更简洁、场景化的操作。
2️⃣ 典型示例: priority_queue 作为适配器
priority_queue 是基于堆的容器适配器，核心适配逻辑：
vector。make_heap、push_heap、pop_heap 等算法。虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为 stack 和队列只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque。
Deque（双端队列）: 是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)。
| 特性 | Deque | Vector | List |
|---|---|---|---|
| 内存连续性 | 非连续（分段连续） | 连续 | 非连续（节点式） |
| 随机访问 | 支持（O(1)，略慢） | 支持（O(1)，最快） | 不支持 |
| 队首增删 | O(1) | O(n) | O(1) |
| 队尾增删 | O(1) | O(1)（扩容时 O(n)） | O(1) |
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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