一. stack

介绍

stack（栈）是一种容器适配器，专门用在 “后进先出”的场景里，元素的插入和提取只能在容器的一端进行。

stack 这种容器适配器，是把某个特定的类封装起来当作底层容器，还提供一组专门的函数来访问里面的元素。它把特定类当作底层元素，往特定容器的尾部（也就是栈顶）进行压入和弹出操作。

stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

• empty：判断容器是否为空的操作
• back：获取容器尾部元素的操作
• push_back：往容器尾部插入元素的操作
• pop_back：从容器尾部删除元素的操作

比如之前提到的 vector、list 这些容器都支持上面的操作，所以都能当作 stack 的底层容器。

使用

函数说明	接口说明
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部的元素弹出

int main()
{
	ncs::stack<int, vector<int>> st;
	for (size_t i = 0; i < 5; i++)
	{
		st.push(i);
	}
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}


	return 0;
}

stack容器实现

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

		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();//top是底 back是顶
		}

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

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

	private:
		Container _con;
	};

}

二. queue

介绍

队列是一种容器适配器，专门用于 先进先出（FIFO） 的场景：从容器的一端插入元素，从另一端提取元素。

队列以 “容器适配器” 的形式实现 —— 容器适配器的作用是把 “特定容器类”封装为底层容器；而queue会提供一组专门的成员函数，用于访问容器内的元素。元素的入队、出队规则为：从队尾进入队列，从队头离开队列。

队列的底层容器，既可以是 “标准容器类模板” 中的一种，也可以是其他专门设计的容器类。但这类底层容器至少要支持以下操作：

• empty：检测队列是否为空。
• size：返回队列中有效元素的个数。
• front：返回队头元素的引用（可直接访问队头元素）。
• back：返回队尾元素的引用（可直接访问队尾元素）。
• push：在队列尾部插入元素（完成 “入队”）。
• pop：在队列头部移除元素（完成 “出队”）。

标准容器里的deque（双端队列）和list（链表），都满足上述底层容器的要求。默认情况下，若没有为queue指定具体的容器类，会自动使用标准容器deque。

使用

函数声明	接口说明
empty()	检测队列是否为空，是返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

queue容器实现

namespace ncs
{
	template<class T, class Container = list<T>>
	class stack
	{
	public:

		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		
		const T& front()
		{
			return _con.front();
		}		
		const T& back()
		{
			return _con.back();
		}
		size_t size() const
		{
			return _con.size();
		}

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

	private:
		Container _con;
	};

}

三. deque

stack和queue不写默认的底层容器都是deque。

deque (双端队列)：是一种双开口的 “连续” 空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)，与 vector 比较，头插效率高，不需要搬移元素；与 list 比较，空间利用率比较高。

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

底层结构

相对优势

• 与 vector 相比：头插头删操作无需移动大量元素，扩容时也不用搬移大量数据，效率更高；
• 与 list相比：底层由分段连续空间组成（非绝对连续），空间利用率更高，且不需要存储额外的指针等字段。

主要缺陷

最明显的不足是不适合遍历操作。因为在遍历时，deque的迭代器需要频繁检测是否到达某段小空间的边界，这会导致遍历效率较低，因此实际中直接使用 deque 的场景并不多。

为何成为 stack 和 queue 的默认底层容器？

• stack和queue的核心操作无需遍历（因此它们没有迭代器），只需要在固定的一端（stack）或两端（queue）进行操作，刚好避开了deque遍历效率低的缺陷；

具体优势：

• 对 stack 而言，元素增长时，deque 比 vector 的扩容效率更高（无需搬移大量数据）；
• 对 queue而言，元素增长时，deque 不仅效率高，还能更高效地利用内存。正是因为 stack 和 queue 的使用场景完美契合了 deque的优点，同时避开了其缺陷，所以 deque成为了它们的默认底层容器。

四.容器适配器

适配器是一种设计模式（设计模式是一套被反复使用、被多数人知晓、经过分类编目后的代码设计经验总结），作用是将一个类的接口转换为客户期望的 “另一种接口”。

容器适配器的核心特点是：它自身不是容器，而是对其他容器进行封装后再使用的类。

举例来说：queue和stack的实现就属于容器适配器 —— 它们本身不是容器，而是对底层容器（如deque）进行封装后得到的。

从代码层面，能更直观看到这种 “封装底层容器” 的设计，比如模板的典型定义形式：

template<class T, class Con = deque<T>> // Con 代表底层容器的类型