一.stack基本概念

栈（Stack）是一种常见的线性数据结构，遵循后进先出（Last-In-First-Out，LIFO）的原则。类似于我们在现实生活中堆叠书本或盘子的方式，最后放入的元素最先被取出。

在栈中，元素的插入操作（入栈）是在栈顶进行，而元素的删除操作（出栈）也是在栈顶进行。这使得栈成为一种适合于后续操作依赖于最近插入的元素的数据结构。栈通常具有以下两个基本操作：

1. 入栈（Push）：将元素添加到栈顶。
2. 出栈（Pop）：从栈顶移除一个元素。

除了基本的入栈和出栈操作，栈还具有以下重要概念：

• 栈顶（Top）：指向栈中最新插入的元素的指针或引用。这是我们可以进行出栈和入栈操作的位置。
• 栈底（Bottom）：指向栈中最先插入的元素的指针或引用。
• 空栈（Empty Stack）：不包含任何元素的栈。
• 满栈（Full Stack）：当栈达到其最大容量时，无法再插入新的元素。

栈可以使用数组或链表等数据结构来实现。在 C++ 标准库中，我们可以使用 std::stack 模板类来实现栈，它默认使用 std::deque 作为底层容器。

需要注意的是，栈是一种单向的数据结构，只能从栈顶插入和删除元素。如果需要在栈中间位置进行操作，可能需要转换为其他数据结构或使用额外的辅助数据结构。

栈在算法、语法分析、递归调用等各种场景中都有广泛的应用。它有助于实现各种基于后进先出顺序的问题和任务。

栈中只有顶端的元素才可以被外界使用，因此栈不允许有遍历行为

二.stack函数接口

当使用栈（std::stack）时，以下是一些重要的详细信息和注意事项：

• 包含头文件：要使用 std::stack，需要包含 <stack> 头文件。

• 栈的创建：可以通过下面的方式声明一个栈。

  std::stack<int> st;
  

  在上述示例中，int 是栈中元素的类型，可以根据需要替换为其他类型。

• 元素插入：可以使用 push 方法将元素压入栈顶。

  st.push(42);
  

  上述示例将整数 42 压入了栈顶。

• 元素访问：可以使用 top 方法访问栈顶元素的值。

  std::cout << st.top(); // 输出栈顶元素的值（不删除）
  

  注意，top 方法不会从栈中删除栈顶元素，只是返回栈顶元素的值。

• 元素删除：可以使用 pop 方法从栈中删除栈顶元素。

  st.pop();
  

  上述示例将栈顶元素从栈中删除。

• 栈的大小：可以使用 size 方法获取栈内元素的数量。

  std::cout << st.size(); // 输出栈中元素的个数
  

• 栈的判空：可以使用 empty 方法判断栈是否为空。

  if (st.empty()) {
      // 栈为空
  } else {
      // 栈不为空
  }
  

  empty 方法在栈为空时返回 true，否则返回 false。

整理成表格：

在上述表格中，value_type 是栈中元素的类型。请注意，栈类 std::stack 是基于其他容器实现的，默认情况下使用 std::deque 作为底层容器。可以使用其他容器，如 std::vector 或 std::list，作为底层容器来实现栈。

三.queue基本概念

队列（Queue）是一种常见的线性数据结构，遵循先进先出（First-In-First-Out，FIFO）的原则。它类似于我们在现实生活中排队等待的场景，先来的人先被服务。

在队列中，元素的插入操作（入队）是在队列的尾部进行，而元素的删除操作（出队）是在队列的头部进行。这使得队列成为一种适合于等待行列或任务调度的数据结构。队列通常有以下两个基本操作：

1. 入队（Enqueue）：将元素添加到队列的末尾（尾部）。
2. 出队（Dequeue）：从队列的头部移除一个元素。

除了基本的入队和出队操作，队列还具有以下重要概念：

• 队列头部（Front）：指向队列中第一个元素的指针或引用。这是我们可以出队的位置。
• 队列尾部（Back）：指向队列中最后一个元素的指针或引用。这是我们可以入队的位置。
• 空队列（Empty Queue）：不包含任何元素的队列。
• 满队列（Full Queue）：当队列达到其最大容量时，无法再入队新的元素。

队列可以使用线性数组、链表或其他数据结构来实现。在C++标准库中，我们可以使用 std::queue 模板类来实现队列，它默认使用 std::deque 作为底层容器。

需要注意的是，队列是一种单向的数据结构，只能从队列的头部删除元素，从队列的尾部插入元素。如果需要在队列中间位置进行操作，可能需要转换为其他数据结构或使用额外的辅助数据结构。

队列在算法、操作系统、网络通信等领域中都有广泛的应用。它有助于实现各种基于顺序处理的问题和任务调度。

四.queue函数接口

构造函数和析构函数：

• queue()：默认构造函数，创建一个空的队列。
• queue(const queue& other)：复制构造函数，创建一个新的队列并复制另一个队列的内容。
• ~queue()：析构函数，销毁队列。

运算符重载：

• operator=：赋值运算符，将一个队列的内容赋值给另一个队列。
• operator==：比较运算符，判断两个队列是否相等。
• operator!=：比较运算符，判断两个队列是否不相等。

成员函数：

• push(value_type& value)：将元素 value 插入队列的尾部。
• pop()：从队列的头部移除一个元素。
• front()：返回队列头部的元素。
• back()：返回队列尾部的元素。
• empty()：判断队列是否为空，如果为空则返回 true，不为空则返回 false。
• size()：返回队列中元素的个数。
• swap(queue& other)：交换两个队列的内容。

请注意，value_type 是队列中元素的类型。默认情况下，std::queue 是使用 std::deque 作为底层容器来实现的，但也可以使用其他容器，如 std::list 或 std::vector。如果需要在队列中访问或修改中间元素，则需要采用其他方式，比如遍历队列实现相关操作。

整理成表格：

五.priority_queue基本概念

std::priority_queue 是 C++ 标准库中的一个模板类，用于实现优先队列（Priority Queue）。优先队列是一种特殊的队列数据结构，它根据元素的优先级自动进行排序，优先级高的元素排在前面。默认情况下，std::priority_queue 使用最大堆（max heap）来实现。

以下是 std::priority_queue 的基本概念：

• 元素的优先级由比较函数（Comparator）确定。对于基本数据类型（如整数、浮点数），可以使用默认的比较函数（std::less）来进行比较。对于自定义类型，需要提供比较函数或比较函数对象。
• 元素在被插入到优先队列时会自动根据优先级进行排序，优先级高的元素会放在前面。当需要从队列中取出元素时，优先队列会返回当前优先级最高的元素，并将其移出队列。

std::priority_queue 支持以下常用的操作：

• std::priority_queue<T>：创建一个空的优先队列，元素类型为 T。
• std::priority_queue<T, Container>：创建一个空的优先队列，元素类型为 T，使用容器 Container 来存储元素。
• push(element)：将元素 element 插入到优先队列中，根据元素的优先级进行排序。
• pop()：移除队列中优先级最高的元素（堆顶元素）。
• top()：获取当前队列中优先级最高的元素（堆顶元素）。
• empty()：检查优先队列是否为空，返回布尔值。
• size()：返回优先队列中元素的个数。
• swap(other_queue)：交换两个优先队列的内容。

需要注意的是，默认情况下，std::priority_queue 是最大堆，即优先级高的元素位于堆的顶部。如果需要最小堆，可以通过提供自定义的比较函数或比较函数对象来实现。

上述操作和概念使得 std::priority_queue 成为在需要根据优先级对元素进行排序和处理的场景中非常有用的工具。

六.priority_queue建立

要使用 std::priority_queue，你需要包含头文件 queue，该头文件中已经定义了优先队列模板类。

以下是使用 std::priority_queue 构建优先队列的详细步骤：

1. 包含头文件：

#include <queue>

2. 定义元素类型和比较函数（可选）：

如果元素类型是基本数据类型（如整数、浮点数），则可以直接使用默认的比较函数 std::less 进行比较。如果元素类型是自定义类型，你需要提供一个能够比较元素优先级的比较函数或比较函数对象。

bool compareFunction(const T& a, const T& b) {
    // 自定义比较规则，返回 true 表示 a 的优先级高于 b
    // 或者使用逆序，返回 true 表示 a 的优先级低于 b
    // 比较函数应该根据元素类型的实际情况进行定义
}

3. 声明优先队列对象：

std::priority_queue<T, Container, Compare> pq;

• T：元素类型。
• Container：可选参数，指定容器类型，默认为 std::vector<T>。
• Compare：可选参数，指定比较函数或比较函数对象，默认为 std::less<T>。

示例：

std::priority_queue<int> pq; // 创建一个存储 int 类型的优先队列，默认使用 std::vector 作为底层容器，使用 std::less 进行比较

std::priority_queue<double, std::vector<double>, std::greater<double>> pq; // 创建一个存储 double 类型的优先队列，使用 std::vector 作为底层容器，使用 std::greater 进行比较

bool compareFunction(const CustomType& a, const CustomType& b) {
    // 自定义比较函数的实现
}

std::priority_queue<CustomType, std::vector<CustomType>, decltype(compareFunction)*> pq(compareFunction); // 创建一个存储自定义类型 CustomType 的优先队列，使用 std::vector 作为底层容器，使用自定义的 compareFunction 进行比较

4. 插入元素：

使用 push 方法将元素插入到优先队列中，并根据元素的优先级进行排序。

pq.push(element);

示例：

pq.push(3);
pq.push(1);
pq.push(4);

5. 删除元素：

使用 pop 方法移除优先队列中优先级最高的元素（堆顶元素）。

pq.pop();

6. 访问顶部元素：

使用 top 方法获取当前优先队列中优先级最高的元素（堆顶元素）。

T topElement = pq.top();

7. 检查优先队列是否为空：

使用 empty 方法判断优先队列是否为空。

if (pq.empty()) {
    // 优先队列为空
}

8. 获取优先队列的大小：

使用 size 方法获取当前优先队列中的元素个数。

int size = pq.size();

9. 交换优先队列的内容：

使用 swap 方法交换两个优先队列的内容。

std::priority_queue<T, Container, Compare> otherPQ;
pq.swap(otherPQ);

整理成表格：

构造函数（了解即可）

下面是 std::priority_queue 的构造函数及相关参数的表格：

注意：上述表格中的 Compare 是比较函数或比较函数对象类型，Container 是用于存储元素的容器类型，Alloc 是分配器类型。如果未提供相应的参数，默认使用 std::less 进行比较，使用 std::vector 作为容器，使用 std::allocator 进行分配。