c++-stack和queue

---

前言

---

一、stack栈

1、stack介绍

1.stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2.stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3.stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作
4.标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。
我们可以看到stack是一个模板，并且该模板有两个模板参数，第一个模板参数为stack中要存的类型，而第二个模板参数就可以指定stack的底层容器，可以看到第二个模板参数的缺省值为deque，即默认情况下stack底层使用deque。
没有迭代器了，这是因为stack已经不是容器了，而是容器适配器。

2、stack使用

int main()
{
	stack<int,vector<int>> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}

	cout << endl;
	cout << st.size() << endl;



	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3、stack练习题

3.1 最小栈

题目链接

3.2 栈的弹出压入序列

题目链接

3.3 逆波兰表达式求值

题目链接

想要知道什么是逆波兰表达式，我们就需要了解一下中缀表达式和后缀表达式。
中缀表达式就是运算符在两个操作数中间，而后缀表达式就是运算符在两个操作数后面，因为计算机只能从左向右依次执行表达式，而不能根据运算符的优先级而先计算优先级高的运算符再计算优先级低的运算符，所以中缀表达式一般都会转换为后缀表达式使用计算器求值。
我们使用后缀表达式计算表达式的值时需要借助一个栈。
根据后缀表达式求结果分为两个步骤：
(1). 遍历后缀表达式，遇到表达式的操作数时就将操作数入栈。
(2). 当遇到表达式的操作符时，取栈顶的两个操作数进行运算，然后将运算结果重新入栈，直到遍历完后缀表达式，此时栈里面的那个值就是最后的结果。
下面的例子中后缀表达式为： 1 2 3 * + 4 -。我们先将1 2 3操作数入栈。

然后再遍历后缀表达式时遇到了 * 运算符，此时我们需要将栈顶的两个操作数出栈，需要注意的是第一个出栈的元素为右操作数，第二个出栈的操作数为左操作数，然后进行运算。最后我们再将运算结果进栈。

然后我们继续向后遍历后缀表达式，下一个运算符为 + 号，所以我们需要将栈里面的两个操作数进行出栈，并且计算结果，最后将结果进行入栈。

然后我们继续向后遍历后缀表达式，下一个为操作数，所以我们直接将操作数进行入栈。

然后继续向后遍历后缀表达式，遇到下一个为 - 号，所以先将栈中出栈两个操作数，然后计算出结果，并且将结果进行入栈。然后后缀表达式遍历完，此时栈中还有一个元素，这个元素的值就是后缀表达式的结果。

上面的步骤就是我们使用代码实现后缀表达式求值的逻辑，然后我们使用这个逻辑编写下面的代码来解决这个oj题。

class Solution {
public:
    //vector里面的每一个元素都是string对象
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        //数据多时一般都是使用引用遍历。
        for(auto& str : tokens)
        {
           if(str == "+" || str == "-" || str == "*" || str == "/")
           {
               int right = st.top();
               st.pop();
               int left = st.top();
               st.pop();
               //因为switch()里面需要是整型或整型表达式，所以要取出str[0]，即取出一个字符进行比较
               switch(str[0])
               {
                   case '+':
                    st.push(left+right);
                    break;
                    case '-':
                    st.push(left-right);
                    break;
                    case '*':
                    st.push(left*right);
                    break;
                    case '/':
                    st.push(left/right);
                    break;
               }
           }
           else
           {
               st.push(stoi(str));
           }
        }
        //最后栈中的元素的值就是后缀表达式的结果。
        return st.top();
    }
};

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

上面的代码中我们求出了后缀表达式的结果，那么如果给我们一个中缀表达式，我们该怎么将中缀表达式转换为后缀表达式进行计算呢？其实将中缀表达式转为后缀表达式也需要借助一个栈。
下面为中缀表达式转为后缀表达式的步骤：
(1)遍历中缀表达式，遇到操作数就直接输出，即存入到后缀表达式要存的空间中。
(2)遇到操作符有两种情况。
a. 栈为空时，操作符直接进栈。
b. 栈不为空时，将该操作符与栈顶的操作符比较优先级，如果该操作符比栈顶的操作符优先级高，则将该操作符进栈，然后继续遍历中缀表达式；如果该操作符的优先级比栈顶的操作符优先级低或相等，此时将栈顶操作符进行输出，然后继续将该操作符与栈顶操作符进行优先级比较。
下面为将中缀表达式1 + 2 * 3 - 4转换为后缀表达式的过程。当遇到操作数时，直接输出到后缀表达式中，当遇到操作符时，因为此时栈为空，所以操作符直接进栈。

然后我们继续遍历中缀表达式时遇到操作符 * ，并且此时栈不为空，所以我们需要将 *与栈顶操作符 + 进行比较，因为 * 优先级高于 + 号，所以 * 会进栈，然后向后继续遍历遇到操作数，则直接输出。

再向后遍历时又遇到 - 操作符，然后将 - 操作符与栈顶的 * 操作符进行优先级比较，因为 - 操作符优先级小于 * 号优先级，所以会将栈顶的 * 操作符进行输出，即会将 * 操作符进行出栈；然后 - 操作符继续与栈顶操作符 + 进行比较，因为 - 操作符的优先级和 + 操作符优先级相等，所以 + 操作符也会出栈进行输出；然后 - 操作符继续与栈顶操作符进行比较，此时发现栈空，所以 - 操作符会直接进行入栈。

然后继续向后遍历中缀表达式，遇到操作数4直接输出，然后中缀表达式遍历完毕，此时将栈中的操作符依次进行出栈和输出。此时就通过中缀表达式得到了后缀表达式。

上面的例子中中缀表达式中没有括号来提高优先级，所以比较转换，下面我们进行一个有括号的中缀表达式转为后缀表达式的例子。
中缀表达式转为后缀表达式有很多种方法，下面我们使用这样的规则来处理中缀表达式中的括号。
(1). () 的优先级最低。
(2). ( 不比较直接入栈。
(3). ) 参与比较，直到遇到 ( 。

下面为将中缀表达式1 + 2 * (3 * (4 - 5)) + 6 / 7 转换为后缀表达式的过程。
遍历中缀表达式时遇到操作数1直接输出，然后遇到操作符 + 号，因为此时栈为空，直接将操作符 + 入栈，然后将操作数2进行输出，然后向后继续遍历中缀表达式遇到操作符 * 号，将该操作符与栈顶的 + 操作符进行优先级比较，因为操作符 * 优先级大于操作符 + 的优先级，所以也将操作符 * 进行入栈。

然后继续向后遍历中缀表达式时，遇到了 ( 操作符，我们直接将该操作符入栈。然后向后继续遍历遇到操作数3直接输出，然后继续向后遍历遇到操作符 * ，将该操作符与栈顶操作符 ( 进行优先级比较，因为我们规定了 ( ) 的优先级最低，所以操作符 * 也进行入栈。

然后我们继续向后遍历中缀表达式，又遇到了操作符 ( ，直接进行入栈；然后继续向后遍历遇到操作数4直接进行输出，然后再向后遍历遇到操作符 - ，将操作符 - 与栈顶操作符 ( 进行优先级比较，因为操作符 - 的优先级大于操作符 ( 的优先级，所以操作符 - 进行入栈。然后我们继续向后遍历遇到操作数5直接进行输出。

然后我们继续向后遍历时，遇到 ) 操作符，此时将操作符 ) 与栈顶操作符 - 进行优先级比较，因为 ( ) 的优先级最低，所以操作符 - 的优先级大于操作符 ) 的优先级，此时将操作符 - 先出栈，然后进行输出；然后再将操作符 ) 与新的栈顶操作符 ( 进行比较，因为规定了操作符 ) 遇到 ( 操作符时就将 ( 操作符进行出栈，然后继续向后遍历，所以此时将栈顶操作符 ( 进行出栈，但不要输出，并且继续向后遍历中缀表达式。

然后继续向后遍历中缀表达式，此时又遇到一个操作符 ) ，所以做与上面一样的步骤，将操作符 ) 与栈顶操作符 * 进行优先级比较，因为操作符 * 优先级大于操作符 ) 优先级，所以操作符 * 先出栈，然后再进行输出；然后操作符 ) 接着与新的栈顶操作符 ( 进行比较，因为操作符 ) 遇到了操作符 ( ，所以直接将操作符 ( 进行出栈，然后继续向后遍历中缀表达式。

继续向后遍历遇到操作符 + ，将该操作符与栈顶操作符 * 进行优先级比较，因为操作符 + 的优先级小于操作符 * 的优先级，所以将操作符 * 先出栈，然后再输出；然后将操作符 + 继续与新的栈顶操作符 + 进行优先级比较，因为两个操作符优先级相等，所以要将栈顶操作符 + 先出栈，然后再输出；然后操作符 + 继续与栈顶元素进行比较，此时发现栈为空，则将操作符 + 进行入栈。

然后继续向后遍历中缀表达式，遇到操作数6直接输出；然后继续向后遍历遇到操作符 / ，此时将操作符 / 与栈顶操作符 + 进行优先级比较，因为操作符 / 优先级大于操作符 + 优先级，所以操作符 / 进行入栈。然后继续向后遍历遇到操作数7直接输出。

此时遍历完中缀表达式，然后将栈中的元素依次出栈并输出。此时就得到了后缀表达式。

4、stack模拟实现

我们可以看到源码中stack的实现很简单，就实现了栈的empty、size、top等一些函数。

我们模拟实现stack也可以向源码中的一样。

namespace dong
{
	//适配器模式/配接器
	template<class T,class Container>
	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();
		}
		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

上面我们就模拟实现了一个stack栈适配器，下面我们创建一个stack栈结构，然后我们传入第二个模板参数为vector< int >，即代表stack的底层容器为vector数组结构。

当我们将第二个模板参数为list< list >时，就代表stack的底层容器为list链式结构。

模板参数也可以给缺省值，因为模板参数表示的是类型，所以给的缺省值也是类型，当模板参数给了缺省值之后，此时如果不传入第二个模板参数，就会使用缺省值，即st底层是一个数组实现的栈。

二、queue队列

1、队列介绍

1.队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2.队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3.底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
4.标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque
队列也是只有这些基本方法，队列的特点是先进先出。

2、queue使用

当我们使用queue时给第二个参数传入vector时，会出现错误，这是因为vector底层为数组实现，而数组进行头删头插时需要挪动数据，开销太大，所以vector容器就没有提供头插头删的方法，这样当queue想要进行头删时会找不到对应的pop_front函数，所以才会报错。

所以我们在使用queue时不传第二个参数的话，queue底层默认就使用deque容器。

int main()
{
	queue<int> qt;
	qt.push(1);
	qt.push(2);
	qt.push(3);
	qt.push(4);

	while (!qt.empty())
	{
		cout << qt.front() << " ";
		qt.pop();
	}
	cout << endl;
	cout << qt.size() << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3、queue队列模拟实现

我们看到源码中的queue默认的底层容器为deque。
如果我们自己模拟时，将queue的底层容器使用vector的话就会出现错误，这是因为vector底层为数组实现，而数组实现的结构进行头插头删时需要将全部数据都要挪动，开销非常大，而且vector容器就没有提供头插头删方法，所以实现queue底层用vector容器时会报错没有pop_front和push_front的错误。所以下面我们底层使用list来模拟实现queue。

template<class T, class Container = list<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_front();
		}
		const T& front()
		{
			return _con.front();
		}
		const 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
23
24
25
26
27
28
29
30
31
32

4、头文件展开

上面我们模拟实现stack和queue的.h文件中，我们可以看到stack.h和queue.h文件中都没有包含头文件，但是在这两个文件中使用了list容器和vector容器。这是因为.h头文件不会被编译器编译，而是会在引用这个头文件的地方展开，即在引用的地方将这个头文件中的代码全部展开过去。可以看到虽然stack.h和queue.h文件中没有包含头文件，但是test.cpp文件中包含了头文件，这样stack.h和queue.h展开后还是可以从上面的头文件中找到list容器和vector容器的头文件。



但是我们需要注意的是如果将using namespace std语句在#include"stack.h"和#include"queue.h"的后面时，此时会报错，这是因为当将stack.h和queue.h头文件中的代码展开后，因为vector和list的使用都在using namespace std的前面，所以当使用vector和list时还没有引入std库里面的变量名，所以才会找不到。

所以我们还是将库引用都统一放在.h文件中比较好。

三、deque双端队列

1、deque双端队列介绍

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

我们学了数据结构后知道顺序表和链表的优缺点，deque容器其实就结合了顺序表的一些优点和链表的一些优点。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组。deque容器的底层实现类似于下面这样。即当向deque中进行头插时就再申请一段小空间，然后在这个空间中插入新元素，然后在中控数组中存储这段空间的地址。需要注意的是头插是在小数组中从后向前插入数据，尾插是在数组中从前向后插入数据。当我们进行大量头插尾插时，如果中控数组满了此时就需要进行扩容，deque扩容时是中控数组扩容，所以扩容代价低。

deque容器进行随机访问时，先减去第一个小数组的值，因为第一个小数组可能不满，然后再计算元素下标。例如当要计算deque中下标为25的元素时，先将(25 - 2) / 10得到该元素在第几个小数组中，然后(25 - 2) % 10得到该元素在小数组中的位置，这样就实现了随机访问元素。

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：
迭代器it进行后移时只需要++it即可，而在deque迭代器的底层，cur向后移动时，需要先进行判断，如果cur不等于last，则cur++就表示向后移动；如果cur等于last时，则需要node++，然后cur等于node，此时才是cur向后移动了一位。

2、deque双端队列优缺点

2.1 deque优点

(1). 相比于vector，deque的扩容代价低。
(2). 相比于vector，deque的头插尾插、头删尾删的效率比较高。
(3). deque也支持随机访问。

2.2 deque缺点

(1). deque中间位置进行插入删除时很麻烦。
对于deque容器中间位置进行插入删除我们可以使用两种思路。
a. 将每个buff小数组设置为不一样大，这样在中间插入时直接插入到小数组中。但是这样实现的话虽然中间位置插入删除的效率高了，但是当随机访问元素时效率变低了，因为buff数组大小不一样，不能再向上面一样通过计算得到元素的位置了。
b. 将每个buff小数组设置为一样大，此时随机访问元素就可以通过计算得到元素的位置，但是这样的话中间位置插入删除就很麻烦了。
(2). 虽然deque包括了vector和list的一些优点，但是通过上面的分析我们可以体会到，deque进行随机访问的效率并没有vector进行随机访问的效率高，并且deque进行中间位置的插入删除效率并没有list的插入删除效率高。

总结:
所以deque适合进行大量头插头删、尾插尾删的场景，而栈和队列都是对头元素和尾元素进行操作，所以deque容器做默认的栈和队列的底层容器最合适了。

2.3 效率测试

可以看到deque容器的排序效率是没有vector容器高的。

int main()
{
	srand(time(0));
	const int N = 100000;
	vector<int> v;
	v.reserve(N);

	list<int> lt1;

	deque<int> dq1;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		v.push_back(e);
		lt1.push_back(e);
		dq1.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	lt1.sort();
	int end2 = clock();

	int begin3 = clock();
	sort(dq1.begin(),dq1.end());
	int end3 = clock();


	cout << "vector sort: " << end1 - begin1 << endl;
	cout << "list sort: " << end2 - begin2 << endl;
	cout << "deque sort: " << end2 - begin2 << endl;

	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
33
34
35
36
37
38
39

下面我们将deque容器的数据先拷贝到vector容器中，然后使用vector排完序后再拷贝到deque中。可以看到deque的数据先拷贝到vector，再排序的效率高一些。所以list容器和deque容器排序效率都不如将数据先拷贝到vector，然后使用vector容器排序后再拷贝数据回来的效率高。

int main()
{
	srand(time(0));
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);

	list<int> lt1;

	deque<int> dq1;
	deque<int> dq2;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		//v.push_back(e);
		//lt1.push_back(e);
		dq1.push_back(e);
		dq2.push_back(e);
	}

	int begin1 = clock();
	for (auto e : dq1)
	{
		v.push_back(e);
	}
	sort(v.begin(), v.end());
	size_t i = 0;
	for (auto e : v)
	{
		dq1[i] = e;
	}
	int end1 = clock();


	int begin2 = clock();
	sort(dq1.begin(),dq1.end());
	int end2 = clock();


	cout << "vector sort: " << end1 - begin1 << endl;
	cout << "deque sort: " << end2 - begin2 << endl;

	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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

四、priority_queue优先级队列

1、priority_queue优先级队列介绍

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

2、priority_queue优先级队列的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。所以priority_queue不是按先进先出的顺序打印，而是按优先级的顺序打印，默认大的优先级高。

int main()
{
	//priority_queue默认情况下，创建的是大堆，其底层按照小于号比较
	priority_queue<int> pq;
	pq.push(3);
	pq.push(5);
	pq.push(1);
	pq.push(4);
	pq.push(2);
	pq.push(6);

	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;

	//如果要创建小堆，将第三个模板参数换成greater比较方式
	priority_queue<int, vector<int>, greater<int>> pq2;
	pq2.push(3);
	pq2.push(5);
	pq2.push(1);
	pq2.push(4);
	pq2.push(2);
	pq2.push(6);
	while (!pq2.empty())
	{
		cout << pq2.top() << " ";
		pq2.pop();
	}
	cout << endl;

	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
33
34
35

3、仿函数

我们从上面的priority_queue使用中知道了，priority_queue模板的第三个模板参数是一个仿函数，该参数决定了priority为大堆还是小堆，那么这个仿函数是什么原理呢？
其实仿函数就是一个类模板，并且在这个类模板中重写了()操作符的重载函数，当我们使用时可以根据这个类模板生成类，然后创建类对象。当lessFunc(1,2)时就调用了这个对象的()操作符重载函数进行了大小比较。c++的仿函数就替代了c语言中的函数指针，并且比函数指针使用起来方便，因为函数指针太复杂了。

4、priority_queue优先级队列的应用

priority_queue优先级队列其实就是一个堆，我们前面学数据结构时知道堆最典型的应用就是求TopK的问题。所以下面我们来使用priority_queue优先级队列解决TopK问题。
题目链接

第一种方法：
直接先排序然后返回第k个值。但是这种方法使用了sort函数，sort函数内部使用快排实现，时间复杂度为O(nlogn)。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        return nums[nums.size() - k];
    }
};
1
2
3
4
5
6
7

第二种方法：
该方法使用了大根堆，即将前k-1个元素都pop，此时堆顶元素就为第k个元素。该方法的时间复杂度为O(nlogn)，建堆的时间代价是 O(n)，删除的总代价是 O(klog⁡n)因为 k < n，故渐进时间复杂为O(n+klog⁡n)=O(nlog⁡n)。并且还有O(n)的空间复杂度。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(),nums.end());

        //先--，再判断。
        while(--k)
        {
            pq.pop();
        }
        return pq.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

第三种方法：
该方法使用了小根堆，如果当N的值远大于K时，我们使用第二种方法会有O(n)的空间复杂度，而该方法我们只需O(K)的空间复杂度。我们建立一个长度为K的小堆，将前K个元素入堆，然后让剩余元素和小堆中的堆顶元素比较，如果大于堆顶元素就进堆，当剩余元素比较完后，此时堆里面就是前K个大的值，并且堆顶元素就是第K个大的值。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq(nums.begin(),nums.begin()+k);
        for(size_t i = k; i < nums.size(); ++i)
        {
            if(nums[i] > pq.top())
            {
                pq.pop();
                pq.push(nums[i]);
            }
        }
        return pq.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5、模拟实现priority_queue优先级队列

priority_queue也是一个容器适配器，所以我们使用模板来实现，并且第二个模板参数定义了priority_queue实现的底层容器，默认priority_queue底层使用vector来实现。

下面我们来使用push函数，因为priority_queue为一个堆，并且默认是一个大堆，所以当新插入数据时，需要将这个新数据进行向上调整，这样才能保证priority_queue一直为大堆。我们需要写一个向上调整的函数来实现向上调整的步骤。然后每当有一个元素插入时就进行向上调整。

然后我们实现priority_queue的pop函数，堆的堆顶删除步骤为：先将第一个元素和最后一个元素交换位置，然后将堆的最后一个元素删除，然后将此时的堆顶元素向下调整，以保证priority_queue一直为大堆。我们写了一个adjust_down函数来实现向下调整。然后在pop函数中调用该函数完成向下调整。


下面我们实现剩下的函数。至此我们就简单模拟实现了一个priority_queue。

我们使用priority_queue时可以使底层容器为deque，因为priority_queue为适配器，所以只要底层容器中提供了priority_queue需要的接口，并且可以随机访问就可以。

我们上面模拟实现的priority_queue只能建立大堆，如果我们想要建立小堆时，还需要修改源码，这样实现priority_queue是肯定不可以的。所以我们也需要和库里面的实现一样，将priority_queue类模板的第三个模板参数使用仿函数。我们可以看到仿函数其实就是一个类模板，然后我们将priority_queue类模板的第三个模板参数传入一个类的类型，这样在priority_queue类中就可以使用第三个参数这个类类型了，然后我们使用时先创建一个类类型的对象，然后比较大小时会自动调用这个对象的()操作符重载函数，即如果第三个模板参数为greater类型，则就表示>号，如果为less类型就表示<号。这样我们就实现了创建priority_queue时根据传入的参数的不同而建立不同类型的堆，less为降序，greater为升序。

6、自定义类型使用priority_queue优先级队列

下面我们先实现一个Date日期类，然后我们将priority_queue中存Date对象，此时我们根据日期类得到了一个小根堆，所以依次打印的日期为升序。需要注意的是如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。


当我们将priority_queue中存入Date * 时，我们发现打印的Date对象并没有按照升序打印，这是因为在比较时比较的是Date * ，即比较的是地址，所以才没有升序打印。

此时如果我们想要将比较时变为Date日期类之间的比较，我们可以重新写一个比较类，将该类中的()操作符重载函数中比较* p1和* p2，这样就是我们想要的比较结果了。


我们在priority_queue类中使用仿函数时，也可以使用匿名对象的写法。

五、反向迭代器

我们在前面模拟实现string、vector、list时都没有实现反向迭代器，现在我们就来学习反向迭代器。

1、土方法实现反向迭代器

我们知道正向迭代器是从第一个元素开始向后遍历容器的元素，而反向迭代器是从最后一个元素开始向前遍历容器的元素。那么我们实现反向迭代器是不是可以再创建一个struct __list_reverse_iterator结构体，然后将该结构体里面的++操作符重载函数改为向前移动，-- 操作符重载函数改为向后移动。

然后我们在list类中使用时将list的最后一个结点作为rbegin()，将头结点作为rend()。

我们看到我们这样实现反向迭代器成功的反向遍历了list中的元素。

2、stl库里面的反向迭代器

下面我们查看源码中的反向迭代器怎么实现的，我们发现源码中的反向迭代器使用正向迭代器来实现。源码中也是重新定义了一个反向迭代器的模板，然后反向迭代器中的++是将正向迭代器 --，反向迭代器的 --是将正向迭代器++。

但是我们发现反向迭代器中的 * 操作符重载函数中并不是返回当前指向的结点的数据，而是返回当前指向的结点的前一个元素的数据。这是因为stl库中实现的反向迭代器和我们不是一样的思路，stl库中的反向迭代器的rbegin()指向头结点，rend()指向正向迭代器的begin()位置，如果 * 操作符重载函数返回的是当前的结点数据，则就会返回头结点的数据，这是错误的，所以stl库中 * 操作符重载函数返回当前结点的上一个结点的数据

3、模拟stl库实现反向迭代器

我们模仿stl库来实现反向迭代器。



那么为什么stl库中使用这样的方法来实现反向迭代器呢，这是因为用我们自己写的第一种方法实现反向迭代器的话，list和vector的反向迭代器实现不一样，所以list和vector需要分别写反向迭代器的代码。而源码中的反向迭代器为适配器，这种方法当实现了一个反向迭代器，则其它容器也可以使用这个适配器来得到反向迭代器。需要注意的是容器的迭代器需要为双向迭代器，因为需要++和–访问。
例如我们将写的代码复制到vector类中，然后实现vector的反向迭代器。

我们看到vector中反向迭代器也成功反向的遍历了vector中的元素。所以stl库中的这个反向迭代器适配器不在乎正向迭代器底层使用什么实现，只要正向迭代器为双向迭代器，可以++和–就可以。反向迭代器底层封装了正向迭代器。