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

举报
跳动的bit 发表于 2022/08/30 07:28:47 2022/08/30
【摘要】 💦 为什么选择deque作为stack和queue的底层默认容器也就是说 stack 为啥不用 vector 作为默认容器;queue 为啥不用 list 做为默认容器 ❓stack 是一种后进先出的特殊线性数据结构,因此只要具有 push_back and pop_back 操作的线性结构,都可以作为 stack 的底层容器,比如 vector and list 都可以;queue 是...

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

也就是说 stack 为啥不用 vector 作为默认容器;queue 为啥不用 list 做为默认容器 ❓

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

  1. stack 和 queue 不需要遍历 (因此 stack and queue没有迭代器),只需要在固定的一端或者两端进行操作。
  2. 在 stack 中空间增长时,deque 比 vector 的效率高 (扩容时不需要搬移大量数据);queue 中的元素增长时,deque 不仅效率高,而且内存使用率高。

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

💦 STL标准库中对于stack和queue的模拟实现

1、stack的模拟实现
#include<vector>
#include<list>
#include<deque>
#include<iostream>
using namespace std;

namespace bit
{
	//stack是一个Container适配(封装转换)出来的,且它是一个缺省参数,deque容器,但是它的功能是不变的,所以叫做容器适配器
	template<class T, class Container = deque<T>>
	class stack
	{
	//Container的尾认定是栈顶
	public:
		void push(const T& x)//先进
		{
			_con.push_back(x);
		}
		void pop()//后出
		{
			_con.pop_back();	
		}
		const T& top()
		{
			//不能用[],因为如果是list就不支持了,back更为通用
			return _con.back();	
		}
		size_t size()
		{
			return _con.size();	
		}
		bool empty()
		{
			return _con.empty();	
		}
	private:
		Container _con;
	};
	void test_stack()
	{
		//stack<int, std::vector<int>> st;
		//stack<int, std::list<int>> st;
		stack<int> st;
		st.push(1);
		st.push(2);
		st.push(3);	

		while(!st.empty())
		{
			cout << st.top() << " ";
			st.pop();	
		}
		cout << endl;
	}
}
int main()
{
	bit::test_stack();
	return 0;	
}
2、queue的模拟实现
#include<vector>
#include<list>
#include<deque>
#include<iostream>
using namespace std;

namespace bit
{
	//stack是一个Container适配(封装转换)出来的,且它是一个缺省参数,deque容器
	template<class T, class Container = deque<T>>
	class queue
	{
	//Container的尾认定是队尾,头是队头
	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;
	};
	void test_queue()
	{
		//queue<int, std::vector<int>> qu;//err,因为vector不支持头删接口,所以不能适配
		//queue<int, std::list<int>> qu;
		queue<int> qu;
		qu.push(1);
		qu.push(2);
		qu.push(3);	

		while(!qu.empty())
		{
			cout << qu.front() << " ";
			qu.pop();	
		}
		cout << endl;
	}
}
int main()
{
	bit::test_queue();
	return 0;	
}
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。