【C++】STL容器适配器栈和队列及优先队列&容器适配器

一，栈stack和队列queue的使用

1.stack的介绍

stack我们都很熟悉，在数据结构中stack（栈）是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作

在C++中，stack是作为容器适配器实现的，容器适配器我们下面会详解讲解，简单来说就是底层封装了其他容器，这里可以看到stack的默认容器是deque，deque我们也会在下面进行讲解，在此之上又提供了特定的函数来访问元素。

---

下面直接来看使用

2. stack的使用

---

我们先来看构造：
：
因为stack是容器适配器，所以其构造也是用的其底层容器的构造

stack<int> first;                    
stack<int,std::vector<int> > second;  
  
1
2
3

注：这里也可以指定容器来做stack的底层容器

---

stack是一个后进先出的结构，所以他的接口也不多，我们在数据结构部分已经熟悉，比较简单我们这里不做过多介绍

3. queue的介绍

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

queue的默认容器也是deque

4. queue的使用

队列的接口也比较少，我们也不做过多介绍

二，容器适配器

1. 什么是容器适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口

下面的图可以形象的理解容器适配器的作用：

举个例子，我们要模拟实现一个栈或者一个队列，是先用一个顺序表或者链表，再在其上封装了栈或队列的对应操作的接口，使其有了栈/队列的功能，这就是容器适配器。stac/queue的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类分别支持相关操作即可。

2. deque的简单介绍

对于deque也只做简单了解即可。

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

deque既可以头插头删也可以为尾插尾删，甚至也可以支持[]访问，这么一个看起来集list和vector的优势为一体的容器的底层结构还是太复杂的，下面我们来看一下其结构：

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，中间的中控数组是链表结构，其每个指向的空间是一段连续空间。

---

当然deque也不是全是优点，不然我们的学的数据结构为什么不直接学deque而是学list和vector呢 (手动狗头)，

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

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

3. 为什么选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不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷

三，模拟实现STL中的stack和queue

知道了容器适配器和deque后，我们实现起来就比较容易了。stack和queue的底层容器都是deque，我们模拟实现也按照STL库中实现。

1. stack模拟实现

因为默认容器也可以指定，所以我们的容器也是一个模板参数

template<class T,class Container = deque<T>>
class mystack {
public:
	//....
private:
	Container _con;
};
1
2
3
4
5
6
7

---

stack的构造和其他一些操作都是复用的底层容器的，所以这里直接上代码:

template<class T,class Container = deque<T>>
class mystack {
public:
	mystack() {
	//这里会调用底层容器的构造函数
	}

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

	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
22
23
24
25
26
27
28
29
30
31
32
33
34
35

2. queue模拟实现

queue的模拟实现和stack一样

template<class T,class Container = deque<T>>
class myqueue {
public:
       myqueue() {
            //调用其底层容器的构造
        }

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

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

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

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

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

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

        }

        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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

三，优先队列 priority_queue

1. priority_queue的介绍

在队列中还有优先队列priority_queue，优先队列也是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。其本质其实就是大堆，底层容器是vector，又在vector之上构建了堆，所以默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector

注：这里默认是大堆

这里可以看到模板参数有三个，第三个参数是仿函数（默认是less），仿函数我们下一节介绍，用来控制底层是大堆还是小堆，

2. priority_queue的使用

优先队列的接口也比较少，我们可以熟悉一下：

3. 模拟实现priority_queue

我们知道了优先队列的底层是由vector构建的堆后，因此模拟实现时只需对其进行封装即可
实际上这里要用到仿函数，所以这里我们先只实现大堆，不用仿函数

---

基本框架

template<class T,class Container = vector<T> >
class my_priority_queue {
public:
	my_priority_queue() 
	{}
	//...
private:
	Container _con;
};
1
2
3
4
5
6
7
8
9

---

我们在数据结构中知道，堆的插入删除需要向上调整和向下调整来保证其结构的完整性

void Adjust_up(int child) {
	int parent = (child - 1) / 2;
	while (child > 0) {
		if(_con[child] > _con[parent])
		{					
			swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

void Adjust_down(size_t parent) {
	Compare com;
	size_t child = parent * 2 + 1;
	while (child < _con.size()) {
		if (child + 1 < _con.size() && child+1<_con.size()) {//child+1<_con.size()判断有右孩子,
			++child;//找到大的那个孩子节点
		}
		if(_con[parent] < _con[child])
		{
			swap(_con[child], _con[parent]);
			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
26
27
28
29
30
31
32
33

---

完整代码：

template<class T,class Container = vector<T> >
class my_priority_queue {
public:
	my_priority_queue() 
	{}
	
	void Adjust_up(int child) {
		int parent = (child - 1) / 2;
		while (child > 0) {
			if(_con[child] > _con[parent])
			{					
				swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else {
				break;
			}
		}
	}
	
	void Adjust_down(size_t parent) {
		Compare com;
		size_t child = parent * 2 + 1;
		while (child < _con.size()) {
			if (child + 1 < _con.size() && child+1<_con.size()) {//child+1<_con.size()判断有右孩子,
				++child;//找到大的那个孩子节点
			}
			if(_con[parent] < _con[child])
			{
				swap(_con[child], _con[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else {
				break;
			}
		}
	}
	
	void push(const T& x)
	{
		_con.push_back(x);

		Adjust_up(_con.size() - 1);
	}

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

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

	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
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

---

至此我们讲解了C++的STL的容器，我们可以看出C++面向对象的优势和便捷，下一节我们将继续感受C++面向对象的魅力。