跳到主要内容 C++ STL 容器适配器：Stack、Queue 及 Priority Queue 详解 | 极客日志
C++ 算法
C++ STL 容器适配器：Stack、Queue 及 Priority Queue 详解 文章介绍了 C++ STL 中的三种容器适配器：Stack（栈）、Queue（队列）和 Priority Queue（优先队列）。详细阐述了它们的定义、底层实现原理（如 Stack 基于 deque 实现 LIFO，Queue 基于 deque 实现 FIFO）、核心成员函数接口（push、pop、top/front/back 等）以及模拟实现方法。通过最小栈、用栈实现队列等经典 OJ 题目示例，展示了这些数据结构在实际场景中的应用，并对比了 deque 作为底层容器的优势。
CoderByte 发布于 2026/2/5 更新于 2026/4/18 C++ STL 容器适配器：Stack、Queue 及 Priority Queue 详解
1. Stack 的介绍
Stack 的文档介绍
这是 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，因为它在两端插入/删除的效率很高，是最优选择。
2. Stack 类的构造函数 (Constructor) 声明
这是 C++ 标准库中 std::stack 构造函数的官方文档说明。
1️⃣ 构造函数签名
explicit 微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown转HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
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）。
ctnr: 这是底层容器的对象，container_type 是 stack 模板的第二个参数 Container 的类型别名（比如默认是 deque<T>）。你可以通过这个参数，用一个已有的容器来初始化栈。alloc: 这是分配器对象，用于底层容器的内存分配。这个参数仅在分配器类型满足 uses_allocator::value == true 时才会生效，一般日常开发中很少用到。拷贝构造 (隐含说明) : 文档最后一行提到的'A stack of the same type…'，指的是支持用另一个同类型的 stack 来构造新的栈（即拷贝构造）。
3. Stack 的成员函数
3.1 Empty 介绍
这是 C++ 标准库中 std::stack::empty 成员函数的官方文档说明。
bool: 返回值是布尔类型，表示栈是否为空。const: 这是一个只读成员函数 ，调用时不会修改栈的任何内容。 2️⃣ 核心功能
这个函数的作用是判断栈是否为空 （即栈中元素的数量是否为 0）。因为 stack 是容器适配器，它的 empty() 本质上是调用了底层容器 （比如默认的 deque）的 empty() 方法来实现的。
参数 : 无 (none)，调用时不需要传入任何参数。返回值 :
true: 栈为空（底层容器的大小为 0）。false: 栈不为空（底层容器包含至少一个元素）。
3.2 Size 介绍
这是 C++ 标准库中 std::stack::size 成员函数的官方文档说明。
size_type: 返回值类型，是一个无符号整数类型 （通常和 size_t 等价）。const: 这是一个只读成员函数，调用时不会修改栈的内容。 2️⃣ 核心功能
这个函数的作用是返回栈中当前的元素数量 。因为 stack 是容器适配器，它的 size() 本质上是调用了底层容器（比如默认的 deque）的 size() 方法来实现的。
参数 : 无 (none)。返回值 : 返回栈中元素的个数，也就是底层容器的元素数量，类型为无符号整数 size_type。
3.3 Top 介绍
这是 C++ 标准库中 std::stack::top 成员函数的官方文档说明。
value_type& top () ;
const value_type& top () const
value_type& top();可读写引用 ，用于修改栈顶元素。const value_type& top() const;只读引用 ，仅用于读取，不能修改。 2️⃣ 核心功能
这个函数的作用是返回栈顶元素的引用 。因为栈是后进先出（LIFO）的容器，栈顶元素就是最后插入的那个元素。它本质上是调用了底层容器（比如默认的 deque）的 back() 方法来实现的。
3️⃣ 关键注意事项
调用 top() 前，必须先用 empty() 判断栈是否为空！如果栈为空时调用 top()，会触发未定义行为 （通常导致程序崩溃）。
3.4 Push 介绍
这是 C++ 标准库中 std::stack::push 成员函数的官方文档说明。
void push (const value_type& val)
void: 无返回值，执行入栈操作后不返回任何内容。const value_type& val: 参数是要入栈的元素的const 引用 ，避免拷贝开销，同时保证不会修改传入的原始值。 2️⃣ 核心功能
这个函数的作用是在栈顶插入一个新元素 ，新元素的内容是参数 val 的副本。因为 stack 是容器适配器，它的 push() 本质上是调用了底层容器（比如默认的 deque）的 push_back() 方法，在容器的尾部（也就是栈的顶部）插入元素。
3️⃣ 关键对比
push() 是通过拷贝元素 入栈，如果你想更高效地直接在栈顶构造元素（避免拷贝），可以使用 emplace() 方法。
3.5 Emplace 介绍
这是 C++ 标准库中 std::stack::emplace 成员函数的官方文档说明。
template <class ... Args> void emplace (Args&&... args)
模板可变参数 : class... Args 和 Args&&... args 是 C++11 引入的可变参数模板和完美转发语法，用来接收任意数量、任意类型的参数，并原封不动地转发给元素的构造函数。 2️⃣ 核心功能
这个函数的作用是在栈顶原地构造并插入一个新元素 。和 push() 不同：
push() 是先构造一个临时元素，再将其拷贝/移动到栈顶；emplace() 则直接在栈顶的内存位置上，用传入的参数构造元素，完全避免了拷贝或移动的开销，效率更高。
3.6 Pop 介绍
这是 C++ 标准库中 std::stack::pop 成员函数的官方文档说明。
void: 无返回值，执行出栈操作后不返回任何内容。 2️⃣ 核心功能
这个函数的作用是移除栈顶的元素 ，并将栈的大小减 1。被移除的元素是最后一个入栈的元素（符合后进先出规则），它的值可以在调用 pop() 前通过 stack::top() 获取。
⚠️ 最容易踩的坑 ：
pop() 不返回被删除的元素：新手常误以为 pop() 会返回栈顶值，实际它仅删除元素。如果需要获取被删除的值，必须先调用 top() 读取，再调用 pop() 删除。空栈调用 pop() 会崩溃 ：调用 pop() 前，必须先用 empty() 判断栈是否为空，否则会触发未定义行为（通常导致程序崩溃）。
3.7 Swap 介绍
这是 C++ 标准库中 std::stack::swap 成员函数的官方文档说明。
void swap (stack& x) noexcept ()
noexcept: 该函数是否抛出异常，取决于底层容器的 swap 操作是否是 noexcept （比如默认底层容器 deque 的 swap 是 noexcept，因此 stack 的 swap 也会是 noexcept）。 2️⃣ 核心功能
这个函数的作用是交换当前栈和参数栈 x 的全部内容 。因为 stack 是容器适配器，它的 swap 本质上是调用了底层容器的非成员 swap 函数，直接交换两个栈的底层容器（比如默认的 deque），这个过程通常是 O(1) 时间复杂度（仅交换底层容器的内部指针，不拷贝元素），效率非常高。
4. 关于 Stack 的一些 OJ 题目
4.1 最小栈 class MinStack {
public :
MinStack () {}
void push (int val) 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;
};
4.2 栈的压入、弹出序列 class Solution {
public :
bool IsPopOrder (vector<int >& pushV, vector<int >& popV) 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 ();
}
};
4.3 验证栈序列 class Solution {
public :
bool validateStackSequences (vector<int >& pushed, vector<int >& popped) 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 ();
}
};
4.4 用栈操作构建数组 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;
}
};
4.5 栈排序 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 (); }
};
5. Stack 核心框架接口的模拟实现 #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) push_back (val); }
void push (T&& val) push_back (move (val)); }
void pop () if (!empty ()) {
_con.pop_back ();
}
}
private :
Container _con;
};
int main () int > st1;
st1. push (10 ); st1. push (20 ); st1. push (30 );
cout << "栈大小：" << st1. size () << endl;
cout << "栈顶元素：" << st1. top () << endl;
st1. pop ();
cout << "出栈后栈顶：" << st1. top () << endl;
return 0 ;
}
6. Queue 介绍 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 作为底层容器。 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()获取队列元素个数
7. Queue 类的构造函数 (Constructor) 声明
这是 C++ 标准库中 std::queue 构造函数的官方文档。
explicit queue (const container_type& ctnr = container_type())
explicitcontainer_typeContainer（默认是 std::deque<T>）。ctnr
8. Queue 的成员函数
8.1 Empty 介绍 用于判断队列是否为空 。本质是检查队列的大小是否为 0。时间复杂度为 O(1) 。
8.2 Size 介绍 用于获取队列中当前的元素数量 。时间复杂度为 O(1) 。
8.3 Front 介绍 value_type& front () ;
const value_type& front () const 用于访问队列的队首元素 。注意：如果队列为空时调用 front()，会触发未定义行为。
8.4 Back 介绍 value_type& back () ;
const value_type& back () const 用于访问队列的队尾元素 。注意：如果队列为空时调用 back()，会触发未定义行为。
8.5 Push 介绍 void push (const value_type& val) 用于在队列的队尾插入一个新元素 。时间复杂度为 O(1) 。
8.6 Emplace 介绍 template <class ... Args> void emplace (Args&&... args) 用于在队列的队尾原地构造 一个新元素。比 push 更高效。
8.7 Pop 介绍 用于移除队列的队首元素 。注意：pop() 仅删除队首元素，不会返回被删除的元素值 。
8.8 Swap 介绍 void swap (queue& x) noexcept 用于交换当前队列与另一个同类型队列的全部内容 。时间复杂度通常为 O(1) 。
9. 关于 Queue 的一些 OJ 题目
9.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) 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 (); }
};
9.2 用队列实现栈 class MyStack {
private :
queue<int > q1;
queue<int > q2;
public :
MyStack () {}
void push (int x) 2. push (x);
while (!q1. empty ()) {
q2. push (q1.f ront());
q1. pop ();
}
swap (q1, q2);
}
int pop () int val = q1.f ront();
q1. pop ();
return val;
}
int top () return q1.f ront(); }
bool empty () return q1. empty (); }
};
9.3 设计循环双端队列 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 () if (isEmpty ()) return false ;
rear = (rear - 1 + capacity) % capacity;
return true ;
}
int getFront () return isEmpty () ? -1 : data[front]; }
int getRear () return isEmpty () ? -1 : data[(rear - 1 + capacity) % capacity]; }
bool isEmpty () return front == rear; }
bool isFull () return (rear + 1 ) % capacity == front; }
};
9.4 设计前中后队列 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) 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) push_back (val); balance (); }
int popFront () if (left.empty () && right.empty ()) return -1 ;
int val;
if (!left.empty ()) { val = left.front (); left.pop_front (); }
else { val = right.front (); right.pop_front (); }
balance ();
return val;
}
int popMiddle () if (left.empty () && right.empty ()) return -1 ;
int val = left.back ();
left.pop_back ();
balance ();
return val;
}
int popBack () if (left.empty () && right.empty ()) return -1 ;
int val;
if (!right.empty ()) { val = right.back (); right.pop_back (); }
else { val = left.back (); left.pop_back (); }
balance ();
return val;
}
};
9.5 有序队列
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;
}
}
};
10. Queue 核心框架接口的模拟实现 #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) push_back (val); }
void push (T&& val) push_back (move (val)); }
void pop () if (!empty ()) {
_con.pop_front ();
}
}
void swap (Queue& other) noexcept swap (other._con); }
private :
Container _con;
};
int main () int > q1;
q1. push (10 ); q1. push (20 ); q1. push (30 );
cout << "队列大小：" << q1. size () << endl;
cout << "队首元素：" << q1.f ront() << endl;
cout << "队尾元素：" << q1. back () << endl;
q1. pop ();
cout << "出队后队首：" << q1.f ront() << endl;
return 0 ;
}
11. Priority Queue 的介绍 1️⃣ 本质 : 带优先级的容器适配器
std::priority_queue 是一个容器适配器 ，它不直接存储数据，而是封装了一个底层容器（默认是 std::vector），并通过堆（heap）算法维护元素的优先级顺序，保证队首（堆顶）始终是优先级最高的元素（默认是最大的元素）。
template <class T , class Container = vector, class Compare = less> class priority_queue;
T: 队列存储的元素类型。Container: 底层容器类型（默认是 std::vector），需要支持随机访问迭代器。Compare: 优先级比较规则（默认是 less<T>，即构建大顶堆；若改为 greater<T>，则构建小顶堆）。
优先级保证 : 队首元素始终是当前队列中优先级最高的元素。堆结构维护 : 插入/删除元素时，自动调用堆算法维护堆的结构，时间复杂度为 O(log n)。访问限制 : 只能访问队首（堆顶）元素，无法随机访问其他位置的元素。
12. Priority Queue 类的构造函数 (Constructor) 声明
这是 C++ 标准库中 std::priority_queue 构造函数的官方文档。
初始化版本 : explicit priority_queue (const Compare& comp = Compare(), const Container& ctnr = Container());范围初始化版本 : template <class InputIterator> priority_queue (InputIterator first, InputIterator last, ...)
comp: 堆的排序比较对象。默认是 less<T>（大顶堆），若传入 greater<T> 则构建小顶堆。ctnr: 底层容器对象。默认是 vector<T>。first, last: 输入迭代器，指向要插入的元素范围。 3️⃣ 底层实现逻辑
无论哪个版本的构造函数，最终都会执行以下步骤：
初始化内部的比较对象和底层容器。
若使用范围版本，先将迭代器范围内的元素插入底层容器。
调用 make_heap 算法，将底层容器转换为堆结构。
13. Priority Queue 的成员函数
13.1 Empty 介绍 用于判断优先队列是否为空 。时间复杂度为 O(1) 。
13.2 Size 介绍 用于获取优先队列中当前的元素总数 。时间复杂度为 O(1) 。
13.3 Top 介绍 const value_type& top () const 用于访问优先队列的队首（堆顶）元素 。注意：如果队列为空时调用 top()，会触发未定义行为。
13.4 Push 介绍 void push (const value_type& val) 用于向优先队列中插入一个新元素 。插入后会自动维护堆的结构。时间复杂度为 O(log n) 。
13.5 Emplace 介绍 template <class ... Args> void emplace (Args&&... args) 用于在优先队列的底层容器中原地构造一个新元素 。效率高于 push。
13.6 Pop 介绍 用于删除优先队列的队首（堆顶）元素 。时间复杂度为 O(log n) 。
13.7 Swap 介绍 void swap (priority_queue& x) noexcept 用于完整交换当前优先队列与另一个同类型队列的全部内容 。时间复杂度通常为 O(1) 。
14. 关于 Priority Queue 的一些 OJ 题目
14.1 数组中第 K 个大的元素 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 ();
}
};
14.2 前 K 个高频元素 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;
}
};
14.3 数据流中的第 K 大元素 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 ();
}
};
14.4 最接近原点的 K 个点 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;
}
};
15. Priority Queue 核心框架接口的模拟实现 #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 (const T& val) push_back (val);
push_heap (_con.begin (), _con.end (), _comp);
}
void pop () if (empty ()) abort ();
pop_heap (_con.begin (), _con.end (), _comp);
_con.pop_back ();
}
void swap (PriorityQueue& other) noexcept using std::swap;
swap (_con, other._con);
swap (_comp, other._comp);
}
private :
Container _con;
Compare _comp;
};
int main () int > pq1;
pq1. push (30 ); pq1. push (10 ); pq1. push (20 );
cout << "大顶堆堆顶：" << pq1. top () << endl;
pq1. pop ();
cout << "出队后堆顶：" << pq1. top () << endl;
return 0 ;
}
16. 适配器介绍 适配器是一种设计模式 ,核心作用是接口转换 :它将一个已有类/对象的接口，转换成另一个符合业务需求的接口，让原本接口不兼容的组件可以协同工作。
在 C++ 标准库中，最常见的是容器适配器 （如 queue、stack、priority_queue），此外还有迭代器适配器（如 reverse_iterator）、函数适配器（如 bind）等。
1️⃣ 核心特点 : 以容器适配器为例
C++ 中的容器适配器不直接管理存储 ,而是封装一个底层容器（如 vector、deque），并通过接口适配，对外提供更简洁、场景化的操作。
封装底层容器 : 复用现有容器的存储能力。适配接口 : 对外提供符合特定场景的极简接口，隐藏底层容器的复杂细节。 2️⃣ 典型示例 : priority_queue 作为适配器
priority_queue 是基于堆的容器适配器 ，核心适配逻辑：
底层容器 : 默认封装 vector。堆算法适配 : 通过 make_heap、push_heap、pop_heap 等算法。比较器适配 : 通过自定义比较器实现大顶堆/小顶堆的切换。
17. Deque 的简单介绍 (了解) 虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为 stack 和队列只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque。
Deque（双端队列） : 是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)。
17.1 为什么选择 Deque 作为 Stack 和 Queue 的底层默认容器？
Stack 和 Queue 不需要遍历（因此没有迭代器），只需要在固定的一端或者两端进行操作。
在 Stack 中元素增长时，Deque 比 Vector 的效率高（扩容时不需要搬移大量数据）；Queue 中的元素增长时，Deque 不仅效率高，而且内存使用率高。
结合了 Deque 的优点，而完美的避开了其缺陷。
特性 Deque Vector List 内存连续性 非连续（分段连续） 连续 非连续（节点式） 随机访问 支持（O(1)，略慢） 支持（O(1)，最快） 不支持 队首增删 O(1) O(n) O(1) 队尾增删 O(1) O(1)（扩容时 O(n)） O(1)
