一、stack的使用

1. stack 简介

stack 是 C++ 标准库中的容器适配器，它提供了一种后进先出（LIFO, Last In First Out） 的数据结构。
在 stack 中，元素的插入（压栈）和删除（弹栈）都只能在容器的一端（栈顶）进行，因此它非常适合于需要“回溯”或“逆序处理”的场景，例如函数调用栈、表达式求值、括号匹配等。

stack 默认基于 deque 实现，但也可以显式指定底层容器（如 vector 或 list）。

2. stack的底层实现

stack 本身并不直接管理内存，而是通过封装底层容器来实现功能。

它要求底层容器支持以下操作：

• empty()：判断栈是否为空

• size()：返回元素个数

• top()：获取栈顶元素

• push_back()：在尾部（栈顶）插入元素

• pop_back()：在尾部（栈顶）删除元素

C++ 标准库中的 deque、vector 和 list 都满足这些要求。
默认情况下，stack 使用 deque 作为其底层容器。

3. stack 的常用接口

函数说明	接口说明
stack()	构造一个空的栈
empty()	判断栈是否为空，返回 true 或 false
size()	返回栈中元素的个数
top()	返回栈顶元素的引用（不删除）
push(val)	将元素 val 压入栈顶
pop()	弹出栈顶元素（无返回值）

⚠️ 注意：pop() 只删除栈顶元素，不返回其值；若要获取栈顶元素，需先使用 top()。

4. 代码示例

#include <iostream>
#include <stack>

int main() {
    std::stack<int> st;

    // 压栈
    st.push(10);
    st.push(20);
    st.push(30);

    // 访问栈顶并弹出
    while (!st.empty()) {
        std::cout << st.top() << " ";  // 输出：30 20 10
        st.pop();
    }

    return 0;
}

二、queue的使用

1. 什么是 queue？

queue 是一种容器适配器，专门用于实现 先进先出（FIFO） 的数据结构。
在队列中，元素从队尾插入，从队头移除，符合“先来先服务”的逻辑。

2. queue 的底层实现

queue 本身并不直接管理内存，而是通过封装底层容器来实现功能。
它要求底层容器支持以下操作：

• empty()：判断队列是否为空

• size()：返回元素个数

• front()：获取队头元素

• back()：获取队尾元素

• push_back()：在尾部插入元素

• pop_front()：在头部删除元素

C++ 标准库中的 deque 和 list 都满足这些要求。
默认情况下，queue 使用 deque 作为其底层容器。

3. queue 常用接口

函数声明	功能说明
queue()	构造一个空队列
empty()	判断队列是否为空
size()	返回队列中元素个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push(val)	在队尾插入元素 val
pop()	弹出队头元素（无返回值）

4. 代码示例

#include <iostream>
#include <queue>
using namespace std;

int main() {
    // 1. 构造空队列
    queue<int> q;
    
    // 2. push: 入队（队尾插入）
    q.push(10);
    q.push(20);
    q.push(30);
    
    // 3. size: 获取元素个数
    cout << "队列大小: " << q.size() << endl;  // 输出: 3
    
    // 4. front / back: 获取队头和队尾
    cout << "队头: " << q.front() << endl;     // 输出: 10
    cout << "队尾: " << q.back() << endl;      // 输出: 30
    
    // 5. pop: 出队（删除队头）
    q.pop();  // 删除 10
    cout << "pop后队头: " << q.front() << endl; // 输出: 20
    
    // 6. empty: 判断是否为空
    cout << "是否为空: " << (q.empty() ? "是" : "否") << endl; // 输出: 否
    
    // 7. 遍历队列（pop方式）
    cout << "遍历队列: ";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;  // 输出: 20 30
    
    return 0;
}


//运行结果


队列大小: 3
队头: 10
队尾: 30
pop后队头: 20
是否为空: 否
遍历队列: 20 30

三、priority_queue的使用

1. 什么是 priority_queue？

在 C++ 标准库中，priority_queue 是一种极为实用的容器适配器。它并非普通的队列，而是一个自带排序规则的“特权队列”——它的队首元素永远是当前队列中优先级最高（即最大或最小）的元素。这一特性使其非常适合用于堆排序、任务调度、Dijkstra 算法等场景。

priority_queue 本质上是一个堆结构。默认情况下，它采用 vector 作为底层容器，并通过堆算法（make_heap、push_heap、pop_heap）自动维护元素顺序，确保队首始终是最大元素。

2. priority_queue的底层实现

priority_queue 本身并不直接管理内存，而是通过封装底层容器来实现功能，并在其基础上通过堆算法维护元素的优先级顺序。

它要求底层容器支持以下操作：

• empty()：判断优先队列是否为空

• size()：返回元素个数

• top()：获取优先级最高的元素（堆顶）

• push_back()：在尾部插入元素

• pop_back()：在尾部删除元素

此外，priority_queue 还依赖于以下堆操作：

• push_heap()：插入元素后调整堆结构

• pop_heap()：删除元素前调整堆结构

C++ 标准库中的 vector 和 deque 都满足这些要求。
默认情况下，priority_queue 使用 vector 作为其底层容器。

元素之间的优先级比较默认使用 std::less，即最大元素优先级最高；也可以通过自定义比较函数来实现最小堆或其他排序规则。

3. priority_queue常用接口

函数声明	功能说明
priority_queue() / priority_queue(first, last)	构造一个空优先队列，或通过迭代器范围初始化
empty()	判断队列是否为空
top()	返回堆顶元素（最大或最小）
push(x)	插入元素
pop()	删除堆顶元素

4. 基本使用示例

4.1 默认大堆

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

int main() {
    std::vector<int> v = {3, 2, 7, 6, 0, 4, 1, 9, 8, 5};
    std::priority_queue<int> q; // 默认最大堆

    for (int num : v) {
        q.push(num);
    }
    std::cout << "堆顶元素（最大）: " << q.top() << std::endl; // 输出 9
    return 0;
}

4.2 小堆实现

若要创建小堆，需指定比较方式为 greater：

std::priority_queue<int, std::vector<int>, std::greater<int>> q2(v.begin(), v.end());
std::cout << "堆顶元素（最小）: " << q2.top() << std::endl; // 输出 0

4.3 自定义类型的使用

如果优先队列中存放的是自定义类型（如 Date），则需要为该类型定义 < 运算符（用于大堆）或通过 greater 配合 < 实现小堆。

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 {
        if (_year != d._year) return _year < d._year;
        if (_month != d._month) return _month < d._month;
        return _day < d._day;
    }

    friend std::ostream& operator<<(std::ostream& os, const Date& d) {
        os << d._year << "-" << d._month << "-" << d._day;
        return os;
    }

private:
    int _year, _month, _day;
};

// 使用示例
void testDateQueue() {
    std::priority_queue<Date> maxHeap; // 大堆
    maxHeap.push(Date(2018, 10, 29));
    maxHeap.push(Date(2018, 10, 28));
    maxHeap.push(Date(2018, 10, 30));
    std::cout << "最大日期: " << maxHeap.top() << std::endl;

    std::priority_queue<Date, std::vector<Date>, std::greater<Date>> minHeap; // 小堆
    minHeap.push(Date(2018, 10, 29));
    minHeap.push(Date(2018, 10, 28));
    minHeap.push(Date(2018, 10, 30));
    std::cout << "最小日期: " << minHeap.top() << std::endl;
}

四、适配器及deque的介绍

1. 什么是适配器？

适配器模式是一种设计模式，它将一个类的接口转换成客户希望的另一个接口。
在 STL 中，stack 和 queue 并不是容器，而是容器适配器——它们是对底层容器的接口封装。

// stack 默认使用 deque
template <class T, class Container = deque<T>> class stack;

// queue 默认使用 deque
template <class T, class Container = deque<T>> class queue;

2. deque 的原理简介

deque（双端队列）是一种双开口的“连续”空间的数据结构，支持在头尾两端进行 O(1) 的插入和删除。

结构特点：

• 不是真正的连续空间，而是由多段连续的小空间拼接而成

• 底层类似于一个动态二维数组，通过一个“map”中控数组管理多个缓冲区

• 迭代器设计复杂，用于维护“整体连续”的假象

当 map 满载时，会重新分配更大的 map 空间（reallocate_map）

---

3. deque 的优缺点

✅ 优势：

• 头尾插入/删除效率高（O(1)），不需要搬移元素

• 扩容时不需要搬移大量数据（比 vector 高效）

• 空间利用率高于 list（无需存储额外指针）

❌ 缺陷：

• 遍历效率低：迭代器需频繁检查是否到达缓冲区边界

• 实际开发中，线性结构优先选择 vector 或 list

---

4. 为什么 stack 和 queue 默认使用 deque？

特性	说明
无需遍历	stack 和 queue 不提供迭代器，避开了 deque 的遍历劣势
头部操作高效	queue 需要 pop_front，deque 天然支持 O(1)
扩容成本低	比 vector 扩容更优，无需搬移全部元素
内存利用率高	比 list 更节省内存

✅ deque 完美结合了 vector 和 list 的部分优点，避开了它们的缺点，因此成为默认底层容器。

5. 模拟实现 stack 和 queue

stack 的简化实现（底层默认 deque）：

template<class T, class Con = deque<T>>
class stack {
public:
    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:
    Con _c;
};

queue 的简化实现（底层默认 deque）：

template<class T, class Con = deque<T>>
class queue {
public:
    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:
    Con _c;
};