C++ STL 容器适配

栈的操作特性：栈的所有操作都集中在一端（尾部）。push 对应 push_back，pop 对应 pop_back，top 对应 back。
容器性能对比：
- std::vector：push_back, pop_back, back 操作的均摊时间复杂度都是 O(1)，性能极好。但是，当 vector 空间不足时，push_back 会触发内存重新分配、元素拷贝/移动，可能导致性能抖动。
- std::list：双向链表，push_back, pop_back 都是 O(1) 复杂度，且不会有内存重新分配的问题。但它的缺点是内存开销更大（每个节点都有额外的指针开销），并且内存非连续，导致缓存命中率较低。
- std::deque：双端队列，是 vector 和 list 的折中。它在尾部进行 push_back 和 pop_back 操作的效率非常高（均摊 O(1)），几乎和 vector 一样快。与 vector 相比，它的扩容代价更小（只需分配新的内存块，无需移动所有元素），性能表现更平滑。与 list 相比，它的内存是分段连续的，缓存友好性更好，内存开销也更小。

结论：deque 在提供高效尾部操作的同时，避免了 vector 可能的大规模内存拷贝和 list 的高内存开销，因此是 stack 最均衡、最合适的默认选择。

代码示例

#include <iostream>
#include <stack>
#include <vector>

int main() {
    // 默认使用 deque
    std::stack<int> s1;
    s1.push(10);
    s1.push(20);

    std::cout << "Top element is: " << s1.top() << std::endl; // 输出 20
    s1.pop();
    std::cout << "Top element after pop is: " << s1.top() << std::endl; // 输出 10

    // 使用 vector作为底层容器
    std::stack<int, std::vector<int>> s2;
    s2.push(100);
    return 0;
}

3. `std::queue` (队列) - 先进先出 (FIFO)

队列的行为模式是 FIFO (First-In, First-Out)，就像排队买票，最先来的人最先买到票离开。

核心接口

push(const T& value): 在队尾添加一个元素。
pop(): 移除队首元素（不返回值）。
front(): 返回对队首元素的引用。
back(): 返回对队尾元素的引用。
empty(): 检查队列是否为空。
size(): 返回队列中元素的数量。

底层容器

默认容器: std::deque
可选容器: std::list

面试深挖：为什么默认使用 `deque` 且 `vector` 不能用？

队列的操作特性：队列需要在尾部插入 (push_back) 和头部删除 (pop_front)。
容器性能对比：
- std::deque：完美匹配！push_back 和 pop_front 的时间复杂度都是均摊 O(1)。
- std::list：同样完美匹配，push_back 和 pop_front 复杂度也是 O(1)。但如前所述，有内存开销和缓存性能问题。
- std::vector：完全不适用。vector 的 push_back 效率高，但它没有 pop_front 接口。如果手动实现（erase(begin())），每次删除头部元素都需要移动后续所有元素，时间复杂度为 O(N)，效率极低。

结论：vector 无法高效地支持队列的 pop 操作，因此被排除。deque 相比 list 在内存和缓存方面更有优势，所以成为 queue 的默认底层容器。

代码示例

#include <iostream>
#include <queue>
#include <list>

int main() {
    // 默认使用 deque
    std::queue<int> q1;
    q1.push(10); // [10]
    q1.push(20); // [10, 20]
    q1.push(30); // [10, 20, 30]

    std::cout << "Front element is: " << q1.front() << std::endl; // 输出 10
    std::cout << "Back element is: " << q1.back() << std::endl;  // 输出 30

    q1.pop(); // 移除 10，队列变为 [20, 30]
    std::cout << "Front element after pop is: " << q1.front() << std::endl; // 输出 20

    // 使用 list 作为底层容器
    std::queue<int, std::list<int>> q2;
    q2.push(100);
    return 0;
}

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

优先队列是一种特殊的队列，它不遵循 FIFO 原则，而是根据元素的优先级进行出队。每次 pop() 操作移除的都是当前队列中优先级最高的元素。

默认情况下，priority_queue 是一个最大堆 (Max-Heap)，即数值越大的元素优先级越高。

核心接口

push(const T& value): 添加一个元素，并根据其优先级在堆中排序。
pop(): 移除优先级最高的元素。
top(): 返回对优先级最高的元素的常引用。
empty(): 检查是否为空。
size(): 返回元素数量。

底层容器与比较器

默认容器: std::vector
可选容器: std::deque
比较器 (Compare):
- 默认: std::less<T>，用于构建最大堆。
- 可自定义: 可以传入一个比较函数或函数对象来定义优先级。

面试深挖：`priority_queue` 深度解析

为什么默认用 vector？ priority_queue 的内部实现是堆 (Heap) 数据结构。堆算法（如 push_heap, pop_heap）非常适合在连续内存上操作，因为可以通过索引 i 快速计算出父节点 ((i-1)/2) 和子节点 (2i+1, 2i+2) 的位置。vector 提供了完美的连续内存，因此是最高效、最自然的选择。deque 也可以用，但由于其分段连续的特性，性能略逊于 vector。
如何创建最小堆 (Min-Heap)？ 要让数值越小的元素优先级越高，需要提供一个不同的比较器。
- 方法：将默认的 std::less<T> 替换为 std::greater<T>。
- 语法：std::priority_queue<T, std::vector<T>, std::greater<T>> pq;

如何为自定义类型定义优先级？ 假设有一个 Task 结构体，我们希望优先级高的 Task 先被处理。

方法一：重载 < 运算符 (推荐，最简洁)

struct Task {
    int priority;
    std::string name;
    // 重载 <, priority_queue 默认使用 less<Task>, 会调用此运算符
    bool operator<(const Task& other) const {
        return this->priority < other.priority; // priority 越大，优先级越高
    }
};
std::priority_queue<Task> tasks;

方法二：自定义比较器 (Functor) (最灵活)

struct Task {
    int priority;
    std::string name;
};
struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        // 返回 true 表示 a 的优先级低于 b
        return a.priority < b.priority;
    }
};
std::priority_queue<Task, std::vector<Task>, CompareTask> tasks;

代码示例

#include <iostream>
#include <queue>
#include <vector>
#include <string>

// 自定义类型
struct Task {
    int priority;
    std::string name;
};

// 自定义比较器
struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        // 返回 true 表示 a 的优先级“低于” b
        return a.priority < b.priority;
    }
};

int main() {
    // 1. 默认最大堆
    std::priority_queue<int> max_heap;
    max_heap.push(30);
    max_heap.push(100);
    max_heap.push(50);
    std::cout << "Max-heap top: " << max_heap.top() << std::endl; // 输出 100

    // 2. 最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    min_heap.push(30);
    min_heap.push(100);
    min_heap.push(50);
    std::cout << "Min-heap top: " << min_heap.top() << std::endl; // 输出 30

    // 3. 自定义类型和比较器
    std::priority_queue<Task, std::vector<Task>, CompareTask> tasks;
    tasks.push({5, "Fix bug"});
    tasks.push({10, "Release new version"});
    tasks.push({2, "Write documentation"});
    std::cout << "Highest priority task: " << tasks.top().name << std::endl; // 输出 Release new version
    return 0;
}

5. 面试总结与快速回顾

特性	`std::stack`	`std::queue`	`std::priority_queue`
行为	LIFO (后进先出)	FIFO (先进先出)	优先级出队 (默认最大堆)
核心操作	`push()`, `pop()`, `top()`	`push()`, `pop()`, `front()`, `back()`	`push()`, `pop()`, `top()`
默认底层容器	`std::deque`	`std::deque`	`std::vector`
为何是默认？	高效尾部操作，性能平滑	高效头、尾操作	堆算法需要连续内存以获得最佳性能
常见应用	函数调用栈、括号匹配、撤销操作	BFS 算法、任务队列、事件处理	Dijkstra 算法、任务调度、Top K 问题