STL--stack queue deque

stack

一、stack介绍

stack是一种容器适配器,专门设计用于后进先出,其中元素仅从容器的一端插入和提取

template <class T, class Container = deque<T> > class stack;

二、stack接口

函数名称功能说明
empty判断容器是否为空
size返回容器容量大小
top返回栈顶数据
push从栈顶插入元素
pop删除栈顶元素

三、stack模拟实现

#pragma once
#include<iostream>
#include<vector>
#include<list>
using std::cout;
using std::endl;

namespace mystack
{
	// 适配器模式/配接器
	template<class T,class Container = std::vector<T>>
	//默认为容器栈
	//类模板半缺省,默认为数组栈
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();
		}
		bool size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
		//通过已有容器适配,从而实现链式栈,数组栈
		//vector<T> _v;
	};



	void test_1()
	{
		stack<int, std::vector<int>> st1;
		st1.push(1);
		st1.push(2);
		st1.push(3);
		st1.push(4);
		st1.push(5);
		while (!st1.empty())
		{
			cout << st1.top() << " ";
			st1.pop();
		}
		cout << endl;
	}
}

queue

一、queue介绍

queue是一种容器适配器,专门用于在先进先出操作,其中从容器一端插入元素,另一端提取元素

template <class T, class Container = deque<T> > class queue;

二、queue接口 

函数名称功能说明
empty判断容器是否为空
size返回容器容量大小
top返回栈顶数据
push从栈顶插入元素
pop删除栈顶元素

三、queue模拟实现

#pragma once
#include<iostream>
#include<vector>
#include<list>
using std::cout;
using std::endl;

namespace myqueue
{
	// 适配器模式/配接器
	template<class T, class Container = std::list<T>>
	//默认为链式队列
	//类模板半缺省,默认为数组栈
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();
		}
		bool size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;

	};



	void test_1()
	{
		queue<int> q1;//默认为链式队列
		q1.push(1);
		q1.push(2);
		q1.push(3);
		q1.push(4);
		q1.push(5);
		while (!q1.empty())
		{
			cout << q1.top() << " ";
			q1.pop();
		}
		cout << endl;
	}
}

deque

一、deque介绍

Deque(通常发音为“deck”)double-e nded queue的不规则首字母缩略词

deque是具有动态大小的序列容器,可以在两端(正面或背面)扩展或收缩

允许通过随机访问迭代器直接访问单个元素,并通过根据需要扩展和收缩容器来自动处理存储。

deque相当于是vector+list。但与vector不同在于,deque不能保证将所有的元素保存在连续的存储位置。deque 容器存储数据的空间是由一段一段等长的连续空间构成,各段空间之间并不一定是连续的,可以位于在内存的不同区域

deque容器通过一个数组来存放各个连续空间的首地址,也就是说deque数组中存放的全是指针,指针指向的连续空间用于存储数据,后面将这款连续区域称为buffer

deque会将每一个连续空间存储满之后,才将数据存放置下一个连续空间

一般用于stack与queue的底层数据结构

优点缺点

1.相比于vector,扩容代价低。只需要扩容存放指针的数组

2.头插头删,尾插尾删效率高

3.支持随机访问(效率没有vector高)

1.buffer固定大小,中间插入删除困难,随机访问较易(一般情况是固定大小)

2.buffer不固定大小,中间插入删除较易,随机访问困难

3.优势不像vector与list突出

4.不适合遍历,需要频繁检验是否到达buffer边界

template < class T, class Alloc = allocator<T> > class deque;

二、deque接口

1.容量操作:

函数名称功能说明
empty检测deque是否为空,是返回true,否则返回false
size返回数组大小

2.访问与遍历:

函数名称功能说明
begin+end返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin+rend返回第一个元素的reverse_iterator,即end位置。返回最后一个元素下一个位置的reverse_iterator,即begin位置
front返回deque的第一个元素的引用
back返回deque的最后一个元素的引用

3.修改操作:

函数名称接口说明
push_front在deque首元素钱插入值为val的元素
pop_front 删除deque中的第一个元素
push_back在deque尾部插入值为val的元素
pop_back删除deque最后一个元素
insert在deque position位置中插入值为val的元素
erase删除deque position位置的元素
swap交换两个deque中的元素
clear清空deque中的有效元素

STL库中deque实现stack与queue

#include<deque>
#include <list>
namespace my_stl
{
	template<class T, class Con = std::deque<T>>
	//template<class T, class Con = list<T>>
	class queue
	{
	public:
		queue() {}
		void push(const T& x) { _c.push_back(x); }
		void pop() { _c.pop_front(); }
		T& back() { return _c.back(); }
		const T& back()const { return _c.back(); }
		T& front() { return _c.front(); }
		const T& front()const { return _c.front(); }
		size_t size()const { return _c.size(); }
		bool empty()const { return _c.empty(); }
	private:
		Con _c;
	};


	template<class T, class Con = std::deque<T>>
	//template<class T, class Con = vector<T>>
	//template<class T, class Con = list<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:
		Con _c;
	};
}

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

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

相关文章

软考--快速掌握七层模型与各种协议的划分

目录 协议族 网络层涉及的协议 传输层涉及的协议 应用层涉及的协议 协议族 认识几个协议族&#xff0c;所谓协议族就是说他不是单一的协议。而是很多协议拼在一起的。 TCP/IP协议族是internet的标准协议族&#xff0c;所以使用广&#xff0c;但是tcp/ip协议族传输效率是比较…

【刷题笔记】不要二+把字符串转换为整数

一、不要二 题目&#xff1a; 牛客网链接&#xff1a;不要二_牛客题霸_牛客网 描述 二货小易有一个W*H的网格盒子&#xff0c;网格的行编号为0~W-1&#xff0c;网格的列编号为0~H-1。每个格子至多可以放一块蛋糕&#xff0c;任意两块蛋糕的欧几里得距离不能等于2。 对…

深度学习技巧应用12-神经网络训练中批归一化的应用

大家好,我是微学AI,今天给大家介绍一下深度学习技巧应用12-神经网络训练中批归一化的应用,在深度学习中,批归一化(Batch Normalization,简称BN)是一种重要的技巧,它在许多神经网络中都得到了广泛应用。本文将详细介绍批归一化的原理和应用,并结合PyTorch框架构建一个简…

排队论_M/M/1/inf/inf 问题

例:某修理店只有一一个修理工人&#xff0c;来修理的顾客到达数服从泊松分布&#xff0c;平均每小时4人;修理时间服从负指数分布&#xff0c;平均需6分钟。求: (1)修理店空闲的概率; (2)店内有3个顾客的概率; (3)店内至少有1个顾客的概率; (4)店内顾客的平均数; (5)顾客在店内的…

Android系统启动流程(三)——属性服务

1 属性服务 属性服务的启动在init进程中&#xff0c;init进程初始化的第二阶段初始化中启动了属性服务。 system/core/init/init.cpp int SecondStageMain(int argc, char** argv) {...PropertyInit();...StartPropertyService(&property_fd);...2 启动属性服务 system/…

Vue Emelent-UI表格合并行或列rowspan和colspan的作用

Vue Element-UI的table组件支持合并行或者列&#xff0c;在这里做个简单的学习笔记。 我们可以通过rowspan和colspan来进行单元格合并&#xff0c;那么这两个属性是什么意思呢&#xff0c;通过官方给的demo来探讨下。 上述单元格将行index为奇数的第一列和第二列合并为一个单…

从【连接受限】看Android网络

从连接受限看Android网络 现象摸索从通知开始是Handler发的通知看看NetworkStateTrackerHandler NetworkMonitor做了什么NetworkMonitor是一个状态机CaptivePortalProbeResult从何而来连接受限的直接原因 嗅探是怎样进行的ProbeThread 回过头看看InternalHanderregisterNetwork…

【自然语言处理】【大模型】CodeGeeX:用于代码生成的多语言预训练模型

CodeGeeX&#xff1a;用于代码生成的多语言预训练模型 《CodeGeeX: A Pre-Trained Model for Code Generation with Multilingual Evaluations on HumanEval-X》 论文地址&#xff1a;https://arxiv.org/pdf/2303.17568.pdf 相关博客 【自然语言处理】【大模型】CodeGen&#x…

十分钟教你搭建类似ChatGPT的安卓应用程序

大家好&#xff0c;我是易安&#xff01; Chat GPT 是当今著名的人工智能工具&#xff0c;就像聊天机器人一样。Chat GPT会回答发送给它的所有查询。今天&#xff0c;我将通过集成 OpenAI API (ChatGPT)构建一个简单的类似 ChatGPT 的 android 应用程序&#xff0c;我们可以在其…

C++ MFC调用JS代码获取返回值

C有时候会需要调用JS代码&#xff0c;这对于C来说或者对于国内来说一直是比较蛋疼的问题&#xff0c;主要是资料少&#xff0c;微软提供了一个COM组件&#xff0c;里面包含有JS引擎&#xff0c;这个组件就是&#xff1a;msscript.dll。 此文件在C:\Windows\SysWOW64目录下&…

基于springboot的4S店车辆管理系统(源码等)

摘 要 随着信息技术和网络技术的飞速发展&#xff0c;人类已进入全新信息化时代&#xff0c;传统管理技术已无法高效&#xff0c;便捷地管理信息。为了迎合时代需求&#xff0c;优化管理效率&#xff0c;各种各样的管理系统应运而生&#xff0c;各行各业相继进入信息管理时代&…

浅谈osgEarth操控器类的createLocalCoordFrame函数如何将局部坐标系的点转为世界坐标系下的Martix(ENU坐标)

在osgEarth操控器类的EarthManipulator中的如下函数&#xff1a; void EarthManipulator::setLookAt(const osg::Vec3d& center,double azim,double pitch,double range,const osg::Vec3d& posOffset) {setCenter( center );.... //…

10个优秀设计网站盘点

从平面广告设计、包装设计和标志设计到游戏特效&#xff0c;都与我们的生活息息相关。过去&#xff0c;设计师依靠一张图纸和一支笔&#xff0c;但进入数字时代后&#xff0c;设计工作从图纸转移到了电脑上。 各种设计网站和在线设计工具相继衍生&#xff0c;简化了工作步骤&a…

备战花了2个月,春招3轮顺利拿下字节offer

PART1&#xff1a;个人情况简介 菜 J 一枚&#xff0c;本硕都是计算机&#xff08;普通二本&#xff09;&#xff0c;2021 届应届硕士&#xff0c;软件测试方向。个人也比较喜欢看书&#xff0c;技术书之类的都有看&#xff0c;最后下面也会推荐一些经典书籍。 先说一下春招结…

使用宝塔在Linux面板搭建网站,并实现公网远程访问「内网穿透」

文章目录 前言1. 环境安装2. 安装cpolar内网穿透3. 内网穿透4. 固定http地址5. 配置二级子域名6. 创建一个测试页面 转载自远程内网穿透的文章&#xff1a;Linux使用宝塔面板搭建网站&#xff0c;并内网穿透实现公网访问 前言 宝塔面板作为简单好用的服务器运维管理面板&#…

【LeetCode】-66. 加一

1. 题目 66. 加一 给定一个由 整数 组成的 非空 数组所表示的非负整数&#xff0c;在该数的基础上加一。 最高位数字存放在数组的首位&#xff0c; 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外&#xff0c;这个整数不会以零开头。 2. 示例 输入&#xff1a;dig…

【Nodejs】Express实现接口

介绍 Express 是一个第三方模块&#xff0c;用于快速搭建服务器 类似于jquery与DOMExpress 是一个基于 Node.js 平台&#xff0c;快速、开放、极简的 web 开发框架。express保留了http模块的基本API&#xff0c;使用express的时候&#xff0c;也能使用http的APIexpress还额外封…

Vue3学习笔记

我目前接手公司的项目是Vue2&#xff0c;但是马上就要接触Vue3的项目了&#xff0c;把Vue3学习一下 1.Vue 3 1.1 简介 2020年9月18日&#xff0c;Vue.js发布3.0版本&#xff0c;代号&#xff1a;One Piece&#xff08;海贼王&#xff09; 耗时2年多、2600次提交、30个RFC、60…

运维——ssh无法登录云服务器

0x00 概述 一般来讲&#xff0c;无法登录ssh的原因挺多&#xff0c;如果无法登录云服务器&#xff0c;则除了要检查ssh端口是否放行&#xff0c;防火墙状态外&#xff0c;还需要检查云服务器web控制台入站规则是否开放了对应端口。如果你前面检查都是正常&#xff0c;那么还需…

静态库和动态库的制作与使用

1.静态库的制作与使用 小知识&#xff1a;删除命令行&#xff0c;或者是配置好的路径之类的&#xff1a;退出编辑模式后&#xff1a;dd 保存并退出&#xff1a;退出编辑模式后&#xff0c;&#xff1a;wq (1)静态库的制作 1.首先生成你需要加入的文件的.O文件。使用如下代码 …
最新文章