【C++】stack、queue和priority_queue的模拟实现-EW帮帮网

前言

之前已经模拟实现了vector和list，在这篇博文中，我们要对stack和queue进行模拟实现。在开始之前，先讲一个东西：容器适配器。

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

在 C++ 标准库中，容器适配器（Container Adaptors）是一种特殊的容器，它们并非独立的容器类型，而是对现有容器类型进行了封装和适配，以提供特定的接口和行为。容器适配器主要有三种：stack（栈）、queue（队列）和priority_queue（优先队列）。

在这里插入图片描述

其中，stack，queue，priority_queue就是通过封装容器deque(双端队列)和vector(动态数组)适配成特定的容器：容器适配器。

这里的容器适配器是设计模式的一种：适配器模式，在此之前，我们学过另外一种设计模式：迭代器模式。

迭代器模式：通过封装底层实现细节，并且提供统一的访问方式来访问容器。
适配器模式：通过封装已有的东西，再提供特定的接口来转换出想要的东西。

一. stack

1.1 stack的介绍

stack的文档介绍

栈是一种容器适配器，其特点是先进后出，只能从容器的一端进行插入和提取元素。
栈是作为容器适配器被实现的，容器适配器是使用特定容器类的封装对象作为其基础容器的类，提供一组特定的成员函数来访问其元素。元素从特定容器的尾部(栈顶)被压入和弹出。
底层容器可以是任何标准容器类模板或其他专门设计的容器类。这些容器类应支持以下操作：

empty：判断容器是否为空
size：获取容器的元素个数
back：获取容器的尾部元素
push_back：在容器尾部插入一个元素
pop_back：删除容器尾部元素

标准容器vector、list、deque均符合以上要求。如果没有为stack指定一个底层容器类，则默认情况下使用deque。

1.2 stack的使用

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部元素弹出

在这里插入图片描述

1.3 stack的模拟实现

因为stack是对容器的封装，所以默认构造函数、析构函数、赋值运算符重载函数等都不需要自己手动去实现，编译器自动生成的会调用底层容器(如vector)的默认成员函数。

//防止与std库里的stack冲突
namespace MyStack {
	//底层容器可以是vector,list,deque，deque兼容了vector和list所有的接口
	//因为只学习了vector和list，就以vector作为底层容器，即为顺序栈
	//如果以list作为底层容器，即为链栈
	//template<class T, class Container = list<T>>
	template<class T, class Container = vector<T>>
	class stack
	{
	public:
		stack(){}

		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			assert(!empty());
			_con.pop_back();
		}
		const T& top() const
		{
			return _con.back();
		}
		bool empty() const
		{
			return _con.empty();
		}
		size_t size() const
		{
			return _con.size();
		}
		void swap(stack& st)
		{
			_con.swap(st._con);
		}
	private:
		Container _con;
	};
}

测试：

void Test()
{
	MyStack::stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	MyStack::stack<int> st1(st);
	st1.push(5);
	st1.swap(st);
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;
	while (!st1.empty())
	{
		cout << st1.top() << " ";
		st1.pop();
	}
	cout << endl;
}

在这里插入图片描述

二. queue

2.1 queue的介绍

queue的文档介绍

总结：

队列是一种容器适配器，其特点为先进先出，其中从容器一端插入元素，另一端提取元素。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：

empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列

标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

在这里插入图片描述

2.2 queue的使用

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是就返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

在这里插入图片描述

2.3 queue的模拟实现

与stack一样，我们不需要手动去实现默认成员函数，编译器自动生成的就满足需求了。

//防止与std库里的queue冲突
namespace MyQueue {
	//底层容器可以是list和deque，这里使用较为熟悉的list
	template<class T, class Container = list<T>>
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			assert(!empty());
			_con.pop_front();
		}
		const T& front() const
		{
			assert(!empty());
			return _con.front();
		}
		const T& back() const
		{
			assert(!empty());
			return _con.back();
		}
		bool empty() const
		{
			return _con.empty();
		}
		size_t size() const
		{
			return _con.size();
		}
		void swap(queue& q)
		{
			_con.swap(q._con);
		}
	private:
		Container _con;
	};
}

注意：不能使用vector作为底层容器，因为vector不支持高效的头部删除操作。

测试：

void Test()
{
	MyQueue::queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	MyQueue::queue<int> q1(q);
	q1.push(5);
	q1.push(6);
	q.swap(q1);
	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
	while (!q1.empty())
	{
		cout << q1.front() << " ";
		q1.pop();
	}
	cout << endl;
}

在这里插入图片描述

三. deque

vector和list各有缺点：

vector：1.头部中部插入删除效率低；2.要扩容
list：1.不支持随机访问；2.cpu高速缓存命中率低

那有没有一种完美的容器，可以将两者的优点结合，缺点抹除呢？

答案是有的，这个容器就是deque。下面来了解一下deque。

3.1 deque的原理介绍

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

在这里插入图片描述
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

map数组存储所有的缓冲区，当缓冲区不够用了，就创建新的map数组，将旧的map数组存储的缓冲区地址拷贝给新的map数组，最后将旧的map数组释放掉即可。

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

在这里插入图片描述
那deque是如何借助其迭代器维护其假想连续的结构呢？

迭代器存储四个成员：first（指向当前缓冲区的头部），last（指向当前缓冲区的尾部），cur（指向当前元素的指针），node（指向当前缓冲区地址在中控数组存储的位置）。

deque的随机下标访问：
分为两种情况：

访问的元素在当前缓冲区

直接移动cur指针到指定位置即可。

访问的元素不在当前缓冲区。

因为buffer数组的大小是固定的，所以我们可以先用下标/buffer数组的大小，找到要访问的元素在第几个buffer数组里；再根据下标%buffer数组的大小，得到要访问的元素在buffer数组的第几个位置。

deque的随机下标访问还是挺麻烦的，也没有vector快，虽然兼容了vector和list，但是它的优点也不突出。

3.2 deque的缺陷

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

与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

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

deque的使用场景：

1、中部插入删除操作少，头尾插入删除操作多
2、偶尔进行随机下标访问

3.3 为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，queue不仅效率高，而且内存使用率高。

结合了deque的优点，而完美的避开了其缺陷。

感兴趣的可以看一下deque的模拟实现：
c++编程(17)——deque的模拟实现（1）迭代器篇
 c++编程（18）——deque的模拟实现（2）容器篇
 deque的模拟实现源代码

四. priority_queue（优先队列）

4.1 priority_queue的介绍

priority_queue的文档介绍

在这里插入图片描述

总结：

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的"尾部"弹出，其称为优先队列的顶部。
底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

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

标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

4.2 priority_queue的使用

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

函数声明	接口说明
priority_queue()/priority_queue(first,last)	构造一个空的优先级队列
empty()	检测优先级队列是否为空，是返回true，否则返回false
top()	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

存储的是内置类型

void Test()
{
	//默认情况下，创建的是大堆
	vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
	priority_queue<int> q1;
	for (auto& e : v)
	{
		q1.push(e);
	}
	cout << q1.top() << endl;
	
	//如果要创建小堆，将第三个模板参数换成greater比较方式
	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
	cout << q2.top() << endl;
}

如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供 > 或者 < 的重载。

class Date
{
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend ostream& operator<<(ostream& _cout, const Date& d);
private:
	int _year;
	int _month;
	int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day;
	return _cout;
}
void Test()
{
	// 大堆，需要用户在自定义类型中提供<的重载
	priority_queue<Date> q1;
	q1.push(Date(2018, 10, 29));
	q1.push(Date(2018, 10, 28));
	q1.push(Date(2018, 10, 30));
	cout << q1.top() << endl;
	// 如果要创建小堆，需要用户提供>的重载
	priority_queue<Date, vector<Date>, greater<Date>> q2;
	q2.push(Date(2018, 10, 29));
	q2.push(Date(2018, 10, 28));
	q2.push(Date(2018, 10, 30));
	cout << q2.top() << endl;
}

在这里插入图片描述

4.3 priority_queue的模拟实现

因为priority_queue的底层结构就是堆，因此我们只需对其进行封装即可。

如果对堆不熟悉的可以看这篇博客：数据结构：二叉树(堆)的顺序存储

4.3.1 向上调整算法

作用：向上调整当前结点，使其满足堆结构。
主要应用：插入一个结点时(在堆尾)，最后一个结点向上调整满足堆结构。

在这里插入图片描述

void AdJustUp(int child)
{
	int parent = (child - 1) / 2;
	if (parent >= 0 && _con[parent]<_con[child]) {
		std::swap(_con[parent], _con[child]);
		AdJustUp(parent);
	}
}

4.3.2 向下调整算法

作用：向下调整当前结点，使其满足堆结构。
主要应用：1. 向下调整算法建堆；2.删除堆顶结点时，第一个结点(堆顶)与最后一个结点(堆底)交换，将最后一个结点删除后，让第一个结点(堆顶)向下调整满足堆结构。

在这里插入图片描述

void AdjustDown(int parent)
{
	int child = 2 * parent + 1;
	if (child + 1 < _con.size() && _con[child]<_con[child + 1]) {
		child++;
	}
	if (child < _con.size() && _con[parent]<_con[child]) {
		std::swap(_con[child], _con[parent]);
		AdjustDown(child);
	}
}

4.3.3 整体代码

namespace Mypriority_queue {
	template<class T, class Container = vector<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() - 2) / 2; i >= 0; i--)
			{
				AdjustDown(i);
			}
		}
		void AdJustUp(int child)
		{
			int parent = (child - 1) / 2;
			if (parent >= 0 && _con[parent]<_con[child]) {
				std::swap(_con[parent], _con[child]);
				AdJustUp(parent);
			}
		}
		void push(const T& val)
		{
			_con.push_back(val);
			AdJustUp(_con.size() - 1);
		}
		void AdjustDown(int parent)
		{
			int child = 2 * parent + 1;
			if (child + 1 < _con.size() && _con[child]<_con[child + 1]) {
				child++;
			}
			if (child < _con.size() && _con[parent]<_con[child]) {
				std::swap(_con[child], _con[parent]);
				AdjustDown(child);
			}
		}
		void pop()
		{
			assert(!empty());
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}
		const T& top() const
		{
			assert(!empty());
			return _con[0];
		}
		bool empty() const
		{
			return _con.empty();
		}
		bool size() const
		{
			return _con.size();
		}
		void swap(priority_queue& q)
		{
			_con.swap(q._con);
		}
	private:
		Container _con;
	};
}

为什么使用向下调整算法建堆？

因为向下调整算法建堆的时间复杂度为O(N)，向上调整算法建堆的时间复杂度为O(NlogN)，优先用时间复杂度低的。

注意：向下调整算法建堆要从最后一个结点的父节点开始，依次到根节点后结束。

整体已经实现的差不多了，还有最后一个：仿函数，接下来我们来看一下仿函数是如何实现大小堆的。

五. 仿函数

仿函数实际上就是一个类，通过重载operator()，可以让我们像使用函数一样去使用这个类。

namespace GL
{
	template<class T>
	struct less {
		bool operator()(const T& left, const T& right) const
		{
			return left < right;
		}
	};
	template<class T>
	struct greater {
		bool operator()(const T& left, const T& right) const
		{
			return left > right;
		}
	};
}
void Test()
{
	GL::greater<int> g;
	cout << g(2, 3) << endl;
	GL::less<int> l;
	cout << l(2, 3) << endl;
}

在这里插入图片描述
less是判断第一个参数是否小于第二个参数，greater是判断第一个参数是否大于第二个参数。

通过对仿函数的了解，我们知道了priority_queue的第三个模板参数就是用来控制大小堆的（默认为less，就是大堆，如果传的是greater，就是小堆）。

namespace Mypriority_queue {
	template<class T>
	struct less {
		bool operator()(const T& left, const T& right) const
		{
			return left < right;
		}
	};
	template<class T>
	struct greater {
		bool operator()(const T& left, const T& right) const
		{
			return left > right;
		}
	};
	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() - 2) / 2; i >= 0; i--)
			{
				AdjustDown(i);
			}
		}
		void AdJustUp(int child)
		{
			int parent = (child - 1) / 2;
			if (parent >= 0 && Compare()(_con[parent],_con[child])) {
				std::swap(_con[parent], _con[child]);
				AdJustUp(parent);
			}
		}
		void push(const T& val)
		{
			_con.push_back(val);
			AdJustUp(_con.size() - 1);
		}
		void AdjustDown(int parent)
		{
			int child = 2 * parent + 1;
			if (child + 1 < _con.size() && Compare()(_con[child],_con[child + 1])) {
				child++;
			}
			if (child < _con.size() && Compare()(_con[parent],_con[child])) {
				std::swap(_con[child], _con[parent]);
				AdjustDown(child);
			}
		}
		void pop()
		{
			assert(!empty());
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}
		const T& top() const
		{
			assert(!empty());
			return _con[0];
		}
		bool empty() const
		{
			return _con.empty();
		}
		bool size() const
		{
			return _con.size();
		}
		void swap(priority_queue& q)
		{
			_con.swap(q._con);
		}
	private:
		Container _con;
	};
}

测试：

void Test()
{
	vector<int> v = { 2,3,1,4,7,6,5 };
	Mypriority_queue::priority_queue<int> q1(v.begin(), v.end());
	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}
	cout << endl;
	Mypriority_queue::priority_queue<int, vector<int>, Mypriority_queue::greater<int>> q2(v.begin(), v.end());
	while (!q2.empty())
	{
		cout << q2.top() << " ";
		q2.pop();
	}
	cout << endl;
}

在这里插入图片描述

再来看一下以下这段代码：

void Test()
{
	Mypriority_queue::priority_queue<Date*> q;
	q.push(new Date(2025, 1, 1));
	q.push(new Date(2025, 2, 1));
	q.push(new Date(2025, 3, 1));
	while (!q.empty())
	{
		cout << *q.top() << " ";
		q.pop();
	}
	cout << endl;
}

在这里插入图片描述

为什么两次运行的结果是不一样的，还是错误的呢？

因为存储的类型为指针类型Date*，而仿函数默认比较的就是Date*，因为地址是随机性的，而堆顶是地址值最大的Date对象，所以每次运行的结果都不一样。

解决办法就是自己再写一个专门用于比较Date*的仿函数：

struct Less
{
	bool operator()(const Date* d1, const Date* d2)
	{
		return *d1 < *d2;
	}
};
struct Greater
{
	bool operator()(const Date* d1, const Date* d2)
	{
		return *d1 > *d2;
	}
};
void Test()
{
	Mypriority_queue::priority_queue<Date*, vector<Date*>, Less> q;
	q.push(new Date(2025, 1, 1));
	q.push(new Date(2025, 2, 1));
	q.push(new Date(2025, 3, 1));
	while (!q.empty())
	{
		cout << *q.top() << " ";
		q.pop();
	}
	cout << endl;

	Mypriority_queue::priority_queue<Date*, vector<Date*>, Greater> q1;
	q1.push(new Date(2025, 1, 1));
	q1.push(new Date(2025, 2, 1));
	q1.push(new Date(2025, 3, 1));
	while (!q1.empty())
	{
		cout << *q1.top() << " ";
		q1.pop();
	}
	cout << endl;
}

在这里插入图片描述

最后

stack、queue、priority_queue的模拟实现到这里就结束了，对以上内容有异议或者需要补充的，欢迎大家来讨论！

本文整体代码：stack,queue,priority_queue的模拟实现

【C++】stack、queue和priority_queue的模拟实现

文章目录

前言

一. stack

1.1 stack的介绍

1.2 stack的使用

1.3 stack的模拟实现

二. queue

2.1 queue的介绍

2.2 queue的使用

2.3 queue的模拟实现

三. deque

3.1 deque的原理介绍

3.2 deque的缺陷

3.3 为什么选择deque作为stack和queue的底层默认容器

四. priority_queue（优先队列）

4.1 priority_queue的介绍

4.2 priority_queue的使用

4.3 priority_queue的模拟实现

4.3.1 向上调整算法

4.3.2 向下调整算法

4.3.3 整体代码

五. 仿函数

最后

网站公告

今日签到

热门文章

最新发布