探密 C++ STL — 深入理解 Stack 和 Queue 的实现与应用

目录

引言

1. 什么是 Stack？

1.1 Stack 的概念

1.2 Stack 的操作

1.3 最小栈的实现

1.4 栈的模拟实现

2. 什么是 Queue？

2.1 Queue 的概念

2.2 Queue 的操作

2.3 队列的模拟实现

3. Priority Queue（优先级队列）

3.1 Priority Queue 的概念

3.2 Priority Queue 的操作

3.3 自定义优先级的优先级队列

4. 容器适配器与底层实现

4.1 容器适配器的概念

4.2 为什么选择 deque 作为默认容器？

4.3 栈和队列的模拟实现

结论

引言

在计算机科学中，数据结构是存储和组织数据的方式，使得我们可以高效地进行数据的访问和修改。在众多数据结构中，stack（栈）和 queue（队列）是两种非常基础且广泛应用的线性数据结构。C++ 提供了非常方便的标准库（STL）来实现 stack 和 queue，并且它们被广泛应用于各种算法和解决方案中。

本文将深入介绍 stack 和 queue 的基本概念、如何使用它们，以及它们在 C++ STL 中的实现细节。通过多个代码示例，我们将理解它们的实现原理，并探索如何灵活运用这些数据结构来解决实际编程问题。

1. 什么是 Stack？

1.1 Stack 的概念

stack 是一种后进先出（LIFO, Last In First Out）的数据结构，这意味着最后插入的数据将最先被移除。栈可以想象成一个物理的堆叠，比如书本堆。只有在最上面的书本可以被移除或被添加到堆中。

栈的典型应用场景包括函数调用栈、括号匹配、撤销操作等。C++ 中的 stack 是通过 STL 提供的容器适配器，底层可以使用 deque 或其他符合条件的容器来实现。

1.2 Stack 的操作

C++ 中，stack 提供了以下基本操作：

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

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

  • top()：返回栈顶元素。

  • empty()：检查栈是否为空。

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

以下是 stack 的常用代码示例：

#include <iostream>
#include <stack>int main() {std::stack<int> s;s.push(1);s.push(2);s.push(3);std::cout << "Stack top: " << s.top() << std::endl; // 输出 3s.pop();std::cout << "Stack top after pop: " << s.top() << std::endl; // 输出 2return 0;
}

在这个示例中，我们创建了一个整数栈，并依次向栈中插入 1、2 和 3。随后，通过 top() 查看栈顶元素并使用 pop() 将其移除。

1.3 最小栈的实现

最小栈是一个扩展版本的栈，它除了支持基本的栈操作外，还可以在常数时间内返回栈中的最小元素。我们可以使用两个栈来实现一个最小栈：

  • 一个栈存储所有元素。

  • 另一个栈存储当前栈中的最小值。

以下是最小栈的代码实现：

#include <stack>class MinStack {
public:void push(int x) {elemStack.push(x);// 如果最小值栈为空，或者当前值小于等于最小值栈顶，则将其压入最小值栈if (minStack.empty() || x <= minStack.top()) {minStack.push(x);}}void pop() {if (elemStack.top() == minStack.top()) {minStack.pop();}elemStack.pop();}int top() {return elemStack.top();}int getMin() {return minStack.top();}private:std::stack<int> elemStack; // 存储栈中的所有元素std::stack<int> minStack;  // 存储当前栈中的最小值
};

在这里，我们使用两个栈 elemStack 和 minStack。minStack 用于保存栈中的最小元素，这样当调用 getMin() 时，可以在 O(1) 时间内返回最小值。

1.4 栈的模拟实现

从栈的接口中可以看出，栈实际是一种特殊的 vector，因此使用 vector 可以完全模拟实现一个栈：

#include <vector>class Stack {
public:void push(int x) {elements.push_back(x);}void pop() {if (!elements.empty()) {elements.pop_back();}}int top() {return elements.back();}bool empty() {return elements.empty();}size_t size() {return elements.size();}private:std::vector<int> elements;
};

在这个实现中，使用 vector 来模拟 stack 的行为，支持基本的栈操作，例如 push()、pop()、top() 和 empty()。

2. 什么是 Queue？

2.1 Queue 的概念

queue 是一种先进先出（FIFO, First In First Out）的数据结构，意味着最早插入的数据最先被移除。队列可以想象成排队买票的场景，最先排队的人最先买到票。

队列的典型应用包括任务调度、宽度优先搜索（BFS）等。C++ 中的 queue 同样是通过 STL 提供的容器适配器，底层可以使用 deque 或其他符合条件的容器来实现。

2.2 Queue 的操作

C++ 中，queue 提供了以下基本操作：

  • push()：将元素插入队尾。

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

  • front()：返回队头元素。

  • back()：返回队尾元素。

  • empty()：检查队列是否为空。

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

以下是 queue 的常用代码示例：

#include <iostream>
#include <queue>int main() {std::queue<int> q;q.push(1);q.push(2);q.push(3);std::cout << "Queue front: " << q.front() << std::endl; // 输出 1q.pop();std::cout << "Queue front after pop: " << q.front() << std::endl; // 输出 2return 0;
}

在这个示例中，我们创建了一个整数队列，并依次向队列中插入 1、2 和 3。随后，通过 front() 查看队头元素并使用 pop() 将其移除。

2.3 队列的模拟实现

因为 queue 的接口中存在头删和尾插的操作，因此使用 vector 来封装效率太低，可以借助 list 来模拟实现 queue：

#include <list>class Queue {
public:void push(int x) {elements.push_back(x);}void pop() {if (!elements.empty()) {elements.pop_front();}}int front() {return elements.front();}int back() {return elements.back();}bool empty() {return elements.empty();}size_t size() {return elements.size();}private:std::list<int> elements;
};

在这个实现中，我们使用 list 来模拟 queue 的行为，因为 list 支持在头部和尾部进行高效的插入和删除操作。

3. Priority Queue（优先级队列）

3.1 Priority Queue 的概念

优先级队列是一种特殊的队列，它的每个元素都有一个优先级，出队时总是优先级最高的元素最先被移除。C++ 中的 priority_queue 默认是一个大顶堆，意味着优先级最大的元素会最先出队。

3.2 Priority Queue 的操作

C++ 中，priority_queue 提供了以下基本操作：

  • push()：将元素插入队列中。

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

  • top()：返回优先级最高的元素。

  • empty()：检查队列是否为空。

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

以下是 priority_queue 的常用代码示例：

#include <iostream>
#include <queue>
#include <vector>int main() {std::priority_queue<int> pq;pq.push(3);pq.push(1);pq.push(4);pq.push(2);std::cout << "Priority Queue top: " << pq.top() << std::endl; // 输出 4pq.pop();std::cout << "Priority Queue top after pop: " << pq.top() << std::endl; // 输出 3return 0;
}

在这个示例中，我们创建了一个整数优先级队列，并依次向队列中插入 3、1、4 和 2。由于优先级队列是一个大顶堆，所以每次 top() 都返回最大的元素。

3.3 自定义优先级的优先级队列

我们可以通过自定义比较器来实现一个小顶堆或者具有自定义优先级的优先级队列。例如，下面是一个实现小顶堆的示例：

#include <iostream>
#include <queue>
#include <vector>int main() {// 使用 greater<int> 作为比较器来实现小顶堆std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;minHeap.push(3);minHeap.push(1);minHeap.push(4);minHeap.push(2);std::cout << "Min Heap top: " << minHeap.top() << std::endl; // 输出 1minHeap.pop();std::cout << "Min Heap top after pop: " << minHeap.top() << std::endl; // 输出 2return 0;
}

在这个示例中，我们使用了 greater<int> 作为比较器，使得 priority_queue 的行为变成了小顶堆，从而每次 top() 返回最小的元素。

4. 容器适配器与底层实现

4.1 容器适配器的概念

容器适配器是一种设计模式，通过对底层容器进行封装，提供不同的接口来实现特定的数据结构。stack 和 queue 就是典型的容器适配器，它们默认使用 deque 作为底层容器。

4.2 为什么选择 deque 作为默认容器？

  • deque 支持在头部和尾部的高效插入和删除操作，这对于 stack 和 queue 来说非常重要。

  • deque 在扩容时不需要搬移大量元素，相比于 vector，deque 的效率更高。

  • 由于 stack 和 queue 不需要遍历操作，deque 的迭代器复杂性并不会影响它们的使用。

4.3 栈和队列的模拟实现

STL 中的 stack 和 queue 默认使用 deque 作为底层实现，但它们也可以使用其他符合条件的容器来实现。例如，可以使用 list 或 vector 来模拟实现栈和队列：

#include <deque>// 使用 deque 作为底层容器来实现 stack
namespace bite {template<class T, class Con = std::deque<T>>class Stack {public:void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_back(); }T& top() { return _c.back(); }size_t size() const { return _c.size(); }bool empty() const { return _c.empty(); }private:Con _c;};
}

在这个实现中，我们使用模板参数 Con 来定义底层容器，默认为 deque，但用户可以自定义底层容器类型，例如 vector 或 list。

结论

通过本文的详细讲解，相信大家对 stack、queue 和 priority_queue 有了更加深入的理解。我们从它们的基本概念和操作入手，逐步探索了它们的实际应用和实现方式。无论是使用 STL 中现成的容器，还是手动模拟实现这些数据结构，理解其底层的原理和操作方式对于写出高效可靠的代码都是至关重要的。

在编程过程中，选择合适的数据结构来解决问题是非常关键的技能。栈和队列作为最基础的数据结构之一，具有简单而强大的特性，能为各种复杂问题提供解决方案。希望通过这篇文章，大家能更好地掌握它们，并在日后的编程实践中灵活运用。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/8341.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

three.js 如何简单的实现场景的雾

three.js 如何简单的实现场景的雾

three.js 如何简单的实现场景的雾 https://threehub.cn/#/codeMirror?navigationThreeJS&classifybasic&idsceneFog import * as THREE from three import { OrbitControls } from three/examples/jsm/controls/OrbitControls.js import { GLTFLoader } from three…
阅读更多...
算法定制LiteAIServer摄像机实时接入分析平台烟火检测算法的主要功能

算法定制LiteAIServer摄像机实时接入分析平台烟火检测算法的主要功能

在现代社会&#xff0c;随着人工智能技术的飞速发展&#xff0c;智能监控系统在公共安全领域的应用日益广泛。其中&#xff0c;烟火检测作为预防火灾的重要手段&#xff0c;其准确性和实时性对于减少火灾损失、保障人民生命财产安全具有重要意义。而算法定制LiteAIServer烟火检…
阅读更多...
C++中sizeof运算符的案例分析

C++中sizeof运算符的案例分析

分析案例 在网上看到一个关于sizeof疑问的文章&#xff0c;所以就想认真研究下&#xff0c;例子代码如下&#xff1a; #include<iostream> using namespace std; int main(void) {cout << sizeof("123456789") << endl; //10cout << siz…
阅读更多...
centos7 部署 Ollama，过程及遇到的问题（上篇）

centos7 部署 Ollama，过程及遇到的问题（上篇）

背景&#xff1a;为了搭建 Dify llama3 实现大模型本地化学习。 材料&#xff1a; 1、centos 7.x 2、网络要通 制作&#xff1a; 1、更新YUM源 1、备份yum源 mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.backup2、下载阿里yum wget -O /e…
阅读更多...
openGauss数据库-头歌实验1-5 修改数据库

openGauss数据库-头歌实验1-5 修改数据库

一、查看表结构与修改表名 &#xff08;一&#xff09;任务描述 本关任务&#xff1a;修改表名&#xff0c;并能顺利查询到修改后表的结构。 &#xff08;二&#xff09;相关知识 为了完成本关任务&#xff0c;你需要掌握&#xff1a; 1.如何查看表的结构&#xff1b; 2.如…
阅读更多...
一文学会编写大模型备案安全评估报告「小白也可学会」

一文学会编写大模型备案安全评估报告「小白也可学会」

文章目录 一、语料安全评估 (一) 评估内容 (二) 评估结论 二、模型安全评估 三、安全措施评估 四、总体结论 适用于不会大模型备案过程中对大模型备案安全评估报告不会如何编写的业务人员。 *图&#xff1a;大模型备案全套素材文件 一、语料安全评估 (一) 评估内容 文本…
阅读更多...
Pytest参数详解 — 基于命令行模式！

Pytest参数详解 — 基于命令行模式！

1、--collect-only 查看在给定的配置下哪些测试用例会被执行 2、-k 使用表达式来指定希望运行的测试用例。如果测试名是唯一的或者多个测试名的前缀或者后缀相同&#xff0c;可以使用表达式来快速定位&#xff0c;例如&#xff1a; 命令行-k参数.png 3、-m 标记&#xff08…
阅读更多...
SpringBoot项目集成ONLYOFFICE

SpringBoot项目集成ONLYOFFICE

ONLYOFFICE 文档8.2版本已发布&#xff1a;PDF 协作编辑、改进界面、性能优化、表格中的 RTL 支持等更新 文章目录 前言ONLYOFFICE 产品简介功能与特点Spring Boot 项目中集成 OnlyOffice1. 环境准备2. 部署OnlyOffice Document Server3. 配置Spring Boot项目4. 实现文档编辑功…
阅读更多...
STL之string的使用(超详解)

STL之string的使用(超详解)

目录 1. C/C中的字符串 1.1. C语言中的字符串 1.2. C中的字符串 2. string的接口 2.1. string的迭代器 2.1.1begin()与end()函数 2.2.2 rbegin()与rend()函数 2.2. string的初始化与销毁 2.3. string的容量操作 2.3.1 size()&#xff0c;length()&#xff0c;capa…
阅读更多...
《JavaEE进阶》----20.＜基于Spring图书管理系统（登录+添加图书）＞

《JavaEE进阶》----20.＜基于Spring图书管理系统（登录+添加图书）＞

PS&#xff1a;关于接口定义 接口定义&#xff0c;通常由服务器提供方来定义。 1.路径&#xff1a;自己定义 2.参数&#xff1a;根据需求考虑&#xff0c;我们这个接口功能完成需要哪些信息。 3.返回结果&#xff1a;考虑我们能为对方提供什么。站在对方角度考虑。 我们使用到的…
阅读更多...
Sigrity Power SI 3D-EM Full Wave Extraction模式如何进行S参数提取和观测3D电磁场和远场操作指导(一)

Sigrity Power SI 3D-EM Full Wave Extraction模式如何进行S参数提取和观测3D电磁场和远场操作指导(一)

Sigrity Power SI 3D-EM Full Wave Extraction模式如何进行S参数提取和观测3D电磁场和远场操作指导(一) Sigrity Power SI的3D-EM Full Wave Extraction模式是Power SI的3D全波提取工具，相比于2D提取，3D全波提取的结果更为精确，且支持设置跨平面的port，也就是lump port，这…
阅读更多...
用Python打造你的《天天酷跑》——从零开始的游戏开发之旅

用Python打造你的《天天酷跑》——从零开始的游戏开发之旅

前言 在快节奏的生活里&#xff0c;偶尔玩一款轻松有趣的小游戏可以很好地放松心情。《天天酷跑》作为一款经典的跑酷游戏&#xff0c;凭借其简单易上手的操作和丰富多彩的关卡设计&#xff0c;深受广大玩家的喜爱。如果你对游戏开发感兴趣&#xff0c;或者想要尝试自己动手制…
阅读更多...
泷羽sec学习打卡-shodan扫描4

泷羽sec学习打卡-shodan扫描4

声明 学习视频来自B站UP主 泷羽sec,如涉及侵权马上删除文章 笔记的只是方便各位师傅学习知识,以下网站只涉及学习内容,其他的都与本人无关,切莫逾越法律红线,否则后果自负 关于shodan的那些事儿-4 一、shodan4如何查看公网ip&#xff1f;如何查看自己的ip&#xff1f;如何查看出…
阅读更多...
深层次识别：书脊图像分割

深层次识别：书脊图像分割

书脊图像分割系统源码&#xff06;数据集分享 [yolov8-seg-C2f-DAttention&#xff06;yolov8-seg-EfficientHead等50全套改进创新点发刊_一键训练教程_Web前端展示] 1.研究背景与意义 项目参考ILSVRC ImageNet Large Scale Visual Recognition Challenge 项目来源AAAI Glo…
阅读更多...
已有商标证的人注意，留存使用证据！

已有商标证的人注意，留存使用证据！

近日有个网友联系普推知产商标老杨&#xff0c;说商标被撤三已经答辩了一次&#xff0c;但是没有成功&#xff0c;无法证明在指定服务上使用&#xff0c;原商标注册证被作废。 现在好的商标资源有限&#xff0c;在许多申请注册时会通过撤三打掉在先权利&#xff0c;即连续三年不…
阅读更多...
Oracle视频基础1.3.7练习

Oracle视频基础1.3.7练习

1.3.7 看oracle是否启动构造一个pfile:boobooke.ora看spfilewilson内容修改alert log file里拷贝的参数内容&#xff0c;创建一个pfile boobooke.ora用新创建的pfile启动数据库&#xff0c;并创建新的spfile:spfilebbk.ora启动数据库&#xff0c;监听&#xff0c;看新的进程解…
阅读更多...
深度强化学习：从理论到应用

深度强化学习：从理论到应用

目录 1.引言 2.什么是强化学习&#xff1f; 3.深度学习和强化学习的结合 4.深度强化学习的主要方法 5.深度强化学习的应用领域 6.深度强化学习的挑战与未来 7.总结 1.引言 深度强化学习&#xff08;Deep Reinforcement Learning&#xff0c;DRL&#xff09;是近年来人工…
阅读更多...
如何在算家云搭建Hunyuan-DiT（图像生成）

如何在算家云搭建Hunyuan-DiT（图像生成）

一、Hunyuan-DiT简介 Hunyuan-DiT 是由腾讯混元推出的文生图扩散模型&#xff0c;支持中文和英文双语输入&#xff0c;其他开源模型相比&#xff0c;Hunyuan-DiT 在中文到图像生成方面树立了新的水平。 要求&#xff1a; 所需的最小 GPU 内存为 11GB&#xff0c;建议使用具有…
阅读更多...
2024版新鲜出炉：最新大厂 Java 面试八股文合集（附权威答案）

2024版新鲜出炉：最新大厂 Java 面试八股文合集（附权威答案）

谈到 Java 面试&#xff0c;相信大家第一时间脑子里想到的词肯定是金三银四&#xff0c;金九银十。好像大家的潜意识里做 Java 开发的都得在这个时候才能出去面试&#xff0c;跳槽成功率才高&#xff01;但 LZ 不这么认为&#xff0c;LZ 觉得我们做技术的一生中会遇到很多大大小…
阅读更多...
Latex之LNCS模板——使用bib添加参考文献

Latex之LNCS模板——使用bib添加参考文献

1、获取参考文献 从谷歌学术中获取bib格式的参考文献。 创建一个.bib文件&#xff0c;将参考文献复制进去。 2、添加参考文献 在文章最后引用.bib格式的参考文献。 \bibliographystyle{splncs04} % 格式 \bibliography{references.bib} % 文件名 LNCS模板中会包含该格式文件…
阅读更多...
最新文章

Copyright @ 2022~2023