一.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 进行分配。