投稿
  1. 首页
  2. C

stack&&queue 和优先级队列的介绍和实现

code•2022-4-3•C•阅读63

stack&&queue 和优先级队列的介绍和实现,第1张

目录

stack的模拟实现

 Queue模拟实现

deque双端队列（了解）

原理介绍

优先级队列priority_queue

优先级队列的模拟实现

仿函数

stack的模拟实现

栈的实现可以放在链表中，也可以放在数组中等等，对于C++的栈，我们没必要像C语言一样，用什么容器就把什么容器实现出来，这样成本太高，我们可以用一个容器模板，在私有成员定义一个容器类的成员变量，相当于实例化了这个容器，再去实现一系列的函数。


	template
	class stack
	{
	public:
		bool empty() const
		{
			return _con.empty();
		}
		size_t size() const
		{
			return _con.size();
		}
		const T& top() const
		{
			return _con.back();
		}
		
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
	private:
		Container _con;
	};

调用一下

	void test_stack1()
	{
		stack> s;
		//stack> s;//这里报错因为要包头文件。


		s.push(1);
		s.push(2);
		s.push(3);
		s.push(4);

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

但是在std中调用栈的时候，并没有给到两个参数模板。


这是因为参数模板也有缺省值，std给到Container中的缺省值是deque,这里模板参数的用法参考函数参数，二者几乎是一样的。


函数参数控制的是对象，模板参数控制的是类型。


这里传的deque是类型。


上面的例子存放string结果也是对的，但是这样是不对的，因为string里面放的是char存1个字节,而int是4字节，将int放入string中会发生截断，这里只是恰巧对了。


如果存其他对象如string对象有肯能不对。


 Queue模拟实现

队列的实现最好不要用vector数组，队列的性质是先进先出，如果在数组中实现，要尾插入数据，而出数据要头删，这样时间复杂度很大，最好用链表。


以下就是队列要实现的各个函数功能

#pragma once
#include 
#include 

namespace wjy
{
	template>//默认用deque,还可以用list
	class queue
	{
	public:
		bool empty() const
		{
			return _con.empty();
		}
		size_t size() const
		{
			return _con.size();
		}
		const T& front() const
		{
			return _con.front();
		}
		const T& back() const
		{
			return _con.back();
		}
		//插入和删除
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_front();
		}
	private:
		Container _con;
	};

	void test_queue()
	{
		//queue q;
		//queue> q;
		queue> q;
		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);
		while (!q.empty())
		{
			cout << q.front() << " ";
			q.pop();
		}
		cout << endl;
	}

}

以上就是适配器模式，适配了一系列容器

deque双端队列（了解） 原理介绍

deque：是一种双开口“连续”空间的数据结构，它集成了vector和queue的优点。


双开口的含义是：可以在头尾两端进行插入和删除 *** 作，且时间复杂度为O(1),与vector比较，头插效率高，不需要搬移元素。


与list相比空间利用率较高。


vector和list的优缺点

vector的优点：下标随机访问，尾插效率高

vector缺点：扩容（效率、浪费空间），不适合头插头删

list优点：按需申请释放空间。


任意位置O(1)插入删除

list缺点：不支持下标随机访问

对于这些接口，发现它既有vector的属性，又有list的属性。


所以在栈和队列中用刚刚好。


deque做默认是配容器的优势：

相较于vector而言，扩容代价不大，不需要拷贝数据，浪费空间也不多。


vector如果扩容，每次都会扩n倍，如果一个数组本来1024个大小，要存放1030个数据，还要扩容到2048，有1000多个空间浪费，，但是deque如果空间不够就扩容，他每次开的空间都很小，也不用拷贝数据，代价非常小 。


他们只需要用指针放在指针数组，如果指针数组不够再扩n倍，也不会频繁扩容。


当vector删除数据后不会释放空间，而deque删除数据后如果一个buffer删没了，那么直接将空buffer释放掉，空间浪费小。


相较于list而言，cpu高速cache命中，其次不会频繁申请小块空间。


申请和释放空间次数少代价低。


如果list删除80个数据要释放80次空间，但是deque一个可以存8个数据的话，只需要释放10此就可以，申请和释放空间的次数少，代价低

所以deque只是在栈和队列中发挥的作用比vecto和list要大，deque适合头尾的插入删除，但是如果平时在用其他数据结构中，因为deque随机插入非常麻烦，如果要对deque中的数据排序，还不如将它拷贝到数组中排序再放回来，这是《SLT源码剖析》这本书就提到的。


所以如果随机访问还是用vector，随机插入删除还是用list，这两个一直是数据结构中的王道。


优先级队列priority_queue

文档介绍

翻译

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


  2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)
  3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。


    元素从特定容器的“尾部”d出，其称为优先队列的顶部

  4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。


    容器应该可以通过随机访问迭代器访问，并支持以下 *** 作：

  •           

对于优先级队列，它的底层是以堆为基础的，是包含在队列这个头文件中。


那么优先级队列是从大到小排序的，还是从小到大排序的呢？通过测试我们发现，默认情况下，优先级队列是从大到小排列的，因为他给的默认缺省仿函数是Less(从大到小排列)，如果要从小到大排列需要加一个参数，反函数greater使队列排序与默认相反。


仿函数会在下面提到。


而在优先级队列中要默认给到vector这个容器，它并不像栈和队列一样用deque容器，deque容器对于栈和队列的好处就是可以头插头删，而且增容代价不大，cache命中率高，所以会用到deque，而它的缺点就是不能在中间插入删除，访问下标也非常麻烦，这对于优先级队列是非常不友好的，优先级队列因为要排序，所以需要访问下表，这时vector的作用就比较大。


优先级队列的默认容器也采用vector。


#include 
#include 

//默认大的优先级高
void test_priority_queue()
{
	//默认是打的优先级高--默认给的仿函数是less
	//priority_queue pq;

	//控制小的优先级高 -- 给一个greater的仿函数
	priority_queue, greater> pq;
	pq.push(1);
	pq.push(9);
	pq.push(3);
	pq.push(4);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}
优先级队列的模拟实现

因为优先级队列还是队列，所以它的push是尾插，pop是头删，这也符合了先进先出的性质。


namespace wjy
{
	template>
    //因为要优先级队列要排序，所以最好用vector，方便访问下标，deque排序就是噩梦
	class priority_queue
	{
	private:
		//如果孩子大于父亲，向上调整，孩子与父亲交换，更新下标，直到孩子小于等于父亲
		void adjust_up(size_t child)
		{
			size_t 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)
		{
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _con[child + 1] > _con[child])//谁更大调谁
				{
					++child;
				}
				if (_con[parent] < _con[child])//比父亲大就交换，上面的永远是大的
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}		
		}
	public:
		priority_queue()
		{}

		//类模板里面的成员函数也可以是一个函数模板
		template
		priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)//用迭代器区间初始化
		{
			//建堆--父节点的左右子树都是大堆了，就可以调大堆
			//从第一个非叶子节点开始调整
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
			{
				adjust_down(i);
			}
		}

		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}
		void pop()
		{
			//断言，堆里不能为空
			//交换堆顶和最后一个数据，尾删然后向下调整
			assert(!_con.empty());//如果不断言也可以，operator[]已经断言数组不能为空
			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;

	};
	void test_priority_queue()
	{
		priority_queue> pq;//默认less
		pq.push(3);
		pq.push(4);
		pq.push(7);
		pq.push(1);
		pq.push(9);

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

以上是基本定义，下面来看仿函数，我们要能控制大堆小堆，比较的方式。


从用法上来看，只要大adjust_up和adjust_down中的child下标的数小于parent下标的数即可。


但是我们不能让用的人改内部的函数，所以我们可以用仿函数。


仿函数

来看下面一段代码，我们在一个类中重载（），（）也是一种 *** 作符。


struct Less
{
	//重载一个operator()
	bool operator()(int x, int y)
	{
		return x < y;
	}
};

struct Greater
{
	bool operator()(int x, int y)
	{
		return x>y;
	}
};

int main()
{
	Less less;
	cout << less(1, 2) << endl;
	Greater gt;
	cout << gt(1, 2) << endl;
	cout << gt.operator()(1, 2) << endl;//等价于上面

	return 0;
}

这里只针对了int类型，如果想要管理更宽泛的类型，可以套一个类模板

ps:模板传参没有实例化，指针不明确指向的对象，引用传参，最后加一个const，为了防止传过来一个const对象。


template
struct Less
{
	//重载一个operator()
	bool operator()(const T& x,const T& y)const
	{
		return x < y;
	}
};

int main()
{
	Less less1;
	cout << less1(1, 2) << endl;
	cout << Less()(1, 2) << endl;//匿名对象
	cout << Less()(1.1, 2.2) << endl;

	return 0;
}

 了解了仿函数，那么如何实现变换类模板就能改变大小堆的实现呢？

写一个仿函数类，在类模板中加一个以Less为缺省值的模板参数，实例化这个参数模板，将需要改变的地方用仿函数实现

但是有的人提出疑问，为什么Less不用大于，这样不是更方便优先级队列吗？既然Less是从大到小排列，x>y不是更方便吗？其实不然，在出了优先级队列的其他函数中，Less都扮演着x


所以如果改成大于，这样更麻烦。


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

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

	template, class Compare = Less>
    //因为要优先级队列要排序，所以最好用vector，方便访问下标，deque排序就是噩梦
	class priority_queue
	{
	private:
		//如果孩子大于父亲，向上调整，孩子与父亲交换，更新下标，直到孩子小于等于父亲
		void adjust_up(size_t child)
		{
			Compare com;//模板实例化
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[child] > _con[parent])等价于
				if (com(_con[parent],_con[child])
				{
					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() && com(_con[child], _con[child + 1]))//谁更大调谁
				{
					++child;
				}
				if (com(_con[parent],_con[child]))//比父亲大就交换，上面的永远是大的
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}		
		}

当我们用自定义类型来写一个优先级

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 << endl;
	return _cout;
}

void test_priority_queue2()
{
	priority_queue> pq;//默认less，从大到小排列
	//priority_queue,greater> pq;
	pq.push(Date(2022, 3, 26));
	pq.push(Date(2021, 10, 26));
	pq.push(Date(2023, 3, 26));

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

 当我们传一个Date的指针Date*类型，直接打印Date只会打出地址，所以我们要打印解引用的值，但是打印解引用的值就不会从大到小（从小到大）排序了，因为传的是Date* 类型，Date指针指向这块空间的地址，地址是16进制的数，他会给地址排序，给地址排好序后，解引用里面的值，可能顺序不一样。


 所以我们可以再次用到仿函数，如果对应的数据类型不支持比较，或者比较的方式不是你想要的，那么可以自己实现仿函数，按照自己想要的方式去比较，控制比较逻辑

 在官方写法中，最后的仿函数默认就给了less，我们也可以自定义写一些其他的来实现。


欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/langs/564144.html

赞 (0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
codecode管理员组
00
上一篇 2022-04-03
下一篇2022-04-03

发表评论

登录后才能评论

评论列表（0条）

    保存