C++栈、队列、优先级队列模拟+仿函数

 

目录

一、栈的模拟和deque容器

1.deque

1.1deque结构

1.2deque优缺点

2.stack模拟

二、队列的模拟

三、priority_queue优先级队列

1.优先级队列模拟

2.添加仿函数

---

一、栈的模拟和deque容器

在之前，我们学过了C语言版本的栈，可以看这篇文章 栈和队列。

但是C语言没有模板，我们只能固定一个类型去写，在C++中引入了模板的概念，我们只需要写一份，在调用中给到类型，编译器会自动去帮我们推导是栈里面元素的类型，会非常方便。

1.deque

我们可以看到，库函数里面的栈调用的是一个deque容器。

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

1.1deque结构

首先deque有一个中控数组，这个数据是指针数组，存放的内容是指针，每个指针都指向的一块空间的起始地址。

他的迭代器有  cur（当前数据当前位置）  fisrt（数据起始位置）last（数据结尾位置） node（指向数据的指针）。

头插就去找到最前面的那个有效指针进行头插，尾插就找最后面那个有效指针尾插，遍历就通过迭代器每一个空间块从头遍历到位，就换下一个空间块。

 

1.2deque优缺点

deque实际上是一个缝合怪，他结合了vector和list的内容，将他们糅合在了一起。

优点

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

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

 但是他也有缺点

deque容器不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list。

那么为何他能在栈和队列中使用，并成为默认容器呢？

因为栈和队列需要尾插，尾删，队列需要尾插，头删deque容器完全可以适配这些需求，因为不需要遍历，并且deque扩容时不需要挪动数据，这也是的deque的效率变高。

2.stack模拟

stack的模拟非常简单，调用模板Container容器的函数就可以了，也不需要迭代器（不用遍历），也不需要构造函数析构函数什么的，因为Container容器是自定义类型，会自动调用的相关构造析构拷贝函数。

#pragma once
#include
namespace kky
{
	template<class T, class Container = deque>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

二、队列的模拟

队列模拟跟stack差不都，多了一个back接口，出数据的时候要调用pop_front()

#pragma once
#include
namespace kky
{
	template<class T, class Container = deque>
	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();
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

三、priority_queue优先级队列

优先级队列出数据的时候，会先出优先级高的数据。

如何来判断优先级的高低呢？

这跟你传的数据类型有关，先举个例子

我们插入了   1,10,8,5,6   但出数据的时候缺省按照数据的大小顺序来出的，在这里使用数据的大小来看段他们优先级的高低。

优先级队列出数据时会帮我们做好排序，他的本质就是堆，通过堆的向上向下调整来处理优先级问题。具体堆排序的过程可以看选择排序中的堆排序。

1.优先级队列模拟

优先级队列的模拟实现就是要建堆，每一次插入数据都要进行向上调整，保证是大堆或者小堆。

出数据的时候将第一个数据和最后一个数据互换，再进行尾删，因为第一个数据是我们想要出的数据，将他和最后一个数据交换再尾删，就可以提取出这个数据了，同时现在只有第一个元素不符合小堆或者大堆的情况，其他元素都符合，因此进行一次从索引为0位置的向下调整即可。

namespace kky
{
	template<class T,class Container = vector>
	class priority_queue
	{
	public:
		void adjust_up(size_t child)
		{
			while(child>0)
			{
				size_t parent = (child - 1) / 2;
				if (_con[child] > _con[parent])
				{
					swap(_con[child], _con[parent]);
					child = parent;
				}
				else
				{
					break;
				}
			}
		}
 
		void adjust_down(size_t parent)
		{
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				{
					child++;
				}
				if (_con[child] > _con[parent])
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
 
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size()-1);
		}
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		T& top()
		{
			return _con[0];
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

刚刚的代码构建了一个大堆，但是我们如果想要构建小堆，难不成又要重写一份代码吗？  那必定不是可能的。 

2.添加仿函数

在C语言中，我们可以通过函数指针来处理顺序的问题，但是函数指针类型很繁琐，并且不容易理解，C++推出了仿函数来帮助我们处理这类问题。

写一个类，仅仅重载了operator()，返回类型为bool，在后面进行判断的时候，我们就可以调用这个类对象的()，类似于函数一样，就可以处理了，

template<class T>
class Less
{
public:
	bool operator()(const T& x1, const T& x2)
	{
		return x1 < x2;
	}
};

第一个方式太丑陋了，一般使用第二种方式去调用。

那之前，我们代码中的判断语句，都可以通过调用仿函数更改了 

给模板参数再添加一个类

template<class T, class Container = vector,class Compare = Less>

现在就可以开始更改了 

只需要注意顺序即可，需要这样判断的都可以更改，参考如下代码

namespace kky
{
	template<class T, class Container = vector,class Compare = Less>
	class priority_queue
	{
	public:
		void adjust_up(size_t child)
		{
			Compare com;
			while (child > 0)
			{
				size_t parent = (child - 1) / 2;
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
				}
				else
				{
					break;
				}
			}
		}
 
		void adjust_down(size_t parent)
		{
			Compare com;
			int 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;
				}
			}
		}
 
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		T& top()
		{
			return _con[0];
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

 这是我们写的Less仿函数，如果你想让优先级队列建小堆，就可以写再写一个仿函数

template<class T>
class Greater
{
public:
	bool operator()(const T& x1, const T& x2)
	{
		return x1 > x2;
	}
};

需要的时候调用一下即可