【C++】C++ STL探索：容器适配器 Stack 与 Queue 的使用及模拟实现

在这里插入图片描述

C++语法相关知识点可以通过点击以下链接进行学习一起加油！
命名空间缺省参数与函数重载C++相关特性类和对象-上篇类和对象-中篇
类和对象-下篇日期类C/C++内存管理模板初阶String使用
String模拟实现Vector使用及其模拟实现List使用及其模拟实现

本文将详细介绍如何使用容器适配器 Stack 和 Queue，并探讨其模拟实现方法。

请添加图片描述
Alt
🌈个人主页：是店小二呀
🌈C语言笔记专栏：C语言笔记
🌈C++笔记专栏： C++笔记
🌈初阶数据结构笔记专栏： 初阶数据结构笔记
🌈Linux笔记专栏： Linux笔记

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅 请添加图片描述

文章目录

  • 一、Stack
    • 1.1 stack介绍
    • 1.2 stack容器使用
    • 1.3 关于stack使用场景
      • 1.3.1 最小栈
      • 1.3.2 栈的弹出压入序列
      • 1.3.3 何为中缀和后缀表达式
      • 1.3.4 逆波兰(后缀)表达式求值
      • 1.3.5 中缀表达式转化为后缀表达式
      • 1.3.6 深入探索：复杂表达式
  • 二、Queue
    • 2.1 queue介绍
    • 2.2 queue使用
  • 三、容器适配器
  • 四、STL标准库中stack和queue的底层结构
    • 4.1 deque
      • 4.1.2 deque介绍
      • 4.1.3 deque的缺陷
      • 4.1.4 为什么选择deque作为stack和queue的底层默认容器
  • 五、模拟实现Stack与queue
    • 5.1 Stack.h
    • 5.2 Queue.h

一、Stack

1.1 stack介绍

stack文档介绍

  1. stack是一种容器适配器专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入和提取操作
  2. stack是作容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素的，将特定类作为其底层，元素特定容器的尾部(即是栈顶)被压入和弹出
  3. stack的底层容器可以是任何标准的容器类名模板或者一些特定的容器类，这些容器类应该支持以下操作
  • empty：判空操作
  • back：获取尾部元素操作
  • push_back：尾部插入元素操作
  • pop_back：尾部删除元素操作
  1. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

在这里插入图片描述

1.2 stack容器使用

函数说明接口说明
stack()构造空的栈
empty()检测stack是否为空
size()返回stack中元素的个数
top()返回栈顶元素的引用
push()将元素val压入stack中
pop()将stack中尾部的元素弹出

1.3 关于stack使用场景

1.3.1 最小栈

在这里插入图片描述

class MinStack
{
    public:
    /** initialize your data structure here. */

    void push(int x) 
    {
        _st.push(x);
        if(_minst.empty() || x <= _minst.top())
        {
            _minst.push(x);
        }
    }

    void pop()
    {
        if(_st.top() == _minst.top())
        {
            _minst.pop();
        }
        _st.pop();
    }

    int top() 
    {
        return _st.top();
    }

    int getMin() 
    {
        return _minst.top();
    }

    private:
    stack<int> _st;
    stack<int> _minst;
};

具体流程:

  1. 创建一个栈，设置min的变量记录最小值。但是效率很低，如果插入或者删除数据，又需要重新遍历
  2. 我们可以创建两个栈，一个用于插入或删除数据，一个用于记录栈中最小数。
  3. 如果插入的数据比最小栈中栈顶数据要小，就插入在最小栈栈顶中。如果删除数据跟最小栈数据一样，需要同步删除，保持对其；如果删除数据不等于最小栈数据，单纯删除一边数据。

1.3.2 栈的弹出压入序列

在这里插入图片描述

bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
{
    stack<int> st;
    int pushi = 0; int popi = 0;

    while(pushi < pushV.size())
    {
        st.push(pushV[pushi++]);

        while(!st.empty() && st.top() == popV[popi])
        {
            popi++;
            st.pop();
        }
    }

    return st.empty();
}

具体思路:

  1. 入栈序列不断入栈，在入栈期间判断栈顶元素和出栈序列是否匹配
  2. 如果匹配，就需要持续出数据，直到不匹配或者栈为空（不一定结束）
  3. 如果不匹配，那就继续入栈，等待下次匹配或结束
  4. 结束标志:入栈序列走完后
  5. 结果判断:栈不为空

1.3.3 何为中缀和后缀表达式

我们在实际中一般采用的是中缀表达式a+(b-c)，而后缀表达式是采用操作数、操作数、操作符的结构，转为这种形式的原因，是提供计算机使用的，中缀表达式给人看，一眼知道运算顺序，但是计算机不知道，需要转化后缀表达式进行运算（观察蓝色一圈圈圈起来的部分），遇到操作符就开始跟前面两操作数进行运算，返回一个数值。

在这里插入图片描述

1.3.4 逆波兰(后缀)表达式求值

在这里插入图片描述

class Solution
 {
public:
    int evalRPN(vector<string>& tokens) 
    {
        stack<int> st;
        set<string> s = {"+","-","*","/"};
        
        for(auto str : tokens)
        {
            //如果等于操作符进行运算符
            if(s.find(str) != s.end())
            {
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();

                switch(str[0])
                {
                    case '+':
                        st.push(left+right);
                        break;
                     case '-':
                        st.push(left-right);
                        break;  
                    case '*': 
                        st.push(left * right);
                        break;  
                    case '/':
                        st.push(left / right);
                        break;      
                }
            }
            else
            {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};

具体流程:

  1. 根据后缀表达式的工作原理，可以很快按照逻辑解决这道题目
  2. 首先遇到操作符先入栈，如果遇到操作符就出栈两个操作数进行四则运算，并将结果入栈，等待下一次运算
  3. 这里采用了set容器和stoi函数，简单介绍这两个函数的作用。
  4. set是一个集合容器，存储唯一的元素，并且按照特定的顺序进行排序。
  5. 使用s.find(str)时。从集合s中查找字符串str。如果str存在s集合中，find函数会返回一个指向该元素的迭代器，否则会返回s.end()，表达未找到该元素
  6. stoi函数将字符串转换为整数，将一个标识数字的字符串转化为对应的整数类型，比如将"123"转化为整数123

1.3.5 中缀表达式转化为后缀表达式

  • 中缀表达式:1 + 2 * 3 - 4
  • 后缀表达式:1 2 3 * + 4 -

办法：

  1. 操作数输出
  2. 操作符
  • 当栈为空，入栈
  • 比栈顶的操作符优先级高，入栈
  • 比栈顶的操作符优先级低或者相等，出栈操作符
  1. 结束后，将栈中操作符，全部出栈

说明:这里关键为操作符，操作符出栈必有两个操作数在前面。同时存在两个操作符在栈中说明前面有三个操作符，即存在操作符的优先性。这里优先性是通过栈得以实现，优先级高的操作符先出栈。至于操作符的结合性就落到比栈顶的操作符优先级相等出栈操作符这块了。

1.3.6 深入探索：复杂表达式

如果是一个复杂的表达式，如何从中缀转化后缀表达式，进行运算呢？

例子: 1+2*（3+4/（2-1）+6）+5

在这里插入图片描述

办法:括号走递归，解决括号中表达式问题，将括号中顺序问题解决再添加到原本表达式中。

二、Queue

2.1 queue介绍

队列文档介绍

  1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
  2. 队列作为容器适配器实现，容器适配器即将容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素(元素从队尾入队列，从队头出队列)
  3. 底层容器可以是标准容器类模板之一，也可以是其他专门设置的容器类。该底层应该至少支持以下操作
  • empty:检测队列是否为空
  • size:返回队列中有效元素的个数
  • front:返回队头元素的引用
  • back:返回队尾元素的引用
  • push_back:返回队尾元素的引用
  • pop_front:在队列头部出队列
  1. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。（这里容器选择不适合vector，因为没有头删，如果使用erase效率也很低）

在这里插入图片描述

2.2 queue使用

函数声明接口说明
queue()构造空的队列
empty()检测队列是否为空，是返回true，否则返回false
size()返回队列中有效元素的个数
front()返回队头元素的引用
back()返回队尾元素的引用
push()在队尾将元素val入队列
pop()将队头元素出队列

三、容器适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口

在这里插入图片描述

四、STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素，但是在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这因为stack和queue只是对其他容器的接口进行了包装。STL中stack和queue默认使用deque。

在这里插入图片描述

在这里插入图片描述在这里插入图片描述

4.1 deque

在模拟实现之前，这里先简单介绍deque容器

4.1.2 deque介绍

在这里插入图片描述

deque(双端队列):是一种双开可口得"连续"空间数据结构

双开口的含义是:可以在头尾两端进行插入和删除操作，且时间复杂度O（1），与vector比较，头插效率高，不需要搬移元素，在扩容时，也不需要搬运大量的数据；与list比较，空间利用率比较高，不需要存储额外的字段

在这里插入图片描述

但是deque并不是真的连续的空间，而是由一段连续的小空间拼接而成的，实际上deque类似于一个动态的二维数组，其底层结构如下:
在这里插入图片描述

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其"整体连续"以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计比较复杂

在这里插入图片描述

那deque是如何借助其迭代器维护其假想连续的结构呢？

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

4.1.3 deque的缺陷

不适合遍历，因为在遍历时，deque的迭代器需要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而且在序列场景中，可能需要经常遍历。因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目能看到的一个应用就是，STL用其作为stack和queue的底层数据结构

4.1.4 为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以

queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。

但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

  1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。

  2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。

  3. deque结合vector和list有点，但是在遍历方面存在缺陷和实现复杂问题上，stack与queue使用deque作为底层容器属于扬长避短手段

五、模拟实现Stack与queue

5.1 Stack.h

#pragma once
#include <vector>

namespace  bit
{
	template<class T, class Container = vector<T>>
	class Stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_back();
		}
	private:
        //容器适配器
		Container _con;
	};

	void test1()
	{
		Stack<int> st;
	}
}

5.2 Queue.h

#pragma once
#include <list>
#include <deque>

namespace bit
{
    template<class T, class Container = deque<T>>
        class queue
        {
            public:

            void push(const T& x)
            {
                _con.push_back(x);
            }

            void pop()
            {
                _con.pop_front();
            }

            size_t size()
            {
                return _con.size();
            }

            bool empty()
            {
                return _con.empty();
            }

            const T& back()
            {
                return _con.back();
            }

            const T& front()
            {
                return _con.front();
            }

            private:
            Container _con;
        };

    void test()
    {
        queue<int> q;
        q.push(1);
        cout << q.back() << endl;
        q.push(2);
        cout << q.back() << endl;
        q.push(3);

        cout << q.back() << endl;
    }
}

以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二呀C++笔记，希望对你在学习C++语言旅途中有所帮助！
请添加图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

探索最佳 Shell 工具：全面测评 Bash、Zsh、Fish、Tcsh 和 Ksh

探索最佳 Shell 工具：全面测评 Bash、Zsh、Fish、Tcsh 和 Ksh

感谢浪浪云支持发布 浪浪云活动链接 &#xff1a;https://langlangy.cn/?i8afa52 文章目录 1. 简介2. 测评工具3. 测评标准4. Bash 测评4.1 易用性4.2 功能特性4.3 性能4.4 可定制性4.5 社区和支持 5. Zsh 测评5.1 易用性5.2 功能特性5.3 性能5.4 可定制性5.5 社区和支持 6. F…
阅读更多...
3款数据恢复免费版软件评测：帮你轻松解决数据丢失问题

3款数据恢复免费版软件评测：帮你轻松解决数据丢失问题

如今数字化时代&#xff0c;数据至关重要&#xff0c;珍贵照片、重要文档、成长记录的视频音频&#xff0c;承载回忆与努力。但数据丢失风险常伴&#xff0c;误删、格式化、病毒攻击等意外频发&#xff0c;令人陷入绝望&#xff0c;如坠数据黑洞。所幸科技发展&#xff0c;数据…
阅读更多...
精益生产现场管理和改善的“蜕变”之旅：从理念到落地的全方位指南

精益生产现场管理和改善的“蜕变”之旅：从理念到落地的全方位指南

精益生产现场管理和改善&#xff0c;正逐步成为众多企业转型升级的必经之路。今天&#xff0c;就让我们&#xff08;深圳天行健企业管理咨询公司&#xff09;带大家一起踏上这场从理念到落地的“蜕变”之旅&#xff0c;探索精益生产现场管理与改善的方方面面&#xff0c;为企业…
阅读更多...
API安全 | 发现API的5个小tips

API安全 | 发现API的5个小tips

在安全测试目标时&#xff0c;最有趣的测试部分是它的 API。API 是动态的&#xff0c;它们比应用程序的其他部分更新得更频繁&#xff0c;并且负责许多后端繁重的工作。在现代应用程序中&#xff0c;我们通常会看到 REST API&#xff0c;但也会看到其他形式&#xff0c;例如 Gr…
阅读更多...
游戏论坛网站|基于Springboot+vue的游戏论坛网站系统游戏分享网站(源码+数据库+文档)

游戏论坛网站|基于Springboot+vue的游戏论坛网站系统游戏分享网站(源码+数据库+文档)

游戏论坛|游戏论坛系统|游戏分享网站 目录 基于Springbootvue的游戏论坛网站系统游戏分享网站 一、前言 二、系统设计 三、系统功能设计 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主介绍&#xff1a;✌️大…
阅读更多...
JAVA同城服务系统大集结活动报名通道已开启构建你的同城圈子系统小程序源码

JAVA同城服务系统大集结活动报名通道已开启构建你的同城圈子系统小程序源码

同城服务系统大集结&#xff0c;活动报名通道已开启&#xff01; &#x1f389; 【开篇号角】同城服务大狂欢&#xff0c;集结号已吹响&#xff01; 嘿&#xff0c;小伙伴们&#xff01;你们期待已久的同城服务系统大集结活动终于来啦&#xff01;&#x1f38a; 是的&#xff…
阅读更多...
kubernetes微服务基础及类型

kubernetes微服务基础及类型

目录 1 什么是微服务 2 微服务的类型 3 ipvs模式 ipvs模式配置方式 4 微服务类型详解 4.1 ClusterIP 4.2 ClusterIP中的特殊模式headless 4.3 nodeport 4.4 metalLB配合loadbalance实现发布IP 1 什么是微服务 用控制器来完成集群的工作负载&#xff0c;那么应用如何暴漏出去&…
阅读更多...
【卷起来】VUE3.0教程-08-路由管理

【卷起来】VUE3.0教程-08-路由管理

在Vue中&#xff0c;我们可以通过vue-router路由管理页面之间的关系。 Vue Router是Vue.js的官方路由&#xff0c;它与Vue.js核心深度集成&#xff0c;让用Vue.js构建单页应用变得轻而易举。 &#x1f332; 在Vue中引入路由 安装路由 npm install --save vue-router 建立三个…
阅读更多...
详聊LLaMa技术细节：LLaMA大模型是如何炼成的？

详聊LLaMa技术细节：LLaMA大模型是如何炼成的？

本文介绍来自 Meta AI 的 LLaMa 模型&#xff0c;类似于 OPT&#xff0c;也是一种完全开源的大语言模型。LLaMa 的参数量级从 7B 到 65B 大小不等&#xff0c;是在数万亿个 token 上面训练得到。值得一提的是&#xff0c;LLaMa 虽然只使用公共的数据集&#xff0c;依然取得了强…
阅读更多...
读论文-《基于计算机视觉的工业金属表面缺陷检测综述》

读论文-《基于计算机视觉的工业金属表面缺陷检测综述》

文章目录 1. 背景1.1 工业需求1.2 传统方法的局限1.3 计算机视觉技术的优势 2. 技术流程2.1 光学成像2.1.1照明方式2.1.2 缺陷和背景特性 2.2 图像预处理2.3 缺陷检测2.4 结果分析和决策 3. 关键算法3.1 光学成像技术相关算法3.2 图像预处理相关算法3.2.1 图像增强3.2.2特征提取…
阅读更多...
【JS】将class转为构造函数需要注意的细节

【JS】将class转为构造函数需要注意的细节

前言 将 class 转为构造函数看似很简单&#xff0c;但作为封装者&#xff0c;有很多注意事项 class Person {constructor(name) {this.name name;}fn() { console.log(this.name); } }实现 初步转化如下&#xff1a; function Person() {this.name name } Person.prototy…
阅读更多...
网络学习-eNSP配置VRRP

网络学习-eNSP配置VRRP

虚拟路由冗余协议(Virtual Router Redundancy Protocol&#xff0c;简称VRRP) VRRP广泛应用在边缘网络中&#xff0c;是一种路由冗余协议&#xff0c;它的设计目标是支持特定情况下IP数据流量失败转移不会引起混乱&#xff0c;允许主机使用单路由器&#xff0c;以及即使在实际…
阅读更多...
二百六十三、Java——IDEA项目打成jar包，然后在Linux中运行

二百六十三、Java——IDEA项目打成jar包，然后在Linux中运行

一、目的 在用Java对原Kafka的JSON字段解析成一条条数据&#xff0c;然后写入另一个Kafka中&#xff0c;代码写完后打成jar包&#xff0c;放在Linux中&#xff0c;直接用海豚调度运行 二、Java利用fastjson解析复杂嵌套json字符串 这一块主要是参考了这个文档&#xff0c;然…
阅读更多...
如何进行DAP-seq的数据挖掘，筛选验证位点

如何进行DAP-seq的数据挖掘，筛选验证位点

从样本准备到寄送公司&#xff0c;每一天都在“祈祷”有个心仪的分析结果&#xff0c;终于在这天随着邮件提示音的响起&#xff0c;收到了分析结果...... 分析前工作 爱基在进行数据分析之前&#xff0c;会有两次质控报告反馈给老师们。第一个&#xff0c;基因组DNA的提取质控…
阅读更多...
Django路由访问及查询数据

Django路由访问及查询数据

1、在应用模块下&#xff0c;创建urls文件&#xff0c;用来存放访问路由 2、在项目总访问url里面注册路由 3、在view文件里&#xff0c;定义方法参数 from django.core import serializers from django.db import connection from django.http import HttpResponse, JsonRespo…
阅读更多...
什么是线程池？从底层源码入手，深度解析线程池的工作原理

什么是线程池？从底层源码入手，深度解析线程池的工作原理

导航&#xff1a; 【Java笔记踩坑汇总】Java基础JavaWebSSMSpringBootSpringCloud瑞吉外卖/谷粒商城/学成在线设计模式面试题汇总性能调优/架构设计源码解析 目录 一、什么是线程池&#xff1f; 1.1 基本介绍 1.2 创建线程的两种方式 1.2.1 方式1&#xff1a;自定义线程池…
阅读更多...
NASA数据集：高级星载热发射和反射辐射计（ASTER）1B 级快速传感器辐射度登记全球数据产品

NASA数据集：高级星载热发射和反射辐射计（ASTER）1B 级快速传感器辐射度登记全球数据产品

目录 简介 代码 引用 网址推荐 0代码在线构建地图应用 机器学习 ASTER L1B Registered Radiance at the Sensor V003 ASTER 加急 L1B 登记传感器 V003 的辐照度 简介 高级星载热发射和反射辐射计&#xff08;ASTER&#xff09;1B 级快速传感器辐射度登记全球数据产品是…
阅读更多...
AIGC简化文件管理：Python自动重命名Word和PDF文件

AIGC简化文件管理：Python自动重命名Word和PDF文件

1.背景 大家应该也有遇到&#xff0c;自己电脑有很多文件命名不合理的文件&#xff0c;比如&#xff1a;文件1、想法3 &#xff0c;当你长时间再看到这个文件的时候&#xff0c;已经很难知道文件内容。 今天我们将借助AIGC的编码能力&#xff0c;帮我们生成一个批量改文件名的…
阅读更多...
语法基础课第五节字符串（知识点+题目）

语法基础课第五节字符串（知识点+题目）

字符串是计算机与人类沟通的重要手段。 1. 字符与整数的联系——ASCII码 每个常用字符都对应一个-128 ~ 127的数字&#xff0c;二者之间可以相互转化。注意&#xff1a;目前负数没有与之对应的字符。&#xff08;英文&#xff09; #include <iostream>using namespace…
阅读更多...
Unity让摄像机跟随物体的方法（不借助父子关系）

Unity让摄像机跟随物体的方法（不借助父子关系）

在Unity中&#xff0c;不使用子对象的方式让相机跟随物体移动&#xff0c;我们通过编写脚本来实现。下面放一个从工程中摘出来的的C#脚本示例&#xff0c;用于将相机绑定到一个Target对象上并跟随其移动&#xff1a; using UnityEngine; public class FollowCamera : MonoBeh…
阅读更多...
最新文章

Copyright @ 2022~2023