stack 和 queue 使用及模拟实现

容器适配器

适配器（adaptor）是标准库中的一种通用概念。容器、迭代器和函数都有适配器。适配器是一种设计模式（设计模式是一套被反复使用的、多人知晓的、经过分类编目的、代码设计的经验的总结），该种模式是一个将类的接口转换成另一个需要的接口。

STL标准库种stack和queue的底层结构：
📗stack和queue也可以存储元素，但STL并没有将它们划分到容器里面，而是将其称为容器适配器，因为stack和queue只是对其它容器的接口进行了包装。

stack

stack的介绍

1. 栈是一种容器适配器，专门设计用于后进先出的操作，只能从容器的一端进行插入和提取元素。

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

3. stack的底层容器可以是任何标准的容器类模板或者是一些其它特定的容器类，这些容器类应该支持以下操作：
   🔘empty：判断容器是否为空
   🔘back：获取尾部元素的操作
   🔘push_back：尾部插入元素的操作
   🔘pop_back：尾部删除元素的操作

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

stack接口说明和使用

stack模拟实现

stack底层默认用deque实现，若想用 list、vector 实现，只需要用栈定义对象的时候传合适的适配容器即可。

#include

namespace hy
{
	//template>
	//template>
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		stack() {}
		void push(const T& val) { _con.push_back(val); }
		void pop() { _con.pop_back(); }
		T& top() { return _con.back(); }
		const T& top()const { return _con.back(); }
		size_t size()const { return _con.size(); }
		bool empty()const { return _con.empty(); }
	private:
		Container _con;
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

queue

queue的介绍

1. 队列是一种容器适配器 ，专门设计用于先进先出的操作,其中将元素插入容器的一端，并从另一端提取元素。
2. 队列被实现为容器适配器，这些类使用特定的容器类的封装对象作为其底层容器，并提供一组特定的成员函数来访问其元素。元素从队尾压入，从对头弹出。
3. 底层容器可以是一个标准容器类模板，也可以是一些其它专门设计的容器类。此基础容器应该支持以下操作：
   🔘empty：检测队列是否为空
   🔘size：返回队列中有效元素的个数
   🔘front：返回队头元素的引用
   🔘back：返回队尾元素的引用
   🔘push_back：在队尾压入数据
   🔘pop_back：将队头的数据弹出
4. 标准容器类 deque 和 list 满足了这些要求。默认情况下，若没有为 queue 实例化指定容器而来，则使用标准容器的却。
   

queue接口说明和使用

queue模拟实现

queue的接口存在头删和尾插，用vector来封装效率低下，可以用 list 和 deque 来模拟实现deque。这里我们使用deque作为底层容器。

#include
#include
#include

namespace hy
{
	//list
	template<class T, class Container = deque<T>>

	class queue
	{
	public:
		void push(const T& x) { _con.push_back(x); }
		void pop() { _con.pop_front(); }
		T front() { return _con.front(); }
		T back() { return _con.back(); }
		size_t size() { return _con.size(); }
		bool empty() { return _con.empty(); }
	private:
		Container _con;
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

priority_queue

priority_queue的介绍

1. 优先级队列是一种容器适配器，根据某种严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此环境类似于堆，在堆中可以随时插入元素，并且只能检索最大的堆元素（即优先级队列中位于顶部的元素）。
3. 优先级队列被实现为容器适配器，它们是使用特定容器类的封装对象作为其底层容器的类，并提供一组特定的成员函数来访问其元素。元素从特定容器的尾部弹出，其称为优先级队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其它特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
   🔘empty()：检测容器是否为空
   🔘size()：返回容器中有效元素个数
   🔘front()：返回容器中第一个元素的引用
   🔘push_back()：容器尾部插入元素
5. 标准容器类 vector 和 deque 满足这些要求。默认情况下，若没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器在需要时自动调用算法函数make_heap、push_heap、pop_heap来自动完成此操作。
   

priority_queue接口说明和使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上使用堆算法将vector中元素构造成堆的结构，所以priority_deque就是一个堆，任何需要用到堆的位置，都可以考虑使用priority_queue, priority_queue默认是大堆。

---

🔎若priority_queue中存放的是自定义类型的数据，在使用的时候我们需要在自定义类型中提供 > 或者 < 的重载函数。

🔎默认情况下，priority_queue是大堆，若要创建小堆的priority_queue我们需要将第三个模板参数换成greater的比较方式。

#include
#include
#include

void TestPriorityQueue()
{
	// 默认情况下，创建的是大堆，其底层按照小于号比较
	vector<int> v{ 1,3,8,2,0,6,4,5,9,7 };
	priority_queue<int> pq;
	for (auto& e : v)
		pq.push(e);
	while (!pq.empty())
	{
		cout << pq.top() << " ";  // 9 8 7 6 5 4 3 2 1 0
		pq.pop();
	}
	cout << endl;

	//若要创建小堆，将第三个模板参数换成greater比较方式
	priority_queue<int, vector<int>, greater<int>> pq1(v.begin(), v.end());
	while (!pq1.empty())
	{
		cout << pq1.top() << " "; // 0 1 2 3 4 5 6 7 8 9 
		pq1.pop();
	}
	cout << endl;
}
int main()
{
	TestPriorityQueue();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

priority_queue模拟实现

📚priority_queue的底层结构是堆，所以要模拟实现 priority_queue 我们需要先学会建堆和堆的删除的算法。以大堆为例来看一下。这里也有详解：二叉树初级

堆的向上调整算法

例如：插入一个值为76的数据进堆，然后进行向上调整，直到满足堆的结构。

1. 先将元素插入堆的末尾位置，即堆的最后一个孩子之后。
2. 插入之后若不满足堆的结构，则将新插入的节点顺着向上调整满足堆结构的位置，如下列图示。
   

堆的向上调整算法：

//堆的向上调整算法
void AdjustUp(vector<int>& v,size_t child)
{
	size_t parent = (child - 1) / 2; // 算出child父亲的下标
	while (child > 0 && v[child] > v[parent]) // 若父亲大于孩子且孩子的下标大于0，那么继续调整
	{
		swap(v[child], v[parent]);
		child = parent;
		parent = (child - 1) / 2;
	}
}
1
2
3
4
5
6
7
8
9
10
11

堆的向下调整算法

堆的删除是删除堆顶的数据，将堆顶的数据与最后一个数据交换，然后删除最后一个数据，进行堆的向下调整算法。

1. 将堆顶元素与最后一个元素交换。
2. 删除堆中最后一个元素。
3. 将堆顶元素向下调整直到满足堆的结构。

堆的向下调整算法:

//堆的向下调整算法
void AdjustDown(vector<int>& v,size_t parent,int n)
{
    // child记录左右孩子中较大孩子的小标
	size_t child = parent * 2 + 1;  // 默认左孩子较大
	while (child < n)
	{
	    // 若右孩子存在且比左孩子大，让child改为右孩子下标
		if (child + 1 < n && v[child + 1] > v[child])
			++child;
		
		// 较大孩子的值大于父亲
		if (v[parent] < v[child])
		{
			swap(v[parent], v[child]); // 交换节点
			parent = child;            
			child = parent * 2 + 1;
		}
		else
		{
		    // 满足条件，停止交换
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

priority_queue模拟实现完整代码

注意：向上和向下调整算法中的仿函数比较，传的参数位置不要传反了，否则构建出来的堆结构不正确。

namespace hy
{
	//仿函数的使用，使传模板参数时，可以根据传的比较方式进行灵活的比较
	template<class T>
	struct less
	{
		bool operator()(const T& l, const T& r)const
		{
			return l < r;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& l, const T& r)const
		{
			return l > r;
		}
	};

	//typename的存在是告诉编译时，后面是一个类型名称，需要等后面类模板实例化以后再去里面找这个value_type
	template<class T, class Container = vector<T>, class Compare = less<typename Container::value_type>>
	class priority_queue
	{
	public:
		//创造空的优先级队列
		priority_queue() :_con() {}

		//堆的向上调整算法
		void AdjustUp(size_t child)
		{
			Compare com;

			size_t parent = (child - 1) / 2; // 算出child父亲的下标
			while (child > 0 && com(_con[parent], _con[child])) // 若父亲大于孩子且孩子的下标大于0，那么继续调整
			{
				swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
		}

		//堆的向下调整算法
		void AdjustDown(size_t parent)
		{
			Compare com;

			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++child;
				}
				
				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

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

		void pop()
		{
			if (empty()) //若为空，直接返回
				return;

			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}

		//堆顶元素不能修改，会破坏堆的结构
		const T& top()const
		{
			return _con[0];
		}

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

		int size()const
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

deque(双端队列) - 了解

deque的介绍

1. deque是双端队列（double-ended queue）的不规则首字母缩写。双端队列是具有动态大小的序列式容器，可以在两端(前段或者后端)进行扩展或者收缩。
2. 特定的库可能以不同的方式来实现deques,通常是作为某种形式的动态数组。但是在任何情况下，它们都允许通过随机访问迭代器直接访问单个元素，并根据需要通过扩展和收缩容器自动处理内存。
3. 它们提供了类似 vector 的功能，但可以在序列的开头高效的插入和删除元素，而不仅仅是末尾。不同于 vector 的是 deque 不能保证其所有的元素存储在连续的存储位置：通过偏移指向另一个元素的指针来访问 deque 中的元素会导致未定义的行为。
4. vector 和 deque 都提供了非常相似的接口，也可以用于类似的目的，但是它们内部的工作方式却不同：vector 使用一个单独的数组，需要偶尔重新分配空间以实现增长，而 deque 的元素可以分散在不同的存储块中，容器在内部保持必要的信息，以便在常数时间内通过统一的顺序接口（通过迭代器）直接访问其任何元素。因此，deque 在内部比 vector 更复杂一些，但这允许它们增长的更多。
5. 对于频繁插入或删除开始或结束位置以外的元素的操作，deque 的性能较差，迭代器和引用的一致性不如 vector 和 forward_list.
   

deque的底层结构

deque 底层是一段假象的连续空间，实际上是分段连续的，为了维护其”整体连续”以及随机访问的假象，落在了 deque 的迭代器上，因此 deque 的迭代器设计复杂。具体可以参考侯捷老师的《STL源码剖析》。

vector、list 和 deque 对比

vector :

list :

deque :

🔖deque的缺陷：不适合遍历，在遍历时，deque 的迭代器要频繁检测其是否移动到某段小空间的边界，导致效率低下，在序列式场景中，可能经常需要遍历。在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list ,deque 的应用场景不多，在STL中用其作为 stack 和 queue 的底层数据结构。

为什么选择deque作为stack和queue底层容器？

🖍️stack 和 queue 不需要遍历，只需要在固定的一端或者两端进行插入和删除等操作。

🖍️stack 中元素增长时，deque 比 vector 的效率高，因为不需要挪动大量数据；queue 中的元素增长时，deque 不仅效率高，且内存的使用率高。