【C++】Stack

在这里插入图片描述

个人主页~


Stack

  • 一、Stack的介绍和使用
    • 1、stack的介绍
    • 2、stack的使用
    • 3、stack的模拟实现
  • 二、容器适配器
    • 1、什么是适配器
    • 2、容器适配器的使用
  • 三、deque
    • 1、原理介绍
    • 2、deque的使用
    • 3、deque的缺陷

一、Stack的介绍和使用

1、stack的介绍

stack详细解释

stack是一种容器适配器,专门用来处理后进先出操作,其删除只能从容器的一端进行元素的插入和提取操作

stack是作为容器适配器被实现的,容器适配器是对特定类封装为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部被压入和弹出

stack的底层容器可以是任何标准的容器类模版或者一些其他特定的容器类,这些容器都要支持empty判空、back获取尾部元素、push_back尾部插入元素、pop_back尾部删除元素的操作,这些是stack的基本接口

标准容器vector、list、deque均符合这些要求,如果没有指定stack的底层容器,默认为deque,这其中只有deque没有学习过,后面拿一个段落专门解释deque

2、stack的使用

函数说明接口说明
stack构造空的栈
empty检测stack是否为空
size返回stack中的元素个数
top返回栈顶元素的引用
push将元素val压入stack中
pop将stack中尾部的元素弹出
void test_stack()
{stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout << st.top() << endl;st.pop();}
}

在这里插入图片描述

手感火热做道题

最小栈
解题思路:就是创建两个栈st和minst,st栈存放数据,minst栈存放最小值,第一个入st栈的直接入minst栈,每次入st栈都与minst栈的top比较一下是不是更小,如果数小就入minst栈

class MinStack 
{
public:MinStack() {}//空构造构造空栈void push(int val) {if(minst.empty() || val <= minst.top()){minst.push(val);}st.push(val);}//如果minst栈为空或者入栈的值小于等于minst的栈顶元素就入minst栈void pop() {if(st.top() == minst.top()){minst.pop();}st.pop();}//如果删除st栈顶元素与minst栈顶的元素相等就连minst栈顶元素一块删除int top() {return st.top();}int getMin() {return minst.top();}
//因为minst是被比较出来的,越往上的元素越小,所以栈顶元素就是最小的元素stack<int> st;stack<int> minst;
};

栈的压入、弹出序列
这个题就是写一个栈弹出顺序是否正确的函数,传给两个vector,然后pushV元素压入栈,然后取栈顶元素与popV的第一个元素进行对比,如果相同就出栈,如果不同就继续入栈,最后如果pushV遍历完后栈为空,那么就正确,否则就错误

bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
{stack<int> st;size_t pushi = 0,popi = 0;//用于记录pushV、popV的下标while(pushi < pushV.size())//如果下标小于size循环继续{st.push(pushV[pushi++]);//pushV元素压入栈while(!st.empty() && st.top() == popV[popi]){st.pop();popi++;}//然后取栈顶元素与popV的第一个元素进行对比,如果相同就出栈}return st.empty();
}

3、stack的模拟实现

stack.h

在这里插入图片描述

#pragma once#include <vector>
#include <deque>
#include <list>
#include <iostream>namespace little_monster
{template<class T,class Container = std::deque<T>>class stack{public:stack(){}void push(const T& x){_c.push_back(x);}void pop(){_c.pop_back();}T& top(){return _c.back();}const T& top() const{return _c.back();}size_t size() const{return _c.size();}bool empty() const{return _c.empty();}private:Container _c;};
}

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

stack可以通过vector为底层实现,也可以通过list为底层实现,直接调用这些模版的接口就可以,不用在从零开始定义成员变量了

这里的Container以及deque是什么呢

二、容器适配器

1、什么是适配器

适配器是一种设计模式,该种设计模式是将一个类的接口转换成用户希望的另外一个接口,适配器可以接受不同的容器来达到用户想要的效果,而stack和queue的默认适配器是deque,priority_queue的默认适配器是vector

2、容器适配器的使用

常见于stack、queue、priority_queue、优先队列中
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

三、deque

相关文档

1、原理介绍

deque是一种双开口的连续空间的数据结构,可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素,与list比较,空间利用率比较高

deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组

双端队列底层是一段假想的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落在了deque的迭代器身上

偷一张详解图
在这里插入图片描述
首先我们可以看到start迭代器,它由四个指针组成,cur表示当前位置,first表示第一个位置,last表示最后一个位置,node是指向map的其中一个变量

当cur等于last时,node指向下一个位置,然后cur、first、last都重置到下一个map元素,在图中就是cur、first指向8,last指向15后一个位置

当start迭代器中的node和finish迭代器中的node相同时,该数组就是最后一个数组

然后这个map其实是一个指针数组,它进行扩容时是从中间向两端地存储,如果我们进行头插,start指向的数组又满了,我们就在start前面的位置再开一个数组,并且把数据存储在这个数组的最后一个位置

2、deque的使用

void test_deque()
{std::deque<int> dq;dq.push_back(3);dq.push_back(4);dq.push_front(2);dq.push_front(1);for (size_t sz = 0; sz < dq.size(); sz++){std::cout << dq[sz] << " ";}std::cout << std::endl;
}

在这里插入图片描述

3、deque的缺陷

它不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某小段小空间的边界,导致效率低下,因此在实际中,需要线性结构时,大多数优先使用vector和list,但我们知道的一个应用就是STL中做stack和queue的底层数据结构

它结合了vector和list的部分优点,也得到了它们的部分缺点,与vector相比,deque的优势是头插头删和扩容时,不需要搬移元素,效率高,与list比较,其底层是连续的空间,空间利用率较高


今日分享就到这里~

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Oracle反向键索引Reverse Key Index

Oracle反向键索引&#xff08;Reverse Key Index&#xff09;是一种特殊的B-Tree索引&#xff0c;它在创建索引时对索引列的键值进行字节反转。这种索引的主要设计目的是为了解决在多实例环境&#xff08;如Oracle RAC&#xff09;中由于索引键值顺序插入导致的索引块争用问题。…

C#环境搭建和入门教程--vs2022之下

目录 1.环境搭建 2.先让程序跑起来 3.C#代码结构 4.变量&#xff0c;输入输出介绍 5.内容输入和类型转换 1.环境搭建 我们的这个c#基础学习主要就是在这个vs2022上面进行的&#xff0c;我们的这个c/c使用的都是这个平台 我们首先检查一下我们的这个环境是不是完全的配置了…

【算法笔记】二分查找 二分答案 (超详细解析,一篇让你搞懂二分)

【算法笔记】二分查找 && 二分答案&#xff08;超详细解析&#xff0c;一篇让你搞懂二分&#xff09; 目录 【算法笔记】二分查找 && 二分答案&#xff08;超详细解析&#xff0c;一篇让你搞懂二分&#xff09;前言一、什么是二分查找&#xff1f;为什么要用二…

vite+vue3快速构建项目+router、vuex、scss安装

安装 Vite npm install -g create-vite-app创建vue3项目 npm init vitelatestnpm i安装依赖 安装veux、router npm install vue-router vuex新建router/index.js&#xff08;自己创建home、login对应页面文件&#xff09; import { createRouter, createWebHistory } from…

python-游戏自动化(三)(实战-豆腐女孩)

前提准备 特别注意&#xff1a; 本节教程所演示的模拟器分辨率设置为 720x1080&#xff08;手机版&#xff09;&#xff0c;电脑分辨率设置大720x1080并且没有设置放大。 今天的课程开始之前我们来回顾一下昨天所学的知识内容&#xff0c;因为今天要学的内容和昨天内容…

828华为云征文 | 华为云Flexusx实例,高效部署Servas书签管理工具的优选平台

前言 华为云Flexus X实例&#xff0c;Servas书签管理工具部署的优选平台&#xff01;828节日特惠&#xff0c;让高效管理您的知识宝藏触手可及。Flexus X实例以其卓越的算力、灵活的资源配置和智能调优技术&#xff0c;为Servas提供了稳定、高效的运行环境。无论是快速访问、安…

链表相关OJ

目录 1、移除链表元素 &#xff08;1&#xff09;题目描述 &#xff08;2&#xff09;算法原理 2、链表的中间结点 &#xff08;1&#xff09;题目描述 &#xff08;2&#xff09;算法原理 3、链表中倒数第K个结点 &#xff08;1&#xff09;题目描述 &#xff0…

ssrf漏洞利用+CTF实例

引发ssrf漏洞的几个函数 file_get_contents() 把整个文件读入一个字符串中&#xff0c;获取本地或者远程文件内容fsockopen() 获得套接字信息curl_exec() 执行一个curl会话&#xff0c;由curl_init()初始化一个新的会话&#xff0c;返回一个curl句柄fopen() 打开文件或者URLre…

【C语言】内存函数详细讲解

文章目录 前言strerror的声明和使用字符串分类函数字符转换函数内存拷贝函数&#xff08;memcpy)memcpy的声明和使用memcpy函数的模拟实现 内存拷贝函数&#xff08;memmove&#xff09;memmove的声明和使用memmove模拟实现 内存比较函数&#xff08;memcmp&#xff09;memcmp的…

如何解决在idea中的hadoop日志错误

在idea中操作hadoop的时候&#xff0c;每次运行代码都会发现有个日志错误&#xff0c;虽然不影响程序运行&#xff0c;但是无法打印日志。这是缺少依赖&#xff0c;和windows上缺少log4j的文件 解决方案&#xff1a; 1、导入slf4j依赖 2、导入hadoop中的log4j文件 1、从hado…

Datawhale X 李宏毅苹果书 AI夏令营 《深度学习详解》第十九章 ChatGPT

19.1 ChatGPT 简介和功能 1、对话框可以输入任何东西 2、可以继续追问 19.2 对于 ChatGPT 的误解 1、第一个误解是 ChatGPT 的回答是罐头讯息 2、另外一个常见的误解是 ChatGPT 的答案是网络搜索的结果 3、那 ChatGPT 真正在做的事情是什么呢&#xff1f;一言以蔽之就是做…

开放式激光振镜运动控制器在Ubuntu+Qt下的文本标刻

开放式激光振镜运动控制器在UbuntuQt下的文本标刻 上节课程我们讲述了如何通过UbuntuQt进行振镜校正&#xff08;详情点击→开放式激光振镜运动控制器在UbuntuQt下的激光振镜校正&#xff09;&#xff0c;本节文本标刻是在振镜校正的前提下实现的。 在正式学习之前&#xff0…

F12抓包08:查看网站Cookie

课程大纲 1、查看Cookie 1. 应用界面查看&#xff1a;按F12进入浏览器的开发者模式 - “应用”&#xff08;Application&#xff09; - Cookie&#xff0c;可查看Cookie并进行增、删、改、查操作。 2. 控制台命令行查看&#xff1a;按F12进入浏览器的开发者模式 - “控制台”&…

2025年第八届计算机图形和虚拟国际会议(ICCGV 2025)即将召开!

2025年第八届计算机图形和虚拟国际会议&#xff08;ICCGV 2025&#xff09;将于2025年2月21-23日在中国成都举行。随着信息技术的飞速发展&#xff0c;计算机图形学与虚拟现实技术正以前所未有的速度重塑着我们的认知世界与交互体验。从沉浸式游戏到精准医疗模拟&#xff0c;从…

坐牢第三十八天(Qt)

1、使用Qt绘画事件处理画一个闹钟 widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QDebug> #include <QPaintEvent>//画画处理事件 #include <QPainter>//画画 #include <QTime> //时间类 #include <QTimer>…

电流互感器电压互感器

一&#xff0c;电流互感器 用途&#xff1a;对信号做精确采样和适当补偿功能&#xff0c;方便对5A以内的交流电进行信号采集。主要作用就是对电流进行测量和取样。 扩展&#xff1a;对应输出模拟交流信号可以调节&#xff0c;可根据电位器&#xff08;调节放大比例&#xff0…

Ali_Yun Port

Ali_Yun Port 云服务器端口

基于云原生向量数据库 PieCloudVector 的 RAG 实践

近年来&#xff0c;人工智能生成内容&#xff08;AIGC&#xff09;已然成为最热门的话题之一。工业界出现了各种内容生成工具&#xff0c;能够跨多种模态产生多样化的内容。这些主流的模型能够取得卓越表现&#xff0c;归功于创新的算法、模型规模的大幅扩展&#xff0c;以及海…

FlinkCDC 3.2.0 新增优点 Pattern Replacement in routing rules

新增优点&#xff1a;Pattern Replacement in routing rules flinkcdc 3.2.0版本相较于3.1.0版本&#xff0c;避免了多表多sink多次写 route 路由的麻烦&#xff0c;类似于统一前后缀的形式多表多sink&#xff0c;通过<>正则&#xff0c;大大减少了书写 官网&#xff1…

【干货分享】Ftrans安全数据交换系统 搭建跨网数据传输通道

安全数据交换系统是一种专门设计用于在不同的网络、系统或组织之间安全地传输数据的软件或硬件解决方案。这种系统通常包含多种安全特性&#xff0c;以确保数据在传输过程中的保密性、完整性和可用性。 安全数据交换系统可以解决哪些问题&#xff1f; 安全数据交换系统主要解…