【C++】stack和queue以及priority_queue的使用以及模拟实现-EW帮帮网

前言

本文主要介绍C++【STL】中的栈(stack)和队列(queue)以及优先级队列(priority_queue)，在栈和队列模拟实现的中会了解到 deque(双端队列)，还有优先级队列的模拟实现过程中了解到仿函数的实现与使用。内容丰富，干货满满，期待你的查阅。

一、栈和队列的使用

我在数据结构的文章中已详细介绍了栈和队列，当时也使用C语言进行了模拟实现，而STL中的栈和队列与之前讲的大差不差，因此使用方面简单讲述下即可

stack:

函数声明	接口说明
push	栈顶插入一个数据
top	返回栈顶元素
pop	删除一个栈顶元素（没有返回值）
empty	判空
size	返回栈中元素个数
swap	交换两个栈对象

简单演示下栈的循环遍历：后进先出

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);

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

	return 0;
}

运行结果：

queue:

函数声明	接口说明
push	队尾插入一个元素
pop	队头删除一个元素
front	返回队头元素
back	返回队尾元素
empty	判空
size	返回队列中元素个数
swap	交换两个队列

循环遍历演示：先进先出

#include <iostream>
#include <queue>
using namespace std;

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

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

	return 0;
}

运行结果：

二、栈和队列的练习题

1.最小栈

链接：155. 最小栈 - 力扣（LeetCode）

思路：

题目的核心要求是 getMin() 函数的时间复杂度为O(1)。

既然要获取栈中的最小元素，那么我们在入栈时就需要进行记录判断最小的元素，因此我们需要设置两个栈，一个栈用来存储所有入栈元素的栈 st，另一个栈专门存入栈的最小元素 minst。

我们在 push 函数中，将元素插入st后，首先判断 minst 栈是否为空，为空就直接将元素插入 minst，不为空，则判断入栈元素是否小于 minst 的栈顶元素，小于的话就需要插入到 minst ，反之则不用管。

你可能想问万一原来最小的元素出栈了怎么办，这时候就是 pop 函数中需要注意的了，我们需要先判断 st 的栈顶元素是否等于 minst 的栈顶元素，相等则说明是同一个元素，则 minst 和 st 都出栈，这是第二小的元素依旧是 minst 的栈顶元素。

所以 getMin 的时间复杂度要想为O(1)，就需要一个最小栈的栈顶记录最小值。

（补充：初始化函数不用写，对应自定义类型，编译器会自动调用对应的构造函数）

题解：

class MinStack {
public:
    //不用写，自动调用构造
    MinStack() {
    }
    
    void push(int val) {
        st.push(val);
        if(minst.empty() || val <= minst.top())
        {
            minst.push(val);
        }
    }
    
    void pop() {
        if(st.top()==minst.top())
        {
            minst.pop();
        }
        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minst.top();
    }
private:
    stack<int> st;
    stack<int> minst;
};

扩展问题：如果有大量重复的元素怎么办？

在上题的基础上，假如元素有大量重复的存在，效率会降低，该怎么解决了呢？

解决方法为：新建一个结构体，结构体由一个最小栈和计数变量组成，当遇到相同最小元素时，只需要++计数即可，删除相同的元素时，只要计数大于1，就直接--计数变量即可。

2.栈的压入、弹出序列

链接：栈的压入、弹出序列_牛客题霸_牛客网

思路：

题目的意思是，给你两个序列，一个是入栈的顺序，一个是出栈的顺序，让你使用程序判断出栈顺序是否合法。

这题我们不能去寻找规律，核心方案就是模拟整个过程，我们需要两个下标去遍历两个序列，如：

pushi 循环往后走，将遍历的数据插入到栈中，每插入一个元素后，只要栈还不为空，就循环判断栈顶元素是否与出栈序列的元素相等，相等则出栈然后popi++，不相等则pushi 继续遍历并入栈，直到 pushi 走到入栈序列的尾部就结束循环。

最后只需判读栈是否为空即可，因为如果出栈序列合法，则栈一定为空，也就是刚好全部出栈。

题解：

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        int pushi = 0, popi = 0;
        stack<int> st;

        while(pushi < pushV.size())
        {
            st.push(pushV[pushi++]);
            while(!st.empty() && st.top() == popV[popi])
            {
                st.pop();
                ++popi;
            }
        }

        return st.empty();
    }
};

3.逆波兰表达式求值

链接：150. 逆波兰表达式求值 - 力扣（LeetCode）

思路：

这题虽然是中等题，但如果我们了解何为逆波兰表达式的话，这题会非常简单。

逆波兰表达式其实就是后缀表达式，我们平时数学上写的表达式是中缀表达式，如下图：

简单点说，后缀表达式就是将操作数按原顺序排列，而运算符则按照优先顺序依次放在需要先计算的操作数后面，关于中缀转后缀的过程此题不用管，已经计算好了的，但如果你感兴趣下面扩展中会提到。

知道了后缀表达式计算规则，这题就很好写了，我们利用栈的特性，先遍历序列，遇到操作数直接入栈，遇到操作符则先将钱两个操作数出栈并保存，然后用 switch 语句判断操作符为哪一种，再计算后将结果入栈，如此循环直至序列被遍历完。最后返回栈顶结果即可。

题解：

class Solution {
public:
    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])
                {
                    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();
    }
};

扩展：中缀转后缀

因为过程稍微有点复杂，我就简单说下转换的思路

我们的目标是将一个 string 的中缀表达式转为后缀表达式并存入 vector 中

首先参数方面需要一个下标 i ，并且使用引用传值，因为在中缀表达式中存在括号这种需要优先计算的情况，那么就需要使用递归，递归返回时需要从递归遍历结束的位置继续遍历，因此需要一个下标 i 去记录。

然后，我们使用 while 循环遍历字符串，遇到操作数则直接尾插到 vector 中，遇到操作符则需要暂存，因为需要判断优先级，如果栈为空则直接插入到栈中，如果下一个操作符优先级大于栈顶操作符，则继续入栈，因为不确定后面还有没有更大的操作符，这里判断优先级需要我们定义一个函数 operatorPrecedence，函数中需要定义一个结构体，_op为操作符，_PD为优先级，优先级按1,2进行区分。

前面说到如果栈为空或者操作符的优先级大于栈顶元素则入栈，反之，说明栈顶操作符的优先级需要先计算，因此先将栈顶操作符尾插到 vector ，此时 i 还不能继续++，因为当前操作符还需要继续与栈顶元素比较。

然后就是遇到括号的情况了，当我们遍历到左括号时，则先++i，然后递归调用自己，递归相当于重新建立一个函数栈帧，此时递归中的栈是独立的，当递归遍历到右括号时需要返回，返回前需要将栈中剩余的操作符直接出栈。

最后当 i 遍历结束后，同样需要将当前栈中的剩余元素全部弹出。这样中缀表达式就成功转化出来了

    //判断操作符的优先级
	int operatorPrecedence(char ch)
	{
		struct opPD
		{
			char _op;
			int _PD;
		};

		static opPD arr[] = { {'+', 1},{'-', 1},{'*', 2},{'/', 2} };
		for (auto& e : arr)
		{
			if (e._op == ch)
			{
				return e._PD;
			}
		}

		assert(false);//代码不应该执行到这里，不然直接报错
		return 0;
	}

	//中缀转后缀
	void toRPN(const string& s, size_t& i, vector<string>& v)
	{
		stack<char> st;
		while (i < s.size())
		{
			//如果是操作数，直接入v
			if (isdigit(s[i]))
			{
				string num;
				while (i < s.size() && isdigit(s[i]))
				{
					num += s[i++];
				}
				v.push_back(num);
			}
			else if (s[i] == '(')//如果遇到括号，需要进行递归
			{
				++i;
				toRPN(s, i, v);
			}
			else if (s[i] == ')')//遇到收括号，则需要将栈里符号弹出到v
			{
				while (!st.empty())
				{
					v.push_back(string(1, st.top()));
					st.pop();
				}
				++i;
				return;
			}
			else//如果是操作符
			{
				//如果栈为空或者操作符的优先级大于栈顶元素，入栈
				if (st.empty() || operatorPrecedence(s[i]) >            
                operatorPrecedence(st.top()))
				{
					st.push(s[i++]);
				}
				else//反之,栈顶操作符入v，i不能++，需要继续判断
				{
					char op = st.top();
					st.pop();
					v.push_back(string(1, op));
				}
			}
		}

		//循环结束，弹出栈里符号到v
		while (!st.empty())
		{
			v.push_back(string(1, st.top()));
			st.pop();
		}
	}

4.用队列实现栈

链接：225. 用队列实现栈 - 力扣（LeetCode）

关于队列的题这里接触的不多，这道题我在C语言数据结构中有详细解答，也就是双队列实现栈，采用来回导的方式。

不多废话直接上代码，就当做队列方法使用的练习了

题解：

// 队列实现栈
class MyStack {
public:
    MyStack() {}

    void push(int x) {
        if (!q1.empty()) {
            q1.push(x);
        } else {
            q2.push(x);
        }
    }

    int pop() {
        queue<int>* empQ = &q1;
        queue<int>* noneQ = &q2;
        if (!q1.empty()) {
            empQ = &q2;
            noneQ = &q1;
        }

        while (noneQ->size() > 1) {
            empQ->push(noneQ->front());
            noneQ->pop();
        }

        int ret = noneQ->front();
        noneQ->pop();

        return ret;
    }

    int top() {
        if (!q1.empty()) {
            return q1.back();
        } else {
            return q2.back();
        }
    }

    bool empty() { return q1.empty() && q2.empty(); }

private:
    queue<int> q1;
    queue<int> q2;
};

三、栈和队列的模拟实现

1.容器适配器

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为 容器适配器。

什么是适配器：

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

不理解？没关系，看了模拟实现的代码你就知道为什么叫容器适配器了

2.stack的模拟实现

#pragma once
#include <deque>

namespace txp
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		//插入
		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
		size_t size() const
		{
			return _con.size();
		}

		//判空
		bool empty() const
		{
			return _con.empty();
		}

	private:
		Container _con;
	};
}

3.queue的模拟实现

#pragma once
#include <deque>

namespace txp
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		//尾插
		void push(const T& val)
		{
			_con.push_back(val);
		}

		//头删
		void pop()
		{
			_con.pop_front();
		}

		//返回队头元素
		T& front()
		{
			return _con.front();
		}
		const T& front() const
		{
			return _con.front();
		}

		//返回队尾元素
		T& back()
		{
			return _con.back();
		}
		const T& back() const
		{
			return _con.back();
		}

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

		//判空
		bool empty() const
		{
			return _con.empty();
		}

	private:
		Container _con;
	};
}

4.说明

根据上面的模拟实现，我们是使用了其他容器作为底层进行封装，将其封装为 “后进先出”的栈或者 “先进先出”的队列，我们不用像C语言那样自己造轮子，所以说适配器这种设计模式实质上是一种复用。

栈和队列的模拟实现非常简单，因为它的底层是使用了 deque 这种容器的，我们先不说 deque，因为是缺省的模版参数，因此我们也可以自己使用 vector 或 list 进行声明。

例如：

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <list>
using namespace std;

int main()
{
	//stack可以使用vector和list进行适配
	stack<int, vector<int>> st1;
	st1.push(1);
	st1.pop();
	stack<int, list<int>> st2;
	st2.push(1);
	st2.pop();

	//deque可以使用list进行适配，但不支持vector，因为vector不支持pop_front
	queue<int, list<int>> q1;
	q1.push(1);
	q1.pop();
	queue<int, vector<int>> q2;
	q2.push(1);
	//q2.pop();error C2039: "pop_front": 不是 "std::vector<int,std::allocator<int>>" 的成员

	return 0;
}

（queue 不支持vector，详细且查看queue的pop模拟实现）

想必你已经猜到为什么缺省参数选择 deque 而不选择 vector 或者 list 的原因了吧？

其实就是因为不够通用，而 deque 就满足这方面需求。

5.deque

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

（deque 属于了解型容器，因此不会进行模拟实现）

deque 的接口介绍：

对于以上的接口名称，想必我们已经很熟悉了，STL的容器接口命名都是统一的，所以以上接口的功能与我们前面所学的 string 、vector 、list 是一样的。

首先我们有没有发现 deque 的接口非常丰富，可以说它融合了 vector、list 的所有接口，是一个功能非常全面的容器。

那么，既然它的功能这么全面，那为什么不能替代 list 和 vector ?

我们先带着这个问题来看一下 deque 的底层实现

deque 的底层结构：

deque 的底层是由一个一个 buffer 数组组成的
当一个数组满后，就另外再开辟一个数组
那么这些数组是怎么管理的呢？它们是通过一个中控数组进行管理的，这个中控数组就是一个指针数组。
注意观察：我们第一个数组的指针是存储在指针数组的中间位置的，这样做是为了方便头插，可以直接往指针数组前面进行插入数组。
当然，当中控数组满了时，中控数组也会进行扩容，但因为是指针数组，不会涉及深拷贝，只需要拷贝地址就行，所以中控数组扩容代价非常低。
在这种结构中，当我们使用 [ ] 进行下标访问时，假设每一个数组大小相同并且为10，我们需要访问 pos 下标，这时我们可以 pos /10 计算得到具体哪一个数组，再通过 pos%10 计算得到具体数组中具体的下标位置，是不是比较方便？

以上是 deque 底层数据存储的结构，那么这种结构有什么设计缺陷呢？

首先就是 insert 和 erase 接口的实现，这两个涉及中间数组的插入和删除，那么对于 deque 这种结构来说，这中间势必存在性能的牺牲，这里有两种实现方式：

1. 挪动中间以及受影响的后面所有数组的数据，这样挪动的代价非常大，效率也很低。但是可以保证每个数组的大小一致，对于 [ ] 访问的效率没什么损失。

2. 只挪动需要插入或者删除的那一个数组，插入就将这个数组单独扩容，这样虽然对插入和删除的效率影响不大，但是 [ ] 访问的效率就会直线下降，因为此时每个数组的大小都不确定，因此 [ ] 访问时需要计算所有数组大小，对于 [ ] 的代价非常大。

虽然 C++ 官方没有明确规定使用那种方式实现，但是绝大部分编译器厂商采用的是第一种方式，也就是牺牲 insert 和 erase 的性能，换取 [ ] 访问的效率，毕竟 [ ] 使用的场景更多。

deque 的迭代器设计：

我们先体会下 deque 的迭代器遍历：

#include <iostream>
#include <deque>
using namespace std;

int main()
{
	deque<int> dq{ 1,2,3,4,5,6,7,8,9 };
	auto it1 = dq.begin();
	while (it1 != dq.end())
	{
		cout << *it1 << " ";
		++it1;
	}
	cout << endl;

	return 0;
}

运行结果：

使用起来都一样，但是 deque 的迭代器设计可以算是比较复杂的

首先 deque 的迭代器由四个指针组成，三个一级指针，一个二级指针。
指针 cur 指向的是当前访问的元素位置，指针 first 指向的是数组开头位置，指针 last 指向的是下一个数组的地址。
接下来，我们全面观赏 deque 的结构：
从下往上看，首先两个迭代器 start 和 finish，这两个迭代器分别指向中控数组（map）中的头数组和尾数组。deque 的底层就有这两个迭代器进行构成：

class deque
{
    iterater start;
    iterater finish;
}

上图中，start 迭代器的 cur 指针指向的是第一个数组的第一个元素，first 同样，last 指向的是第一个数组中最后一个元素，node 指向中控数组中的下一个数组。对于 finish 迭代器与 start 同理。
然后，关于迭代器的遍历，操作符 *，它的运算符重载是解引用迭代器中的 cur 指针，也就是数组中当前位置的元素。操作符 ++，它的运算符重载也是让 cur 向前走，如果 cur 指向的位置与 last 相同，那么就解引用 node 二级指针，将当前迭代器的 first 、last、cur 全部重置为下一个数组的位置，最后还需要将 node 更新为中控数组中的下一个数组。

以上就是 deque 的迭代器设计，这是多么的巧妙啊，虽然复杂，但是完美的管理起了所有的数组。

接下来，我们再说一下deque的缺陷：

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是比vector高的。但是对于 [ ] 的访问效率，deque 是比不过 vector 的。

与list比较，deque 底层是连续空间，空间利用率比较高，不需要存储额外字段。但是 list 中间插入和删除数据效率是很高的，这一点 deque 也是比不过 list 的。

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

简单点说 vector 和 list 特点很明显，相当于最强的矛和盾，但是 deque 相比就夹在中间，这就是前面所说为什么 deque 替代不了 vector 和 list。

我们可以通过两段代码，比较下 deque 使用 sort 的排序效率：

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

void test_op1()
{
	srand((unsigned int)time(0));
	const int N = 1000000;
	vector<int> v1;
	deque<int> dq1;

	for (size_t i = 0; i < N; i++)
	{
		int e = rand();
		v1.push_back(e);
		dq1.push_back(e);
	}

	size_t begin1 = clock();
	sort(v1.begin(), v1.end());
	size_t end1 = clock();

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

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

void test_op2()
{
	srand((unsigned int)time(0));
	const int N = 1000000;
	deque<int> dq1;
	deque<int> dq2;

	for (size_t i = 0; i < N; i++)
	{
		int e = rand();
		dq1.push_back(e);
		dq2.push_back(e);
	}

	size_t begin1 = clock();
	sort(dq1.begin(), dq1.end());
	size_t end1 = clock();

	size_t begin2 = clock();
	vector<int> v;
	v.assign(dq2.begin(), dq2.end());
	sort(v.begin(), v.end());
	dq2.assign(v.begin(), v.end());
	size_t end2 = clock();

	cout << "deque sort: " << end1 - begin1 << endl;
	cout << "deque copy vector sort,vector back: " << end2 - begin2 << endl;
}

int main()
{
	test_op1();
	test_op2();

	return 0;
}

运行结果：

test_op1 是测试 vector 和 deque 分别排序一百万个相同的数据需要的时间

test_op2 是测试 deque 将一百万个数据拷贝给 vector 排序，vector 排好后再拷回 deque的时间效率。

通过结果，很明显可以看到，哪怕经过拷贝这一层消耗，deque 排序的效率完全比不过 vector，所以排序方面，我们不建议直接使用 deque 进行排序。

最后在补充下，为什么选择deque作为stack和queue的底层默认容器：

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的优点，而完美的避开了其缺陷。

四、优先级队列介绍

参数 T 为数据类型，参数 Container 为适配容器（默认vector），参数 Compare 为仿函数。

详细介绍：

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。

优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

empty() 检测容器是否为空

size() 返回容器中有效元素个数

front() 返回容器中第一个元素的引用

push_back() 在容器尾部插入元素

pop_back() 删除容器尾部元素

标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue 类实例化指定容器类，则使用vector。

需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

省流版：

简单说，优先级队列就是顺序结构的二叉树 ---- 堆。

（如果不清楚何为堆，请查看主页数据结构之二叉树篇章）

默认情况下就是一个大堆，也就是堆顶为最大值。

注意：优先级队列是包含在 queue 头文件下的。

（因为优先级队列和栈以及队列一样都是容器适配器，所以没有迭代器）

priority_queue 的接口介绍：

函数声明	接口说明
priority_queue()	构造，支持默认构造和迭代器区间构造
push()	尾插一个元素
pop()	删除堆顶元素
top()	返回堆顶元素
size()	返回元素个数
empty()	判空
swap()	交换两个优先级队列的数据

简单演示优先级队列默认情况下的出堆顺序：

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	priority_queue<int> pq1;
	pq1.push(5);
	pq1.push(3);
	pq1.push(4);
	pq1.push(1);
	pq1.push(2);

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

	return 0;
}

运行结果：

因为默认是大堆，所以出队顺序就是从大到小。

优先级队列的简单练习题：

链接：215. 数组中的第K个最大元素 - 力扣（LeetCode）

这题使用堆就是一个简单题，我们先建堆，然后根据堆顶为最大值，先将前k-1个最大的元素出堆，最后返回堆顶元素即可。

题解：

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.基础框架

#pragma once
#include <vector>

namespace txp
{
	template<class T, class Container = vector<T>>
	class priority_queue
	{
	public:
		
	private:
		Container _con;
	};
}

我们先不管仿函数，底层默认使用 vector 进行适配。

因为是自定义类型，所以不用写默认构造。

我们需要自己包含 vector 头文件，因为默认容器就是使用 vector。

2.基本接口实现

（1）push

//向上调整算法
void AdjustUp(size_t child)
{
	size_t parent = (child - 1) / 2;

	while (child > 0)
	{
		//小堆：父节点 > 孩子节点，交换
		//大堆：父节点 < 孩子节点，交换
		if (_con[parent] < _con[child])
		{
			std::swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

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

我在C语言数据结构中已讲解堆的实现，因此不再重复。

我们在堆中插入数据时就需要借助 “向上调整算法” 进行调整建堆，向上调整算法就是将新插入的数据与堆中数据进行比较，以保持堆顶为最大值（默认是大堆）。

（2）pop

//向下调整算法
void AdjustDown(size_t parent)
{
	//左孩子
	size_t child = 2 * parent + 1;

	while (child < _con.size())
	{
		//小堆：找左右孩子中小的值
		//大堆：找左右孩子中大的值
		if (child + 1 < _con.size() && _con[child] < _con[child + 1])
		{
			child++;
		}

		//小堆：父节点 > 孩子节点, 交换
		//大堆：父节点 < 孩子节点，交换
		if (_con[parent] < _con[child])
		{
			std::swap(_con[child], _con[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

//头删
void pop()
{
	std::swap(_con[0], _con[_con.size() - 1]);
	_con.pop_back();
	AdjustDown(0);
}

pop 对应着头删，头删不是直接删除，而是先将头部数据与尾部数据进行交换，再尾删以达到删除数据效果，这样删除效率高，但是这样会破坏堆的性质，因此需要 “向下调整算法进行调整”。

向下调整算法就是调整堆顶数据，将堆顶数据与下面数据比较，将最大值交换上去。

（温馨提醒：如果不懂该算法可以移步主页数据结构之二叉树的文章）

（3）top、empty、size

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

	//判空
	bool empty()
	{
		return _con.empty();
	}

	//返回size
	size_t size()
	{
		return _con.size();
	}

这三个接口可以直接使用适配容器的接口进行实现。

3.仿函数

以上，我们已经实现了一个大堆，但是大堆只能返回最大值，当我们需要小堆的时候，我们就需要自己到代码中去调节比较操作符，这样会很麻烦，所以有没有一种方法可以方便调整比较操作符呢？

这时，就是仿函数存在的意义了

仿函数简介：

仿函数其实就是一个类，只不过类中重载了 () 这个运算符，我们之前重载过 += 这样的操作符，使用时只需要对象名+=就可以进行使用了，而（）也一样，当我们重载了小括号后，就可以使用对象名() 进行调用重载函数了。

这时，我们想解决上面问题，就可以在重载的()函数中写一个比较函数，将堆中需要进行比较的地方换成这个仿函数，我们事先写好两个仿函数，一个比较大于，一个比较小于，在官方中，大于的仿函数叫 greater，小于的仿函数叫 less。

实现仿函数类：

//仿函数
template<class T>
struct less
{
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

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

这时，我们再将堆的模版参数加上一个 class Compare = less<T>，在官方中，传小于的仿函数是实现大堆，传大于的仿函数实现的是小堆，因此我们实现的堆是与官方看齐的，虽然这一点设计的感觉不太好。

最后将堆中 “向上调整算法” 和 “向下调整算法”’ 中需要比较孩子节点和父节点等地方进行替换。这样比较大小就由我们传的仿函数进行控制了。

调整后的优先级队列：

#pragma once
#include <vector>

namespace txp
{
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		//向上调整算法
		void AdjustUp(size_t child)
		{
			Compare com;//仿函数对象
			size_t parent = (child - 1) / 2;

			while (child > 0)
			{
				//小堆：父节点 > 孩子节点，交换
				//大堆：父节点 < 孩子节点，交换
				//if (_con[parent] < _con[child])
				if(com(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

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

		//向下调整算法
		void AdjustDown(size_t parent)
		{
			Compare com;//仿函数对象
			//左孩子
			size_t child = 2 * parent + 1;

			while (child < _con.size())
			{
				//小堆：找左右孩子中小的值
				//大堆：找左右孩子中大的值
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					child++;
				}

				//小堆：父节点 > 孩子节点, 交换
				//大堆：父节点 < 孩子节点，交换
				//if (_con[parent] < _con[child])
				if(com(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}

		//头删
		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}

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

		//判空
		bool empty()
		{
			return _con.empty();
		}

		//返回size
		size_t size()
		{
			return _con.size();
		}

	private:
		Container _con;
	};

	//仿函数
	template<class T>
	struct less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

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

4.补充构造函数

优先级队列我们已经大差不差的实现了，但是还有一个重要的功能没有实现，就是使用迭代器区间进行构造。

注意这可不是简单的拷贝插入，而是需要进行建堆操作，如果你了解堆这个数据结构，你就一定知道堆排序，堆排序之前就需要对数组元素进行建堆，以保证数据是大堆或者是小堆的结构。

在我们之前堆排序的学习中，我们知道建堆和堆排序都是使用向下调整算法进行实现的，因为向下调整建堆的效率整体是高于向上调整的。

实现迭代器区间构造：

//强制生成默认构造
priority_queue() = default;

//迭代器构造
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
	:_con(first, last)
{
	//建堆
	for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(i);
	}
}

详细建堆解释在主页二叉树文章中有详细介绍。

简单点说就是从最后一个父节点开始，逐渐往上进行建堆，最后使其整体成为一个大堆或者小堆。

需要注意的是，当我们显示的写了构造后，编译器是不会自动生成默认构造了，如果我们不想自己手动去写默认构造，可以加上上面第一行代码，强制编译器生成一个默认构造。

5.完整代码

#pragma once
#include <vector>

namespace txp
{
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		//强制生成默认构造
		priority_queue() = default;

		//迭代器构造
		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)
		{
			//建堆
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				AdjustDown(i);
			}
		}

		//向上调整算法
		void AdjustUp(size_t child)
		{
			Compare com;
			size_t parent = (child - 1) / 2;

			while (child > 0)
			{
				//小堆：父节点 > 孩子节点，交换
				//大堆：父节点 < 孩子节点，交换
				//if (_con[parent] < _con[child])
				if(com(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

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

		//向下调整算法
		void AdjustDown(size_t parent)
		{
			Compare com;
			//左孩子
			size_t child = 2 * parent + 1;

			while (child < _con.size())
			{
				//小堆：找左右孩子中小的值
				//大堆：找左右孩子中大的值
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					child++;
				}

				//小堆：父节点 > 孩子节点, 交换
				//大堆：父节点 < 孩子节点，交换
				//if (_con[parent] < _con[child])
				if(com(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}

		//头删
		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}

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

		//判空
		bool empty()
		{
			return _con.empty();
		}

		//返回size
		size_t size()
		{
			return _con.size();
		}

	private:
		Container _con;
	};

	//仿函数
	template<class T>
	struct less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

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

6.仿函数使用演示

我们同时使用自己实现的优先级队列和官方的优先级队列进行演示：

#include <iostream>
#include <queue>
#include "PriorityQueue.h"
using namespace std;

int main()
{
	vector<int> v = { 9,6,3,2,5,8,1,4,7 };

	//官方
    //默认建大堆
	priority_queue<int> pq1(v.begin(), v.end());
	while (!pq1.empty())
	{
		cout << pq1.top() << " ";
		pq1.pop();
	}
	cout << endl;

    //建小堆
	priority_queue<int, vector<int>, greater<int>> pq2(v.begin(), v.end());
	while (!pq2.empty())
	{
		cout << pq2.top() << " ";
		pq2.pop();
	}
	cout << endl;

	//我们自己实现的
    //默认建大堆
	txp::priority_queue<int> my_pq1(v.begin(), v.end());
	while (!my_pq1.empty())
	{
		cout << my_pq1.top() << " ";
		my_pq1.pop();
	}
	cout << endl;

    //建小堆
	txp::priority_queue<int, vector<int>, txp::greater<int>> my_pq2(v.begin(), v.end());
	while (!my_pq2.empty())
	{
		cout << my_pq2.top() << " ";
		my_pq2.pop();
	}
	cout << endl;

	return 0;
}

运行结果：

最后需要注意的一点是，当我们需要给第三个模版参数传值时，前两个必须也上传。

总结

以上就是本文的全部内容了，博主熬夜码字不易，感谢支持！

【C++】stack和queue以及priority_queue的使用以及模拟实现

前言

一、栈和队列的使用

二、栈和队列的练习题

1.最小栈

扩展问题：如果有大量重复的元素怎么办？

2.栈的压入、弹出序列

3.逆波兰表达式求值

扩展：中缀转后缀

4.用队列实现栈

三、栈和队列的模拟实现

1.容器适配器

2.stack的模拟实现

3.queue的模拟实现

4.说明

5.deque

四、优先级队列介绍

优先级队列的简单练习题：

五、优先级队列的模拟实现

1.基础框架

2.基本接口实现

（1）push

（2）pop

（3）top、empty、size

3.仿函数

4.补充构造函数

5.完整代码

6.仿函数使用演示

总结

网站公告

今日签到

热门文章

最新发布

empty()	检测容器是否为空
size()	返回容器中有效元素个数
front()	返回容器中第一个元素的引用
push_back()	在容器尾部插入元素
pop_back()	删除容器尾部元素