【C++】STL中stack,queue容器适配器的模拟实现(使用deque容器)

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

🌏博客主页: 主页
🔖系列专栏: C++
❤️感谢大家点赞👍收藏⭐评论✍️
😍期待与大家一起进步!



前言

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

虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque
【C++】STL中stack,queue容器适配器的模拟实现(使用deque容器),c++,java,开发语言,list
【C++】STL中stack,queue容器适配器的模拟实现(使用deque容器),c++,java,开发语言,list

一、deque的一些基本知识

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

【C++】STL中stack,queue容器适配器的模拟实现(使用deque容器),c++,java,开发语言,list
【C++】STL中stack,queue容器适配器的模拟实现(使用deque容器),c++,java,开发语言,list

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

【C++】STL中stack,queue容器适配器的模拟实现(使用deque容器),c++,java,开发语言,list

相比vector:

1.极大缓解了扩容问题以及头插头删问题
2.deque的下标访问不够极致,遇上遍历的时候要拉跨很多
3.deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下

相比list:

1.可以支持下标访问
2.cpu高速缓存效率不错
3.和list一样头插头删效率可以,但中间插入删除效率很拉跨

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

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

  2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高

高频的头插头删,尾插尾删很合适文章来源地址https://www.toymoban.com/news/detail-616444.html

二、stack模拟实现

namespace simulation {
	template<class T,class Container=deque<T>>
	class stack {
	public:
		void push(const T& x) {
			_con.push_back(x);
		}
		void pop() {
			_con.pop_back();
		}
		T& top() {
			return _con.back();
		}
		size_t size() {
			return _con.size();
		}
		bool empty() {
			return _con.empty();
		}


	private:
		Container _con;
	};
}

三、queue的模拟实现

namespace simulationQ {
	template<class T,class Container=deque<T>>
	class queue {
	public:
		void push(const T&x) {
			_con.push_back(x);
		}
		void pop() {
			_con.pop_front();
		}
		T& front() {
			return _con.front();
		}
		T& back() {
			return _con.back();
		}
		size_t size() {
			return _con.size();
		}
		bool empty() {
			return _con.empty();
		}
	private:
		Container _con;
	};
 
	 
}

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

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

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

相关文章

  • 【C++】STL之容器适配器——使用deque适配stack和queue

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

    2024年02月16日
    浏览(54)
  • 【C++入门到精通】C++入门 —— 容器适配器、stack和queue(STL)

    文章绑定了VS平台下std::stack和std::queue的源码,大家可以下载了解一下😍 前面我们讲了C语言的基础知识,也了解了一些数据结构,并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载,引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象

    2024年02月12日
    浏览(44)
  • C++初阶:容器适配器介绍、stack和queue常用接口详解及模拟实现

    介绍完了list类的相关内容后:C++初阶:适合新手的手撕list(模拟实现list) 接下来进入新的篇章,stack和queue的介绍以及模拟: stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。 stack是作为容器适配器

    2024年02月19日
    浏览(41)
  • STL: 容器适配器stack 与 queue

      目录 1.容器适配器 1.1 STL标准库中stack和queue的底层结构 1.2 deque的简单介绍(了解) 1.2.1 deque的原理介绍 1.2.2 deque的缺陷 1.2.3 为什么选择deque作为stack和queue的底层默认容器 2. stack的介绍和使用 2.1 stack的介绍  2.2 stack的使用 2.3 利用deque模拟实现stack 3.queue的介绍和使用 3.1 queue的

    2024年02月05日
    浏览(43)
  • 【C++】容器适配器--stack&queue&deque

    设计模式 设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结,是解决特定问题的一系列套路。它不是语法规定,而是一套用来提高代码可用性,可维护性,可读性,稳健性以及安全性的解决方案 迭代器模式 迭代器模式(Iterator Pattern) :提供

    2023年04月10日
    浏览(46)
  • [C++] STL_priority_queue(优先级队列) 的使用及底层的模拟实现,容器适配器,deque的原理介绍

    priority_queue文档介绍 翻译: 1. 优先队列是一种 容器适配器 ,根据严格的弱排序标准, 它的第一个元素总是它所包含的元素中最大的。 2. 此上下文类似于 堆 , 在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。 3. 优先队列被实现为容器适配

    2024年02月04日
    浏览(40)
  • STL stack,queue,deque以及适配器

    下面是stack库中的接口函数,有了前面的基础,我们可以根据函数名得知函数的作用 函数 说明 stack() 构造空栈 empty() 判断栈是否为空 size() 返回栈中元素个数 top 返回栈顶元素 push() 将值从栈顶压入栈内 pop() 在栈顶出栈 栈其实就是一种特殊的 vector ,因此可以使用 vector 模拟实

    2024年02月10日
    浏览(38)
  • 【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

    这篇文章我们接着上一篇的内容,再来学一个STL里的容器适配器—— priority_queue (优先级队列) 1.1 priority_queue的介绍 我们上一篇文章学了 queue (队列),那优先级队列也是在 queue 里面的: 和 queue 一样, priority_queue 也是一个容器适配器,那他和 queue 有什么区别呢?我们一

    2024年02月07日
    浏览(41)
  • 【C++干货铺】适配器 | stack | queue

    ========================================================================= 个人主页点击直达: 小白不是程序媛 C++系列学习专栏: C++干货铺 代码仓库: Gitee ========================================================================= 目录 stack的介绍和使用 stack的介绍 stack的使用 queue的介绍和使用 queue的介绍 qu

    2024年02月05日
    浏览(43)
  • 【C++从入门到放弃】stack和queue的深度剖析及空间适配器的介绍

    🧑‍💻作者: @情话0.0 📝专栏:《C++从入门到放弃》 👦个人简介:一名双非编程菜鸟,在这里分享自己的编程学习笔记,欢迎大家的指正与点赞,谢谢!   此篇博客将谈及到的stack、queue和priority_queue都不是STL的标准容器,而是一种空间适配器。它是通过对一种容器进行

    2024年02月11日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包