C++ stack、queue以及deque

时间:2024-05-02 13:45:42

1、stack和queue常用接口

严格来说栈和队列的实现是容器适配器
1、常用接口:
栈:top、push、pop、size、emptystack - C++ Reference (cplusplus.com)

队列:top、push、pop、swap、size、emptyqueue - C++ Reference (cplusplus.com)

2、deque:双端队列

deque - C++ Reference (cplusplus.com)
queue使用的是deque实现的
deque是一个比较复杂的容器
结合了list和vector的优势
但是,在结构的设计上做出了必要的牺牲
deque是一个一个的小数组,小数组的大小N固定
每一个小数组使用一个中控数组控制
中控数组内部是每一个小数组的开始位置
访问数据第i个数据时:
小数组就是i/N
小数组内部的位置是i%N
同时,中控数组从中间开始开辟,这是为了支持尾插和头插
尾插就是在中控数组空间的右边开辟小数组,进行小数组的头插
头插就是在中控数组空间的左边开辟小数组,但是是小数组的尾插

尽管deque结构的设计使得其在尾插和头插方面具备了list和vector不具备的优势
但是,这样的结构设计也导致了一个致命的弱点:
1、中间插入很麻烦
2、[]访问相对不快,没有vector快
所以说,中间插入不如list,访问遍历不如vector
但是综合来说,已经不错了
所以说,stack和queue的底层是使用deque实现的,因为基本不会有中间插入的场景

3、容器适配器设计模式


栈:

#pragma once
#include<vector>
using namespace std;

namespace myspace
{

	template <class T, class Container = vector<T> >
	class stack
	{
	public:

		void push(const T& val)
		{
			_con.push_back(val);
		}

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

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

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

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

	private:
		Container _con;
	};

};

队列:

#pragma once
#include<deque>
//使用deque实现
using namespace std;

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

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


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

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

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

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


	private:
	Container	_con;

	};





}