【C++干货铺】适配器 | stack | queue

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

=========================================================================

个人主页点击直达:小白不是程序媛

C++系列学习专栏:C++干货铺

代码仓库:Gitee

=========================================================================

目录

stack的介绍和使用

stack的介绍

stack的使用

queue的介绍和使用

queue的介绍

queue的使用

容器适配器

什么是适配器

STL中stack和queue的底层结构

deque的介绍

deque的缺陷

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

stack的模拟实现

queue的模拟实现


stack的介绍和使用

stack的介绍

【C++干货铺】适配器 | stack | queue,C++干货铺,c++,开发语言,学习,适配器,栈stack,队列queue,数据结构

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

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

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

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

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

【C++干货铺】适配器 | stack | queue,C++干货铺,c++,开发语言,学习,适配器,栈stack,队列queue,数据结构 

stack的使用

函数名称

函数作用

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

【C++干货铺】适配器 | stack | queue,C++干货铺,c++,开发语言,学习,适配器,栈stack,队列queue,数据结构 


queue的介绍和使用

queue的介绍

【C++干货铺】适配器 | stack | queue,C++干货铺,c++,开发语言,学习,适配器,栈stack,队列queue,数据结构 

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

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

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

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

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

【C++干货铺】适配器 | stack | queue,C++干货铺,c++,开发语言,学习,适配器,栈stack,队列queue,数据结构

queue的使用

函数名称 函数作用
queue() 构造空的队列
empty() 检测队列是否为空,是返回true,否则返回false
size() 返回队列中有效元素的个数
front() 返回队头元素的引用
back() 返回队尾元素的引用
push() 在队尾将元素val入队列
pop() 将队头元素出队列
	queue<int> qu;
	qu.push(1);
	qu.push(2);
	qu.push(3);
	qu.push(4);
	qu.push(5);
	cout << qu.size() << endl;
	while (!qu.empty())
	{
		cout << qu.front() << " ";
		qu.pop();
	}

【C++干货铺】适配器 | stack | queue,C++干货铺,c++,开发语言,学习,适配器,栈stack,队列queue,数据结构 


容器适配器

什么是适配器

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

【C++干货铺】适配器 | stack | queue,C++干货铺,c++,开发语言,学习,适配器,栈stack,队列queue,数据结构

STL中stack和queue的底层结构

虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque。

deque的介绍

deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:

可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。 

【C++干货铺】适配器 | stack | queue,C++干货铺,c++,开发语言,学习,适配器,栈stack,队列queue,数据结构

deque不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组, 其底层结构如下图所示:

【C++干货铺】适配器 | stack | queue,C++干货铺,c++,开发语言,学习,适配器,栈stack,队列queue,数据结构

双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落在了deque的迭代器身上,因此deque的迭代器设计就比较复杂,如下图所示: 

【C++干货铺】适配器 | stack | queue,C++干货铺,c++,开发语言,学习,适配器,栈stack,队列queue,数据结构

【C++干货铺】适配器 | stack | queue,C++干货铺,c++,开发语言,学习,适配器,栈stack,队列queue,数据结构 

deque的缺陷

  • 与vector比较,deque的优势是:

头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是必vector高的。

  • 与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。
  • 但是,deque有一个致命缺陷

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

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

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

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

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

结合了deque的优点,而完美的避开了其缺陷。


stack的模拟实现

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

容器适配器默认缺省为deque,但是对于stack的特点:尾插尾删;使用vector和list都可以。


queue的模拟实现

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

queue和stack的默认缺省适配器也是deque,但是对于queue的特点:头删尾插;适配器可以使用list,不可以使用vector因为对于vector来说头删需要移动数据,不是很方便。


今天对适配器以及stack和queue的介绍、使用、模拟实现的分享到这就结束了,希望大家读完后有很大的收获,也可以在评论区点评文章中的内容和分享自己的看法。您三连的支持就是我前进的动力,感谢大家的支持!! !

 文章来源地址https://www.toymoban.com/news/detail-755498.html

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

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

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

相关文章

  • C++初阶:容器适配器介绍、stack和queue常用接口详解及模拟实现

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

    2024年02月19日
    浏览(44)
  • 容器适配器---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)
  • 【C++】STL中stack,queue容器适配器的模拟实现(使用deque容器)

    🌏博客主页: 主页 🔖系列专栏: C++ ❤️感谢大家点赞👍收藏⭐评论✍️ 😍期待与大家一起进步! 虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和

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

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

    2024年02月11日
    浏览(44)
  • 适配器模式实现stack和queue

    适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。 虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器

    2024年02月11日
    浏览(47)
  • 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日
    浏览(47)
  • STL stack,queue,deque以及适配器

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

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

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

    2024年02月06日
    浏览(48)
  • 【C++】容器适配器之priority_queue & 仿函数

    我们和学习之前的容器一样,可以使用cplusplus官网进行学习:priority_queue文档介绍 priority_queue(优先级队列)是一种容器适配器,它 和queue使用同一个头文件,其底层结构是一个堆,并且默认情况下是一个大根堆,此外,priority_queue也不支持迭代器,这是为了不破坏堆的结构使用

    2024年02月01日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包