【C++】STL——stack和queue使用及模拟实现

这篇具有很好参考价值的文章主要介绍了【C++】STL——stack和queue使用及模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。
🚁 个人主页:不 良
🔥 系列专栏:🛸C++  🛹Linux
📕 学习格言:博观而约取,厚积而薄发
🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同成长! 🌹


认识deque

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

【C++】STL——stack和queue使用及模拟实现,C++,c++,开发语言,后端

deque是双端队列,对标的是vector加list的合体。

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

【C++】STL——stack和queue使用及模拟实现,C++,c++,开发语言,后端

vector的优缺点:

优点:支持下标随机访问;

缺点:头部或者中部插入删除效率低下;扩容

list的优缺点:

优点:任意位置插入删除效率高效;

缺点:不能支持下标随机访问

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

deque容器是开一个一个的小数组,当数组满了之后再开一个小数组;将这些小数组管理起来的数组是指针数组(中控(指针数组)),最开始使用的指针是中控指针数组中间位置的指针,当进行头插、尾插的时候,就可以直接使用前一个、后一个指针指向新开辟的空间。

【C++】STL——stack和queue使用及模拟实现,C++,c++,开发语言,后端

中控满了之后就扩容,而且deque扩容给代价低,一个小数组对应一个中控数组中的指针,扩容代价低是因为只需要拷贝指针数组中的指针,然后再将原来的空间释放。

头插插入数组尾部,尾插在数组头部:

【C++】STL——stack和queue使用及模拟实现,C++,c++,开发语言,后端

deque支持下标的随机访问,但是效率没有vector高。

deque的下标访问(每个数组大小固定): 假设每个小数组的容量为 10 ,我们想要找到下标为 25 的元素,用下标减去第一个数组内元素的个数,再除以每个小数组的容量就能找到其所在哪一个小数组。比如上图中就用(25 - 3) / 10 。找到对应元素存在于第 2 个数组后,再用 (25 - 3) % 10 就可以知道对应元素是在该小数组中的第几个。

deque容器中间插入删除时候很难搞,可以用size和capacity记录每个数组,可以每个数组不一样大,但是此时随机访问就麻烦了。

与vector比较,deque的优势是:头部插入和删除时,不需要移动元素,效率特别高,而且在扩容时,也不需要移动大量的元素,因此其效率是比vector高的。
与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。

所以deque优点有:

  1. 相比vector,deque扩容代价低;
  2. 头插头删、尾插尾删效率高;
  3. 支持下标随机访问

缺点:

1.中间插入删除后很难搞(当每个数组不一样大时,中间插入删除的效率会变高但是随机访问的效率变低;当每个数组大小固定时,牺牲中间插入删除的效率,随机访问的效率就变高了);

2.没有vector和list优点极致

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

deque适用于什么情况?

如果头插头删多,尾插尾删多可以使用deque容器,所以很适合用作栈和队列的默认底层容器。所以默认作为栈和队列的底层适配容器。

stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以;queue是先进先出的特殊线性数据结构,只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如list。但是STL中对stack和queue默认选择deque作为其底层容器,主要是因为:

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

在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);

queue中的元素增长时,deque不仅效率高,而且内存使用率高。结合了deque的优点,而完美的避开了其缺陷

stack简介

stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。

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

stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:

  • empty:判空操作
  • back:获取尾部元素操作
  • push_back:尾部插入元素操作
  • pop_back:尾部删除元素操作

标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque。

【C++】STL——stack和queue使用及模拟实现,C++,c++,开发语言,后端

stack常用接口

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

库中stack定义方式接口:

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

缺省值为deque容器,说明底层容器为deque,我们也可以根据情况定义,所以定义方式有以下两种:

1.使用默认的适配器定义栈。

stack<int> st;//定义一个存储int类型的栈

2.:使用特定的适配器定义栈。

stack<int, vector<int>> st;//定义一个用vector<int>作为底层容器存储int类型的栈
stack<int, list<int>> st;//定义一个用list<int>作为底层容器存储int类型的栈

使用:

#include <iostream>
#include <stack>
using namespace std;
int main()
{
	stack<int> st;//构造
	//判断是不是空
	cout << st.empty() << endl;//0
	//插入元素
	for (int i = 0; i < 4; i++)
	{
		st.push(i);
	}
	//判断是不是空
	cout << st.empty() << endl;//1
	//打印栈中元素个数
	cout << st.size() << endl;
	//打印,stack不支持迭代器
	for (int i = 0; i < 4; i++)
	{
		cout << st.top() << " ";//打印栈顶元素
		st.pop();//删除
	}
	//输出3 2 1 0
}

stack没有迭代器,所以遍历的时候不能使用范围for。

stack模拟实现

我们用适配器模式/配接器模式,本质是转换也就是把已有的东西进行转换,就好比我们的手机充电器并不能直接使用220v电压,所以提供了一个转换器,将电压转换为适合我们使用的。

设计模式就是指把常见的设计方法进行总结,适配器也是一种设计模式。

我们用已有的容器封装:可以这样定义类模板template<class T,class Container>,Container就是符合我们要求的一个容器。

stack模拟实现主要依赖底层容器中的函数,所以stack模拟实现比较简单,将类模板中的第二个参数默认值为deque容器,目的是让deque作为默认底层容器。

namespace Niu {
	//给类模板中的第二个参数默认值为deque容器
	template<class T,class Container = deque<T>>
	class stack {
	public:
		//实现push
		void push(const T& val)
		{
			//调用容器的push_back函数
			_con.push_back(val);
		}
		//实现pop
		void pop()
		{
			//调用容器的pop_back函数
			_con.pop_back();
		}

		const T& top()
		{
			//调用容器的back函数返回容器最后一个数据
			return _con.back();
		}
		size_t size()
		{
			//调用容器的size函数
			return _con.size();
		}
		bool empty()
		{
			//调用容器的empty函数
			return _con.empty();
		}
	private:
		Container _con;
	};
}

queue简介

队列是一种容器适配器,专门用于在FIFO上下文(先进先出)的环境中操作,其中从容器一端插入元素,另一端提取元素。

队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列。

底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

  • empty:检测队列是否为空
  • size:返回队列中有效元素的个数
  • front:返回队头元素的引用
  • back:返回队尾元素的引用
  • push_back:在队列尾部入队列
  • pop_front:在队列头部出队列

标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。

queue常用接口

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

库中queue定义方式接口:

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

缺省值为deque容器,说明底层容器为deque,我们也可以根据情况定义,所以定义方式有以下两种:

1.使用默认的适配器定义栈。

queue<int> st;//定义一个存储int类型的栈

2.:使用特定的适配器定义栈。

注意queue中底层容器仅可使用deque和list容器,其他容器没有符合的对应操作。

queue<int, list<int>> st;//定义一个用list<int>作为底层容器存储int类型的栈

队列能不能用vector适配?不能,vector不适合头删,使用erase的话效率低。

使用:

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	//判断q队列中是不是为空
	cout << q.empty() << endl;//0
	// 插入元素
	for (int i = 0; i < 5; i++)
	{
		q.push(i);
	}
	//获取队头元素
	cout << q.front() << endl; //0
	//获取队尾元素
	cout << q.back() << endl; //4

	//判断队列是否为空
	cout << q.empty() << endl; //1
	//队列中元素个数
	cout << q.size() << endl; //5
	//删除元素
	for (int i = 0; i < 5; i++)
	{
		cout << q.front() << " ";
		q.pop();//从队头开始删除
	}
	//输出0 1 2 3 4

	return 0;
}

queue模拟实现

queue模拟实现和stack模拟实现差不多,都是通过调用容器的函数来完成对应的功能。

模板声明和定义分离,在不同的文件中,要单独加模板参数,即便加了之后也可能会出错。

模板声明和定义分离会有很多的问题,会产生链接错误。所以模板都定义在.h中就可以,不然会产生未知错误。文章来源地址https://www.toymoban.com/news/detail-542817.html

namespace Niu {
	template<class T , class Container = deque<T>>
	class queue {
	public:
		//判空
		bool empty()
		{
			return _con.empty();
		}
		//在队尾插入元素
		void push(const T& val)
		{
			_con.push_back(val);
		}
		//删除队头元素
		void pop()
		{
			_con.pop_front();
		}
		//返回size大小
		size_t size()
		{
			return _con.size();
		}
		//返回队头元素
		T& front()
		{
			return _con.front();
		}
		//返回队头元素
		const T& front() const
		{
			return _con.front();
		}
		//返回队尾元素

		const T& back() const 
		{
			return _con.back();
		}
		//返回队尾元素
		T& back()
		{
			return _con.back();
		}
	private:
		Container _con;
	};
}

到了这里,关于【C++】STL——stack和queue使用及模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 容器适配器---deque和STL ---stack queue priority_queue的模拟实现 C++

    目录 一、容器适配器 deque原理 deque的缺陷 deque的优势 二、stack的模拟实现  三、queue的模拟实现 四、优先级队列的模拟实现 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户

    2024年02月02日
    浏览(55)
  • 【C++】STL中的容器适配器 stack queue 和 priority_queue 的模拟实现

    适配器是一种设计模式 (设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。 例如我们常见的充电器就是一种适配器,它将我们常用的220V交流电压转化为4,5V (或者其他更高的电

    2023年04月26日
    浏览(61)
  • STL容器适配器 -- stack和queue(使用+实现)(C++)

    栈和队列数据结构+画图分析如果对栈和队列的结构不了解的,可以先看该链接的内容 使用stack时需要头文件 #includestack stack是一种容器适配器,用于具有 后进先出 (LIFO)的环境中。只能从容器的一端(栈顶),执行删除、插入和提取操作。 stack是作为容器适配器实现的,容器

    2024年02月14日
    浏览(63)
  • 【STL】容器适配器stack和queue常见用法及模拟实现

    1.stack介绍及使用 1.1 stack的介绍 stack文档介绍 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。 stack是作为容器适配器被实现的,容器适配器是使用特定容器类的封装对象作为其基础容器的类,提供一

    2024年02月06日
    浏览(48)
  • 带你深入理解“栈”(c语言 c++和stl Stack三个版本的模拟实现)

    目录 一.栈的概念及结构 二.栈的实现(c语言版) 2.1静态增长的栈 2.2动态增长的栈 2.3动态栈的模拟实现    1.栈的初始化   2.入栈  3.出栈 4.获取栈顶元素 5.获取栈中有效数据个数 6.检查栈是否为空 7.栈的销毁 三.C++ 版本模拟实现栈  1.C++版本的源代码 四.c语言版本的源代码

    2024年02月08日
    浏览(45)
  • 【C++】stack、queue模拟实现+仿函数

    铁汁们,今天给大家分享一篇stack、queue模拟实现+仿函数,来吧,开造⛳️ stack是容器适配器,专门用于进行”先进后出”操作的环境中,只能在容器的一端进行数据的插入和删除操作,元素在特定容器的尾部(即栈顶)被压入和弹出。 容器适配器是将特定的类进行封装,将其

    2024年03月19日
    浏览(40)
  • [C++随笔录] stack && queue模拟实现

    🗨️stack的容器适配器应该选什么比较好呢? 首先, stack的特点是 头部入, 尾部出 ⇒ 尾插 和 尾删操作比较频繁 我们前面学过的容器有 vector 和 list, vector 和 list的尾插 和 尾删的时间复杂度是 O(1) , 还是适合做容器适配器的. stack的基本结构 用这个容器对象来进行模拟实现stac

    2024年02月06日
    浏览(43)
  • 【C++】stack与queue的模拟实现

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 stack与queue的实现比较简单,本篇不会有太大的篇幅,但值得我们学习的是『 适配器

    2024年01月24日
    浏览(44)
  • C++:Stack和Queue的模拟实现

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

    2024年03月12日
    浏览(43)
  • 【C++】STL之容器适配器——使用deque适配stack和queue

    个人主页:🍝在肯德基吃麻辣烫 分享一句喜欢的话:热烈的火焰,冰封在最沉默的火山深处。 本文章主要介绍容器适配器的功能,以及一个适配的场景。 容器适配器,按字面意思理解的话,就是用来对一个容器进行匹配的。在C++STL中,容器有:vector,list,deque,map,set等。

    2024年02月16日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包