来喽，STL的栈和队列！

[TOC]

1.Stack

栈是一个遵循LIFO规则的容器，即后进先出（last in first out）。后放入容器内的数据会先出来。

如果你不太理解栈的性质，可以先看看我写的C语言栈的博客【链接】

打开Cplusplus一看，栈的函数肉眼可见的少。这和我们C语言实现的功能基本是一样的。

image-20220718185545464

它甚至没有拷贝构造！

image-20220718185609965

1.1 容器适配器

等会，这个container是什么玩意？

别急，先让我们来看看栈的类定义👇

1
2
std::stack
template <class T, class Container = deque<T> > class stack;

和之前不同的是，这里出现了container，和一个我们好像没有接触过的deque

搜索后得知，deque也是一种容器，被称为双端队列

image-20220718185741066

  • 那么栈为什么需要一个容器呢？

实际上，栈不是直接写出来的代码，而是借用了deque这个容器，进行封装后的结果。

意思就是，栈其实是解用了别人的代码！

比如deque有头插头删，尾插尾删。而我们的栈只需要尾插尾删，那么我们包装一下deque，只提供尾插尾删的函数，不就成了栈了？

image-20220718190148404

1.2 模拟实现

直接这么说可能有点干巴巴，我们直接上代码！

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

private:
	Container _con;
};

以上便是栈的模拟实现代码！

What？这就结束了？——甚至写的比我们C语言版本的栈更少！

QQ图片20220419102702

本质上，我们只需要创建一个Container的对象_con，再借助这个对象的函数进行封装，就完成了一个栈！

因为模板里面默认传入的是deque，所以这里用的便是deque的函数了。这就好比函数传入了一个缺省值。你可以将deque换成其他有尾插尾删函数的容器，比如vector

测试一下，莫得问题！

image-20220718190826657

2.queue

和栈不同，队列遵循FIFO，即先进先出（first in first out）

image-20220718191052856

同样的，我们只需要包装一下容器，即可完成模拟实现

1
2
std::queue
template <class T, class Container = deque<T> > class queue;

2.1 模拟实现

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
template<class T, class Container = deque<T>>
class queue {
public:
	size_t size()const{
		return _con.size();
	}
	const T& front(){
		return _con.front();
	}
	const T& back(){
		return _con.back();
	}
	void push(const T& val){
		_con.push_back(val);
	}
	void pop(){
		_con.pop_front();
	}
	bool empty(){
		return _con.empty();
	}

private:
	Container _con;
};

需要注意的是，队列就不能用vector来当作容器辣！因为vector头插删的效率很低，需要挪动数据。我们可以使用list来当作容器

image-20220718191157819

当然，你可以把头插头删改成insert和erase，但是那样没有意义，依旧拖慢了效率

因为栈和队列压根不支持迭代器，自然也没有迭代器失效问题！

2.2 关于queue的front

学习linux课程的时候，突然想到一个问题，如果queue里面是空的，那么我直接访问front会是什么情况？会出现异常吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;

int main()
{

    printf("hello vscode!\n");
    queue<int> q;//不会报错，但是数据无效
    cout << q.front() << endl;
    return 0;
}

在linux下用g++编译运行，发现获取到的值是0

1
2
3
[muxue@bt-7274:~/git/test]$ ./test
hello vscode!
0

简单概括，如果队列中没有数据，此时调用front接口不会报错，但是获取到的数据是无效的。

个人猜测，这里能否获取到数据也和编译器的优化有关。比如相同的代码，在vs2019下，会直接报assert错误！

image-20230116101936473

所以，为了代码的兼容性，请严格检查调用front的时候队列里面有没有数据，stack的top同理

了解完相对简单的栈和队列之后，我们可以直接来看看优先级队列

3.priority_queue 优先级队列

优先级队列和queue同属于头文件<queue>

1
2
template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;
  • 那么它和普通的队列有什么不同呢？

优先级队列是一个堆，且默认是大堆

如果你不知道堆是什么，可以看看我之前C语言数据结构的博客【链接】

简单说来，堆的堆顶（这里是第一个数据）一直保持着最大值或者最小值。每一次插入、删除操作，都需要向上、向下重新调整容器内元素的位置

3.1 make_heap

这里简单说一下另外一个函数make_heap，这个函数可以通过迭代器区间，将区间内的数据调整为一个堆。

image-20220718191900669

在文档介绍里面可以看到，最后一行提到了优先级队列就是自动调用make_heap函数来维护自己堆的属性的

image-20220718191924148

3.2 函数接口

优先级队列本质上还是一个队列，它提供的函数也很少

不同的是，这里的top堆顶指的是容器中首个元素，pop也是移除堆顶元素

image-20220718192010887

3.3 仿函数

image-20220718193035799

注意这里出现了第三个模板参数，Compare

这是一个仿函数，其就是一个类，但是仿照了函数的调用方式

想做到这一点，我们需要重载()操作符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//仿函数，重载（）操作符
	template<class T>
	struct less {
		bool operator()(const T& a, const T& b)const
		{
			return a < b;
		}
	};
	//大于比较
	template<class T>
	struct greater{
		bool operator()(const T& a, const T& b)const
		{
			return a > b;
		}
	};

比如这里的less和greater就是两个仿函数，优先级队列需要用它来进行比较。这样我们就可以快速在大堆和小堆直接进行切换。

它们的使用方式和函数是一样的！不过在使用之前，我们需要先创建一个对象

1
2
less func;
func(1,2);

库函数中的less和greater都在<functional>这个头文件中

image-20220718193351898

  • std库中优先级队列默认传的less小于比较，为大堆！
  • 我们可以手动传入greater，即可变成小堆

3.4 模拟实现

在3.3中，我们已经实现出了库函数中的less和greater这两个仿函数，接下来我们只需要包装一下优先级队列的接口，即可使用！

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
template <class T, class Container = vector<T>,class Compare = less<T> >
	class priority_queue
	{
	public:
		size_t size()const {
			return _con.size();
		}
		const T& top() {
			return _con[0];
		}
		bool empty() {
			return _con.empty();
		}

		//向上调整
		void AdjustUp(size_t child)
		{
			Compare comFunc;
			while (child > 0)
			{
				size_t parent = (child - 1) / 2;
				if (comFunc(_con[parent],_con[child]))//小堆，小的数据往上调
				{
					std::swap(_con[parent], _con[child]);
					child = parent;
				}
				else
				{
					return;
				}
			}
		}
		//向下调整
		void AdjustDown(size_t parent)
		{
			Compare comFunc;
			size_t child = parent * 2 + 1;//左孩子
			while (child < _con.size())
			{

				//找左右孩子中小的那一个
				if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1]))
				{//如果左孩子大于右孩子，则选择右孩子
					child++;
				}

				if (comFunc(_con[parent],_con[child]))
				{
					std::swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					return;
				}
			}

		}

		//因为是优先级队列，所以需要进行调整
		//默认情况下第一个元素始终是最大元素
		void push(const T& val) 
		{
			_con.push_back(val);
			AdjustUp(_con.size() - 1);
		}
		void pop() 
		{
			assert(!_con.empty());
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();

			AdjustDown(0);
		}
		
	private:
		Container _con;
	};

这里需要注意的便是adjustdown/up这两个用来维持堆属性的调整函数，你可以看我之前的博客，里面有关于这部分的详细解释！回到上面

先来测试一下默认大堆的属性

image-20220718193801786

可以看到，打印出来的数据是按从大到小顺序存放的！

如果我们显示传入greatre仿函数，就会变成从小到大

image-20220718193855093

同时，即便我们pop了一部分数据，也不会影响堆的属性

image-20220718193935842

优先级队列在一部分地方可以用于帮我们找到一段数据中的topK和第n个最大/小的数据

比如下面这道leetcode OJ题目215. 数组中的第K个最大元素

image-20220718194052981

我们只需要pop掉前面的K-1个元素，这时候的堆顶就是我们需要的第K个最大值

4.deque

前面已经提到了deque这个容器，它拥有的库函数和vector很相似，这里我们不关注如何使用这个容器，而是来谈谈这个“双端队列”相比于vector/list有没有什么优势

1
2
std::deque
template < class T, class Alloc = allocator<T> > class deque;

4.1存储结构

deque最特殊的就是它的存储结构了。它并不是一个连续的结构，也不像链表一样每个数据都有自己的单独节点

这个是百度百科上找到的一张图片

img

https://www.cnblogs.com/yifengs/p/15190416.html

其实deque有点类似二维数组，其中有一个头指针指向队列头，一个尾指针指向队列尾部。主数组“中控器”存放的则是这些数组的指针。注：每一个数组的容量大小都是一样的，所以存放在中间的数组一定是满的！

image-20220718200026705

这样我们就避免了list节点分散，需要多次开空间，无法随机访问的缺陷；又可以灵活快速地进行头插头删操作，而不需要挪动数据。

当然，deque的随机访问性能肯定不如数据连续存储的vector，其更适合下面的场景：

  • 需要高性能的头插头删，尾插尾删
  • 偶尔需要进行随机访问

结语

关于栈和队列的部分到这里就结束辣！

我们还认识了双端队列deque，以及让其作为容器的模拟实现操作

有任何问题，欢迎评论提出！