【STL】stack、queue基本使用和模拟实现

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

目录

前言

stack

接口介绍

模拟实现

queue

接口介绍

模拟实现

没有迭代器 

deque介绍


前言

stack 和 queue 本质上是一种容器配接器,就像我们平时充电时使用的电源适配器,能够将电压转换成设备能够接受的程度。

其通过封装特定容器作为其底层容器的类,通过一组特定的成员函数来实现结构的功能。


stack

【STL】stack、queue基本使用和模拟实现

🍑stack 就是 STL 中封装好的栈,在使用的时候我们不仅可以指定内部的数据类型,还可以指定内部的容器

🍑不指定容器其实也是可以的,内部的模板参数有一个缺省值

int main()
{
	stack<int, vector<int>> s1;     //内部容器为vector
	stack<int, list<int>> s2;       //内部容器为list
    stack<int> s3;                  //内部为默认容器deque
	return 0;
}

接口介绍

🍑库中还提供了一系列的接口,我们以前如何使用栈就如何使用 stack 即可,下面用一系列代码来示例一下。 

【STL】stack、queue基本使用和模拟实现

int main()
{
	stack<int> s;
	s.push(5);          //5
	s.push(6);          //5 6
	s.push(7);          //5 6 7
	s.push(8);          //5 6 7 8
	cout << s.size() << endl;   //打印栈的大小
	while (!s.empty())        //直到栈为空循环
	{
		cout << s.top() << endl;   //打印栈顶元素
		s.pop();                   //出栈
	}
	return 0;
}

 【STL】stack、queue基本使用和模拟实现

模拟实现

🍑根据库中接口简单地实现一下 stack,需要注意的是这里复用的接口需要确保几个底部容器都要同时拥有

namespace Alpaca
{
	template<class T,class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& x)    //入栈
		{
			_con.push_back(x);   //设置尾端为栈顶,入栈即尾插
		}

		void pop()               //出栈
		{
			_con.pop_back();
		}

		const T& top()           //获取栈顶元素
		{
			return _con.back();  //获取最后一个元素
		}

		size_t size()            //获取栈的大小
		{
			return _con.size();  //返回容器的大小
		}

		bool empty()              //栈的判空
		{
			return _con.empty();  //返回容器的判空
		} 

	private:
		Container _con;      //容器对象
	};
}

queue

🍑queue 则是封装出来的队列,与 stack 相反遵循着先进先出的原则(FIFO)。

【STL】stack、queue基本使用和模拟实现

🍑通过查询资料我们还发现,要作为 queue 的容器还需要支持以下操作:

【STL】stack、queue基本使用和模拟实现

🍑同样,使用 queue 时模板参数有两个,分别是内部元素的类型和内部容器,且内部容器缺省为 deque。

int main()
{
	queue<int> q1;                //传递缺省模板参数
	queue<int, list<int>> q2;     //指定内部容器为list
	return 0;
}

接口介绍

🍑队列与栈相反,其只在队尾入队,在队头出队。我们可以通过实例代码简单使用一下。

【STL】stack、queue基本使用和模拟实现

int main()
{
	queue<int> q;
	cout << "size is: " << q.size() << endl;   //查看队列大小
	q.push(1);                                 //数据入队
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	cout << "size is: " << q.size() << endl;   
	cout << "first is: " << q.front() << endl; //查看首元素
	cout << "last is: " << q.back() << endl;   //查看最后一个元素
	while (!q.empty())                         //直到队空循环
	{
		cout << q.front() << " ";              //打印队头
		q.pop();                               //出队
	}
	cout << endl;
	cout << "size is: " << q.size() << endl;   //查看队列大小
	return 0;
}

模拟实现

🍑由于是泛型在使用的时候并不会对内部函数进行提示,简单理解就是我们复用对应容器的接口来实现队列的接口函数

namespace Alpaca
{
	template<class T,class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& x)        //入队
		{
			_con.push_back(x);       //尾插
		}

		void pop()                   //出队
		{
			_con.pop_front();        //头删
		} 

		const T& front()             //获取队头元素
		{
			return _con.front();
		}

		const T& back()              //获取对尾元素
		{
			return _con.back();
		}

		size_t size()                //获取队列大小
		{
			return _con.size();      //获取容器大小
		}

		bool empty()                 //队列判空
		{
			return _con.empty();     //容器判空
		}

	private:
		Container _con;
	};

}

没有迭代器 

🍑因为无论是 stack 和 queue 都是根据其特定的顺序进行元素的插入和删除,因此二者都不提供走访功能,也不提供迭代器。

deque介绍

🍑在出现 vector 和 list 之后,有人想到 vector 能够随机读取,但扩容和随机插入删除效率较低,而 list 插入删除效率都极高却无法随机访问,能不能实现一个结构能够同时兼顾 vector 和 list 的优点呢?

🍑于是 deque 就诞生了,deque 又叫双端队列,即一种双向开口的连续线性空间

【STL】stack、queue基本使用和模拟实现

🍑为了兼顾双端插入以及随机访问,deque 的底层是使用一个中控数组来管理一个个连续的空间,且第一个空间被开辟出来后是存放在中控数组的中央位置,之后不断插入数据,若一块连续空间已满只需要再开一块连续空间即可。也就是在中控数组中再增加一个指针。

🍑若是进行头插,则需要开辟一段新空间,将新的值存于连续空间的尾部

【STL】stack、queue基本使用和模拟实现

🍑得益于这种结构,即便是扩容所带来的拷贝消耗也是极低的,实际上不会像 vector 那样复杂的深拷贝,而只是对中控数组中的指针进行拷贝。同时  deque 也支持随机访问,只要直到每个连续空间的大小通过简单的计算便可以实现随机访问。

🍑若 deque 有这么多的有点,那为什么它还没有取代 vector 和 list 呢?这就不得不提到 deque 最为鸡肋的地方了,中部的插入删除操作相当复杂,若是直接在中部插入就要挪动当前空间的数据,更甚者还要牵扯到接下来的连续空间。不仅如此 deque 提供的优点不如 vector 和 list 那样极致,这也是为什么 deque 代替不了二者的原因。

🍑但若是有一种容器并不需要中间的插入删除,只需要在两端进行插入删除呢?于是 deque 就成为了适合 stack 和 queue 实现的内部容器


🍑好了,今天 stack、queue基本使用和模拟实现 的相关内容到这里就结束了,如果这篇文章对你有用的话还请留下你的三连加关注。文章来源地址https://www.toymoban.com/news/detail-471361.html

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

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

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

相关文章

  • 【C++】STL中的容器适配器 stack queue 和 priority_queue 的模拟实现

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

    2023年04月26日
    浏览(59)
  • 容器适配器---deque和STL ---stack queue priority_queue的模拟实现 C++

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

    2024年02月02日
    浏览(52)
  • C++入门之stl六大组件--stack和queue源码深度剖析及模拟实现

    目录 前言 一、stack的介绍和使用 1.stack的介绍 2.stack的使用 3.stack的模拟实现 二、queue的介绍和使用 1.queue的介绍 2.queue的使用 3.queue的模拟实现 三、priority_queue的介绍和使用 1.priority_queue的介绍 2.priority_queue的使用 3.priority_queue的模拟实现 3.1解决一个topK问题 四、容器适配器 1

    2024年02月14日
    浏览(47)
  • STL之stack+queue的使用及其实现

    所属专栏:C“嘎嘎\\\" 系统学习❤️ 🚀 博主首页:初阳785❤️ 🚀 代码托管:chuyang785❤️ 🚀 感谢大家的支持,您的点赞和关注是对我最大的支持!!!❤️ 🚀 博主也会更加的努力,创作出更优质的博文!!❤️ stack的文档介绍 stack是一种容器适配器,专门用在具有后进先

    2024年02月21日
    浏览(28)
  • STL容器适配器 -- stack和queue(使用+实现)(C++)

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

    2024年02月14日
    浏览(60)
  • [STL]stack和queue使用介绍

    stack介绍 stack是一种 容器适配器 ,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。 stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为

    2024年02月15日
    浏览(31)
  • 【STL】priority_queue的使用及模拟实现

    目录 前言 priority_queue的使用 功能解析 基本接口 写点题目 模拟实现 结构解析 插入删除 调整函数结合仿函数 仿函数介绍 结合使用 其他功能 接口补齐 迭代器区间构造 🍾打开 queue 头文件后,我们发现除了我们之前介绍过的普通队列以外,还有一个 priority_queue 。 🍾其又名为

    2024年02月08日
    浏览(38)
  • 【STL】stack与queue的底层原理及其实现

    (图片来自知乎) 1.stack是一种 容器适配器 ,模拟了栈的数据结构。数据只能从一端进去,另一端出来( 先进后出 )。 2.stack适配器 默认是由 deque 容器实现 的,也可以显示要求stack的底层封装的容器类型。由于栈的特性, array 和 forward_list 不能用来构造stack适配器 。 3.st

    2024年04月10日
    浏览(43)
  • 【STL详解 —— priority_queue的使用与模拟实现】

    std::priority_queue 是 C++ 标准库中的容器适配器,它提供了一种基于堆的优先级队列实现。优先级队列是一种特殊的队列,其中的元素按照一定的优先级顺序排列,而不是按照它们被插入的顺序。 在 std::priority_queue 中,插入元素时会根据元素的值自动进行排序,最大(或最小)

    2024年04月17日
    浏览(31)
  • stack&queue的模拟实现

    stack模拟: stack的源代码: stack的全部源代码就这些。 stack的代码少,原因在于采用了适配器模式,所谓适配器,以电器为例,每个电器都有电源适配器,中国的家用电源为220V的交流电,但是几乎没有电器需要220V的交流电,所以每个电器都有一个电源适配器,将家庭电压转换

    2024年02月06日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包