一、stack

1. 以vector作为底层容器

从栈的接口中可以看出栈实际是一种特殊的vector因此使用vector完全可以模拟实现stack。

由于stack的所有工作是底层容器完成的而这种具有“修改某物接口形成另一种风貌”的性质称为配接器适配器所以stack往往不被归类为容器而是被归类为容器配接器容器适配器。

template<class T>
class stack
{
private:
		std::vector<T> _c;
public:

	stack() {}
	void push(const T& x)
	{
		_c.push_back(x);
	}
	void pop()
	{
		_c.pop_back();
	}
	T& top()
	{
		return _c.back();
	}
	const T& top()const
	{
		return _c.back();
	}
	size_t size()const
	{
		return _c.size();
	}
	bool empty()const
	{
		return _c.empty();
	}
};

2. 以list作为底层容器

stack的接口push_back、pop_back除vector外list也都具备因此以list作为stack的底层容器一样能够轻易实现stack。

template<class T>
class stack
{
private:
		std::list<T> _c;
public:
	//……
};

这样修改底层成员变量很麻烦可以增加一个模板参数并给缺省值来实现根据传入参数使用不同底层容器的stack

template<class T, class Con = std::vector<T>>
class stack
{
private:
		Con _c;
public:
	//……
};

这样就可以像如下代码使用stack:

stack<int,list<int>> st1;//以list作为底层容器
stack<int> st2//以vector作为底层容器

---

二、queue

因为queue的接口中存在头删和尾插因此使用vector来封装效率太低故可以借助list来模拟实现queue

template<class T, class Con = std::list<T>>
class queue
{
private:
	Con _c;
public:
	queue() {}
	void push(const T& x)
	{
		_c.push_back(x);
	}
	void pop()
	{
		_c.pop_front();
	}
	T& back()
	{
		return _c.back();
	}
	const T& back()const
	{
		return _c.back();
	}
	T& front()
	{
		return _c.front();
	}
	const T& front()const
	{
		return _c.front();
	}
	size_t size()const
	{
		return _c.size();
	}
	bool empty()const
	{
		return _c.empty();
	}
};

查看官方文档发现stack是以deque作为底层容器的缺省那么deque是一种什么样的数据结构呢

---

三、deque

1. deque概述

vector是单向开口的连续线性空间deque双端队列则是一种双向开口的连续线性空间。双向开口是指可以在头尾两端进行插入和删除操作虽然vector可以在头尾操作但是头部操作效率极低。

deque和vector、list的比较

1. 与vector相比deque在头部插入删除是常数时间
2. 与list相比deque空间利用率比较高

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

图中的map并不是STL中的map它其实是一个T**也就是说它是一个指针指向的东西是一个指针数组这些指针又指向了一块连续空间

2. deque迭代器介绍

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

那deque是如何借助其迭代器维护其假想连续的结构呢

由于最后一个缓冲区还有4个空间push三次不会引起缓冲区的再配置。如果尾端再添加一个元素则引发新缓冲区的配置finish迭代器改变此时使用了4个节点。

3. deque的缺陷

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

与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。

但是deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到 某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历。

因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作 为stack和queue的底层数据结构

4. 选择deque作为底层默认容器的原因

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不仅效率高而且相较于list内存使用率高。

从以上可以看出deque是vector和list的折中。

STL标准库中对于stack和queue的模拟实现只需要将默认容器改为deque

template<class T, class Con = std::deque<T>>
class stack
{
private:
		Con _c;
public:
	//……
};
template<class T, class Con = std::deque<T>>
class queue
{
private:
		Con _c;
public:
	//……
};

---