STL stack,queue,deque以及适配器

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

stack

stack的使用

下面是stack库中的接口函数,有了前面的基础,我们可以根据函数名得知函数的作用

函数 说明
stack() 构造空栈
empty() 判断栈是否为空
size() 返回栈中元素个数
top 返回栈顶元素
push() 将值从栈顶压入栈内
pop() 在栈顶出栈

stack模拟实现

栈其实就是一种特殊的vector,因此可以使用vector模拟实现stack
比较容易:

#include <iostream>
#include <vector>
using namespace std;

namespace my_stack
{
	template<class T>
	class stack
	{
	public:
		void push(const T& val)
		{
			_v.push_back(val);
		}

		void pop()
		{
			_v.pop_back();
		}

		T& top()
		{
			return _v.back();
		}

		bool empty()
		{
			return _v.empty();
		}

		size_t size()
		{
			return _v.size();
		}


	private:
		vector<T> _v;
	};
}

queue

queue的使用

函数 说明
queue() 构造空队列
empty() 判断队列是否为空
size() 返回队列中元素个数
front() 返回队头元素的引用
back() 返回队尾元素的引用
push() 在队尾入队
pop() 在队头出队

queue模拟实现

queue的接口中存在头删,用vector实现起来效率太低,所以可以使用list实现

#include <iostream>
#include <list>
using namespace std;


namespace my_queue
{
	template<class T>
	class queue
	{
	public:
		void push(const T& val)
		{
			_lt.push_back(val);
		}

		void pop()
		{
			_lt.pop_front();
		}

		T& front()
		{
			return _lt.front();
		}

		T& back()
		{
			return _lt.back();
		}

		bool empty()
		{
			return _lt.empty();
		}

		size_t size()
		{
			return _lt.size();
		}

	private:
		list<T> _lt;
	};
}

适配器

适配器是一种设计模式,该模式是将一个类的接口转换成客户希望的另一个接口
对已有的东西,进行适配转换

在C语言中,我们习惯用顺序表去实现栈,因为使用顺序表实现栈比较方便
但是也可以用链表去实现,我们如果想去用链表实现栈,还需要再写一套,会比较麻烦

在C++中,有了适配器,不用再实现两遍了
我们可以使用适配器进行实现,这样我们就可以做到数组栈和链表栈秒切换了
在用适配器实现后,平时使用时感觉不到差异,但是两者的底层逻辑完全不同

下面我们用适配器设计出stack

首先我们添加一个模板参数
template<class T,class Container>Container就是适配器
在实例化的时候,我们需要指定适配器是哪一种容器

接下来,把成员变量改为适配器

	template<class T,class Container>
	class stack
	{
	public:
	
	private:
		Container _con;
	};

接下来,我们按照前面模拟实现的stack把所有_v改为_con就可以了

namespace my_stack
{
	template<class T,class Container>
	class stack
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_back();
		}

		T& top()
		{
			return _con.back();
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}


	private:
		Container _con;
	};
}

接下来我们看一下 用适配器实现的数组栈和链表栈

int main()
{
	my_stack::stack<int, vector<int>> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.push(5);
	st.push(6);

	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}//输出 6 5 4 3 2 1
	cout << endl;


	my_stack::stack<int, list<int>> st1;
	st1.push(1);
	st1.push(2);
	st1.push(3);
	st1.push(4);
	st1.push(5);
	st1.push(6);

	while (!st1.empty())
	{
		cout << st1.top() << " ";
		st1.pop();
	}
	//输出 6 5 4 3 2 1
	cout << endl;
}

下面我们也可以使用适配器实现queue

namespace my_queue
{
	template<class T, class Container>
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_front();
		}

		T& front()
		{
			return _con.front();
		}

		T& back()
		{
			return _con.back();
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}

	private:
		Container _con;

	};
}

这里的适配器类型只能是list,不能是vector因为vector中不支持pop_front头删,无法支持queuepop

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


deque

我们看STL中,stackqueue的实现
可以发现它们的适配器默认为deque<T>
STL stack,queue,deque以及适配器,C++,c++,stl,对象,开发语言,数据结构

STL stack,queue,deque以及适配器,C++,c++,stl,对象,开发语言,数据结构
这个deque是什么容器,我们下面来看一看

deque叫双端队列(但不是队列),是一种双开口的“连续空间”的数据结构
STL stack,queue,deque以及适配器,C++,c++,stl,对象,开发语言,数据结构
deque可以在头尾两端进行插入和删除操作,时间复杂度为O(1),效率高,并且支持[]



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

deque中有一段中控数组(本质是指针数组),其中每一个元素指针都指向一个固定大小的缓冲区
STL stack,queue,deque以及适配器,C++,c++,stl,对象,开发语言,数据结构
插入元素先从存入中控数组中间位置指针指向的缓冲区,因为要保证头插和尾插都有空间
如果一个Buff满了,就在其下一个指针指向的Buff中存储数据
如果中控数组满了,扩容即可,对于指针类型的拷贝消耗少

deque相比于vector
极大缓解了扩容的问题,同时解决了头删和头插带来的效率低的问题
但是deque的[]随机访问相对于vector的随机访问还是有差距的,因为要计算随机访问的位置在哪个Buff的哪个位置上

假设要访问位置i上的元素
1.先看i在不在第一个Buff中,如果在就直接找到位置访问
2.如果不在第一个Buff,i-=第一个Buffsize()
在第i/buffsizeBuff
在这个Buffi%buffsize位置上
而vector中的[]就是直接解引用指针,效率高

deque相比于list:
deque支持随机访问
cpu高速访问效率搞
但是deque中间位置元素的插入和删除效率没有list

所以deque的最大价值就在于它的头插,头删,尾插,尾删的效率高
这也正是stackqueue中适配器最需要的特点,所以deque作为stackqueue的默认适配器最合适

用deque为默认适配器实现stackqueue文章来源地址https://www.toymoban.com/news/detail-687874.html

#include <deque>
#include <stack>
#include <list>
#include <iostream>
using namespace std;
namespace my_queue
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_front();
		}

		T& front()
		{
			return _con.front();
		}

		T& back()
		{
			return _con.back();
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}

	private:
		Container _con;

	};
}


namespace my_stack
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_back();
		}

		T& top()
		{
			return _con.back();
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}


	private:
		Container _con;
	};
}

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

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

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

相关文章

  • 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++入门 —— 容器适配器、stack和queue(STL)

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

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

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

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

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

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

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

    2023年04月10日
    浏览(48)
  • 【C++】STL之适配器---用deque实现栈和队列

    目录 前言 一、deque  1、deque 的原理介绍  2、deque 的底层结构  3、deque 的迭代器  4、deque 的优缺点   4.1、优点   4.2、缺点 二、stack 的介绍和使用  1、stack 的介绍  2、stack 的使用  3、stack 的模拟实现 三、queue 的介绍和使用  1、queue 的介绍   2、queue 的使用  3、queue 的模

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

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

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

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

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

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

    2024年02月05日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包