一、stack的介绍和使用

1. 简介

stack文档介绍

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。

2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

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

   empty：判空操作

   back：获取尾部元素操作

   push_back：尾部插入元素操作

   pop_back：尾部删除元素操作

4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

2. 使用

接口名称	功能说明
stack()	无参构造空栈
empty()	判断是否为空
size()	获取有效元素个数
top()	获取栈顶元素的引用
push()	入栈
pop()	出栈

3. 模拟实现

namespace bit
{
	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();
		}

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

	private:
		Container _con;
	};
}

二、queue的介绍和使用

1. 简介

queue的文档介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。

2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

   empty：检测队列是否为空

   size：返回队列中有效元素的个数

   front：返回队头元素的引用

   back：返回队尾元素的引用

   push_back：在队列尾部入队列

   pop_front：在队列头部出队列

4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

2. 使用

接口名称	功能说明
queue()	无参构造空队列
empty()	判断是否为空
size()	获取有效元素个数
front()	获取队头元素的引用
back()	获取队尾元素的引用
push()	队尾入栈
pop()	队头出栈

3. 模拟实现

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

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

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

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

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

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

private:
	Container _con;
};

三、容器适配器

1. 简介

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设

计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

• 迭代器也是一种设计模式

2. STL标准库中的使用

STL标准库中stack和queue的底层结构：

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque

四、deque（了解）

1. 简介

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：

可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。（功能上为vector和list的结合体，就像骡子）

2. 底层原理

2.1 底层空间

（既不像vector那样使用一整块连续空间，也不像list那样全部使用节点，而是使用一小块一小块的连续空间 (buffer数组) 存储数组，然后使用一个指针数组存储这些小数组的指针）

• 每个buffer数组长度相同，一个存满后就再开辟一个
• 指针数组（中控数组）中存储buff数组首元素的地址（按顺序存储）

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

2.2 模拟访问元素

1. 方法：

   设buffer数组长度为N，访问第x个元素：

   1. 从指针数组中找buffer：

      i = x / N ，找到该元素位于第i个buffer数组

   2. 从buffer中找元素：

      j = x % 10，找到该元素位于对应buffer数组的第j个位置

2. 实例：

   

3. 思考：

   头插时，新创建的buff数组未满，该方法是否有问题？

2.3 迭代器

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

---

---

---

2.4 STL源码片段摘要

• 迭代器相关定义

  

  ---

  

• 模拟迭代器遍历调用过程

  

• 下标访问

  

3. 缺陷和使用场景

1. deque中间位置进行插入和删除也需要挪动元素，效率不高（等同于vector）
2. 下标[]访问 在大量访问情景（如排序）下 效率远不及vector

• 结论：

  给stack和queue作默认适配容器很合适：

  1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。

  2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

五、priority_queue

1. 简介

priority_queue（优先队列)：

默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用

• 默认情况下priority_queue是大堆。

• 底层容器：默认为vector，需支持随机访问迭代器。

• 堆维护：通过自动调用相关算法函数保持堆结构。

• 使用场景：这些特性使得优先队列在需要频繁插入和检索最大元素的场景中非常高效。

2. 使用

接口名称	功能说明
priority_queue()/priority_queue(first,last)	空构造 / 迭代器区间构造
empty( )	判断是否为空
top( )	获取顶部元素
push(x)	插入
pop( )	删除顶部元素

void TestPriorityQueue()
{
	// 默认情况下，创建的是大堆，其底层按照小于号比较
	vector<int> v1 = { 3,2,7,6,0,4,1,9,8,5 };
	priority_queue<int> q1(v1.begin(), v1.end());

	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}
	cout << endl;
	// 如果要创建小堆，将第三个模板参数换成greater比较方式（greater为一个仿函数，我们后面会进行讲解）
	priority_queue<int, vector<int>, greater<int>> q2(v1.begin(), v1.end());
	while (!q2.empty())
	{
		cout << q2.top() << " ";
		q2.pop();
	}
}

3. 模拟实现

0. 仿函数

• 定义：就是一个重载了operator() 的类，使得该类的对象可以像函数一样使用（代替C语言的函数指针）

• 简单示例：

  template<class T>
  class compare
  {
  public:
  	bool operator()(const T& x, const T& y)
  	{
  		return x == y;
  	}
  };
  
  
  int main()
  {
  	compare<int> f1;
  
  	//f1.operator()(10, 5); 一般类对象调用成员函数
  	f1(10, 5); //仿函数，像函数一样使用
  
  	return 0;
  }
  

• 大于和小于比较

  template<class T>
  class myless
  {
  public:
  	bool operator()(const T& x, const T& y)
  	{
  		return x < y;
  	}
  };
  
  template<class T>
  class mygreater
  {
  public:
  	bool operator()(const T& x, const T& y)
  	{
  		return x > y;
  	}
  };
  

1. 整体结构

template<class T, class Container = vector<T>, class Compare = myless<T>>
class priority_queue
{
public:

	//... 各类函数接口

private:
	Container _con;
}

2. 构造

//1. 强制生成默认构造（无参）
priority_queue() = default;

//2. 迭代器区间构造
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		_con.push_back(*first);
		++first;
	}

	for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
	{
		adjust_down(i);
	}
}

3. 向上调整

void adjust_up(int child)
{
	Compare comfunc; //定义仿函数对象
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//if(_con[parent] < _con[child])
		if(comfunc(_con[parent], _con[child]))
		//if (comfunc.operator()(_con[parent], _con[child]))
		{
			swap(_con[parent], _con[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

4. 向下调整

void adjust_down(int parent)
{
	Compare comfunc; // 同上

	size_t child = parent * 2 + 1;
	while (child < _con.size())
	{
		//if (child + 1 < _con.size() && _con[child] < _con[child] + 1)
		if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1]))
		{
			++child;
		}

		//if (_con[parent] < _con[child])
		if (comfunc(_con[parent], _con[child]))
		{
			swap(_con[parent], _con[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

5. 插入

void push(const T& x)
{
	_con.push_back(x);
	adjust_up(_con.size() - 1);
}

6. 删除

void pop()
{
	swap(_con[0], _con[_con.size() - 1]);
	_con.pop_back();

	adjust_down(0);
}

7. top / size / empty

const T& top()
{
	return _con[0];
}

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

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

总结

本文介绍了stack，list，deque，priority_queue，并对其中重点接口进行了模拟实现，以便读者了解其底层逻辑，有利于更好地使用。
尽管文章修正了多次，但由于水平有限，难免有不足甚至错误之处，敬请各位读者来评论区批评指正。