移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——8.stackqueuepriority_queue（无习题）

#1024程序员节|征文#

C++ 中的 stack 和 queue 容器详细总结

1. 概述

C++ 标准模板库（STL）提供了一系列容器，其中 stack 和 queue 是两种常用的适配器容器。它们基于底层的序列容器（如 vector、deque）实现，分别用于支持栈和队列的操作模型。栈（stack）遵循“后进先出”（LIFO）的原则，而队列（queue）遵循“先进先出”（FIFO）的原则。本文将详细介绍这两种容器的特点、使用方法、实现机制及其应用场景。

2. stack 容器

2.1 什么是 stack？

stack 是一种基于“后进先出”（LIFO, Last In First Out）数据结构的容器。它的特点是只能在栈的顶部进行元素的插入和删除操作。栈的操作类似于现实中的叠盘子，最新添加的盘子在最上面，也最先被移除。

2.2 stack 的特点

• 后进先出（LIFO）：只能访问栈顶的元素，插入和删除也都只能在栈顶进行。
• 限制性操作：stack 只允许在栈顶插入（push）和删除（pop）元素，无法随机访问中间的元素。
• 适配器容器：stack 并非独立的容器，而是基于其他序列容器（如 deque、vector 或 list）实现的适配器。

2.3 stack 的常用操作

• push(value)：将元素压入栈顶。

#include <stack>
#include <iostream>int main() {std::stack<int> s;s.push(10);  // 将 10 压入栈顶s.push(20);  // 将 20 压入栈顶return 0;
}

• pop()：移除栈顶元素。

s.pop();  // 移除栈顶元素 20

• top()：访问栈顶元素。

int topElement = s.top();  // 获取栈顶元素 10

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

if (s.empty()) {std::cout << "栈为空" << std::endl;
}

• size()：返回栈中的元素个数。

std::cout << "栈的大小: " << s.size() << std::endl;

2.4 stack 的底层实现

stack 是一个容器适配器，底层通常使用 deque 作为默认的序列容器，也可以使用 vector 或 list。由于 stack 只暴露了栈的接口，底层的容器类型对外不可见。

以下代码展示了如何使用 deque 来实现一个 stack：

std::stack<int, std::deque<int>> s;  // 使用 deque 作为底层容器

stack 的默认实现是基于 deque，因为 deque 支持高效的头部和尾部插入与删除操作。而 vector 虽然也可以用来实现 stack，但在需要扩展时可能需要重新分配内存，性能可能不如 deque 稳定。

2.5 stack 的应用场景

• 函数调用管理：在编译器的实现中，stack 常被用来管理函数调用，包括参数传递、返回地址保存等。
• 表达式求值：在中缀表达式到后缀表达式的转换、后缀表达式的计算中，stack 都能起到重要的作用。
• 括号匹配：stack 常用于判断括号是否匹配的问题，可以高效地检查表达式中的括号是否正确闭合。
• 回溯问题：stack 也常用于深度优先搜索（DFS）等需要回溯的算法中。

2.6 stack 的优缺点

• 优点：
  • 操作简单，只需关注栈顶的元素。
  • 插入和删除操作的时间复杂度为 O(1)。
• 缺点：
  • 无法随机访问元素，限制了灵活性。
  • 只能通过 push 和 pop 操作进行数据操作。

3. queue 容器

3.1 什么是 queue？

queue 是一种基于“先进先出”（FIFO, First In First Out）数据结构的容器。它的特点是只能在队尾插入元素，在队头删除元素，类似于排队的过程，最先进入队列的元素最先被移除。

3.2 queue 的特点

• 先进先出（FIFO）：元素只能从队尾插入，从队头移除。
• 适配器容器：queue 和 stack 类似，也是基于其他序列容器（如 deque、list）实现的适配器。
• 限制性操作：queue 只允许在队尾插入和在队头移除，无法随机访问中间的元素。

3.3 queue 的常用操作

• push(value)：将元素添加到队尾。

#include <queue>
#include <iostream>int main() {std::queue<int> q;q.push(10);  // 将 10 添加到队尾q.push(20);  // 将 20 添加到队尾return 0;
}

• pop()：移除队头元素。

q.pop();  // 移除队头元素 10

• front()：访问队头元素。

int frontElement = q.front();  // 获取队头元素 20

• back()：访问队尾元素。

int backElement = q.back();  // 获取队尾元素 20

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

if (q.empty()) {std::cout << "队列为空" << std::endl;
}

• size()：返回队列中的元素个数。

std::cout << "队列的大小: " << q.size() << std::endl;

3.4 queue 的底层实现

queue 通常使用 deque 作为默认的底层容器，也可以使用 list。deque 是双端队列，支持高效的头尾操作，因此非常适合用于实现 queue。

以下代码展示了如何使用 list 作为底层容器实现一个 queue：

std::queue<int, std::list<int>> q;  // 使用 list 作为底层容器

3.5 queue 的应用场景

• 任务调度：queue 常用于任务调度中，例如打印任务、进程任务等，确保任务按照先后顺序执行。
• 广度优先搜索（BFS）：在图算法中，queue 常用于实现广度优先搜索，逐层访问节点。
• 缓冲区：queue 常用于实现缓冲区，保证数据的顺序处理，例如在多线程编程中用于生产者-消费者模型。

3.6 queue 的优缺点

• 优点：
  • 结构简单，保证元素按顺序被处理。
  • 插入和删除操作的时间复杂度为 O(1)。
• 缺点：
  • 无法随机访问元素。
  • 只支持从队尾插入和从队头移除，限制了灵活性。

4. priority_queue 容器

4.1 什么是 priority_queue？

priority_queue 是一种特殊的队列，其元素根据优先级进行排序。默认情况下，priority_queue 中的元素是按大顶堆（最大元素优先）进行排序的，即优先级最高的元素最先出队。

4.2 priority_queue 的特点

• 优先级排序：元素按优先级进行排序，最大或最小的元素优先出队。
• 基于堆实现：priority_queue 通常使用堆结构（如二叉堆）来实现，以保证元素的插入和删除操作具有对数级的时间复杂度。
• 只允许访问队头元素：与普通 queue 类似，priority_queue 只允许访问和移除队头元素，不能随机访问其他元素。

4.3 priority_queue 的常用操作

• push(value)：将元素添加到队列中，并根据优先级调整位置。

#include <queue>
#include <iostream>int main() {std::priority_queue<int> pq;pq.push(30);  // 将 30 添加到队列中pq.push(10);  // 将 10 添加到队列中pq.push(20);  // 将 20 添加到队列中return 0;
}

• pop()：移除优先级最高的元素。

pq.pop();  // 移除队头元素 30（最大值）

• top()：访问优先级最高的元素。

int topElement = pq.top();  // 获取优先级最高的元素 20

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

if (pq.empty()) {std::cout << "优先队列为空" << std::endl;
}

• size()：返回队列中的元素个数。

std::cout << "优先队列的大小: " << pq.size() << std::endl;

4.4 priority_queue 的底层实现

priority_queue 使用堆来实现，默认情况下是大顶堆（最大值优先），可以通过指定比较器来实现小顶堆。

以下代码展示了如何使用小顶堆来实现一个 priority_queue：

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;  // 小顶堆template<class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};   //仿函数，判断大小template<class T>class greater{public:bool operator()(const T& x, const T& y){return x > y;}};   //仿函数，判断大小
————————————————

如果元素为自定义类型，则需要用户自己重载仿函数

4.5 priority_queue 的应用场景

• 任务调度：在操作系统中，priority_queue 可以用于实现优先级调度，让优先级高的任务先执行。
• 最短路径算法：在图算法中，priority_queue 常用于 Dijkstra 算法，以找到权重最小的路径。
• 事件驱动模拟：在事件驱动的模拟系统中，priority_queue 可以根据事件的优先级处理事件，确保最重要的事件最先被处理。

4.6 priority_queue 的优缺点

• 优点：
  • 能够根据优先级高效地管理元素。
  • 插入和删除的时间复杂度为 O(log n)，适合处理大量需要排序的元素。
• 缺点：
  • 无法随机访问元素。
  • 只允许访问优先级最高的元素，限制了灵活性。

5. stack、queue 和 priority_queue 的对比

5.1 访问方式

• stack：后进先出，只能访问栈顶元素。
• queue：先进先出，只能访问队头和队尾元素。
• priority_queue：按照优先级排序，只能访问优先级最高的元素。

5.2 应用场景

• stack：适用于需要后进先出逻辑的场景，例如递归、函数调用管理等。
• queue：适用于需要先进先出逻辑的场景，例如任务调度、广度优先搜索等。
• priority_queue：适用于需要根据优先级处理元素的场景，例如任务调度、图算法等。

5.3 底层实现

• stack：基于 deque（默认）、vector 或 list。
• queue：基于 deque（默认）或 list。
• priority_queue：基于堆，通常使用 vector 实现。

5.4 时间复杂度

• stack：插入和删除操作的时间复杂度为 O(1)。
• queue：插入和删除操作的时间复杂度为 O(1)。
• priority_queue：插入和删除操作的时间复杂度为 O(log n)。

6. 示例代码总结

以下是一个完整的示例代码，展示了 stack、queue 和 priority_queue 的基本使用方法：

#include <iostream>
#include <stack>
#include <queue>int main() {// stack 示例std::stack<int> s;s.push(1);s.push(2);s.push(3);std::cout << "Stack top: " << s.top() << std::endl;s.pop();std::cout << "Stack top after pop: " << s.top() << std::endl;// queue 示例std::queue<int> q;q.push(1);q.push(2);q.push(3);std::cout << "Queue front: " << q.front() << ", back: " << q.back() << std::endl;q.pop();std::cout << "Queue front after pop: " << q.front() << std::endl;// priority_queue 示例std::priority_queue<int> pq;pq.push(10);pq.push(5);pq.push(20);std::cout << "Priority queue top: " << pq.top() << std::endl;pq.pop();std::cout << "Priority queue top after pop: " << pq.top() << std::endl;return 0;
}

7. 总结

C++ 中的 stack、queue 和 priority_queue 容器为开发者提供了实现特定数据结构的便捷方式。stack 采用后进先出的逻辑，适合处理递归和回溯问题；queue 采用先进先出的逻辑，适合任务调度和广度优先搜索；priority_queue 根据优先级处理元素，适合任务调度和图算法。在使用这些容器时，需要根据具体的应用场景选择合适的容器，以便最大化性能和代码简洁性。每种容器都有其特定的用途和优势，合理选择可以有效简化程序设计，并提升程序的可维护性和效率。