【c++】【STL】stack类、queue类、deque类详解及模拟

template<class T, class container = vector<T >>
class stack
{
public:
	//函数
private:
	container _con;
};

2.3 构造函数：

这个不用写，因为自动生成的默认构造函数会去调用container对应的容器的默认构造，这里就是vectro的默认构造。

2.4empty

是否为空栈

bool empty()
{
	return _con.empty;
}

2.5size

栈中的元素个数

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

2.6top

获取栈顶元素，注意返回值是传引用

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

2.7push

将某个元素入栈

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

2.8pop

将栈顶弹出

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

三：queue的介绍和模拟

3.3 构造函数：

这个不用写，因为自动生成的默认构造函数会去调用container对应的容器的默认构造，这里就是vectro的默认构造。

3.4empty

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

3.5size

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

3.6front

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

3.7back

两个重载就不用我多说了吧

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

3.8push

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

3.9pop

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

四：deque的介绍

4.1 deque的原理介绍

4.4deque的缺陷与优势

优势：

• 与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
• 与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

劣势：

• 但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，
• 中间元素插入删除时间复杂度高

简单来说，他的规避了vector和list的劣势，他的劣势是没有vector和list那么极端的优势（如vector的随机访问，list的插入删除）。

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

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