【C++】stack、queue模拟实现+仿函数

stack、queue模拟实现+仿函数

• stack
• • 定义
  • stack模拟实现
• queue
• • 定义
  • queue模拟实现
• priority_queue
• • 定义
  • priority_queue模拟实现
• deque
• • 定义
  • 底层分析
• 容器适配器
• • 定义
  • 种类
• 仿函数
• 控制类里面数据的比较逻辑
• • 回调函数
  • 仿函数
  • 两者区别

铁汁们，今天给大家分享一篇stack、queue模拟实现+仿函数，来吧，开造⛳️

stack

定义

• stack是容器适配器，专门用于进行”先进后出”操作的环境中，只能在容器的一端进行数据的插入和删除操作，元素在特定容器的尾部(即栈顶)被压入和弹出。
• 容器适配器是将特定的类进行封装，将其作为该容器的底层容器，通过调用底层容器提供的一系列成员函数来实现该容器。
• stack的底层容器既可以是任何标准容器类模板(list、vector、deque),也可以是其他特定的容器类,它必须支持以下操作：push_back()->入栈、pop_back()->出栈、back()->获取栈顶元素、empty()->判断栈是否为空、size()->获取栈中元素总个数。
• stack底层容器可以是list、vector、deque,若未实例化指定特定的底层容器，则默认为deque。
• 栈空间从高地址往低地址方向增长，堆从低地址往高地址方向增长。

template<class T, class Container = deque<T>> 
class stack {

private:
	Container _con;
};

stack模拟实现

template<class T, class Container = deque<T>> 
class stack {
public:
    stack()  //构造空栈
	{  }

	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();
	}

	bool empty()const  //判断栈是否为空
	{
		return _con.empty();
	}
		 
	size_t size()const //获取栈中元素的总个数
	{
		return _con.size();
	}

private:
	Container _con;  //底层容器创建的对象
};

queue

定义

• queue是容器适配器，专门用于进行”先进先出”操作的环境中，从容器的一端插入数据并从容器的另一端取出数据。
• 容器适配器是将特定的类进行封装，将其作为该容器的底层容器，通过调用底层容器提供的一系列成员函数来实现该容器。
• queue的底层容器既可以是某些标准容器类模板(list、deque),也可以是其他特定的容器类,它必须支持以下操作：push_back()->入队、pop_front()->出队、back()->获取队尾元素、front()->获取队头元素、empty()->判断队列是否为空、size()->获取队列中元素总个数。
• queue底层容器可以是list、deque,但不可以是vector(没有支持pop_front())，若未实例化指定特定的底层容器，则默认为deque。
• 队列从队尾入队列，从队头从队列。

template<class T, class Container = deque<T>>
class queue {

private:
	Container _con; //底层容器创建的对象
};

queue模拟实现

template<class T, class Container = deque<T>>
class queue {
public:
    queue() //构造空队列
	{ }

	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();
	}

	bool empty()const  //判断队列是否为空
	{
		return _con.empty();
	}

	size_t size()const  //获取队列中元素的总个数
	{
    	return _con.size();
	}

private:
	Container _con; //底层容器创建的对象
};

priority_queue

定义

• priority_queue为优先队列，是容器适配器，默认情况下元素呈降序排列，且它的第一个元素总是它所有元素中最大的。
• 容器适配器是将特定的类进行封装，将其作为该容器的底层容器，通过调用底层容器提供的一系列成员函数来实现该容器。元素从优先队列的顶部弹出。
• priority_queue的底层容器既可以是某些标准容器类模板(vector、deque),也可以是其他特定的容器类,它必须支持以下操作：push_back()->插入元素、pop_back()->删除元素、front()->获取优先队列顶部的元素、empty()->判断优先队列是否为空、size()->获取优先队列中元素总个数。
• priority_queue底层容器可以是vector、deque,但不可以是list(不支持随机访问[])，若未实例化指定特定的底层容器，则默认为vector。
• priority_queue底层结构为堆，所有需要用到堆的地方，都可以考虑使用priority_queue。默认情况下为大堆，即小于less-》降序(大堆），greater-》升序(小堆)。
• priority_queue底层容器要支持随机访问，以保持堆的结构。在堆中可以随时插入数据，且只检索到最大元素(大堆)或者最小元素(小堆）。

template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue {

private:
	Container _con;
	Compare _com;
};

priority_queue模拟实现

💡void push(const T& val) ；

• 方法: 在堆的底部插入元素，在采用向上调整法

💡void pop( )

• 方法: 堆顶元素和堆中最后一个元素交换，在删除最后一个元素，在采用向下调整法

//仿函数:功能像函数，但它就是个类模板，重载了operator(),通过将其设置为类模板参数，在其他类中通过该参数创造出对象，直接()调用
template<class T> //设计为类模板，泛型编程，是为了支持所有数据类型的比较
class less {  //小于
public:
	bool operator()(int x, int y)
	{
		return x < y;
	}
};

template<class T>
class greater { //大于
public:
	bool operator()(int x, int y)
	{
		return x > y;
	}
};

template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue {//默认为大堆，且底层容器为vector
public:
	priority_queue()  //构造空优先队列
	{ }

	void Adjust_up(int child)  //向上调整法
	{
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			if (_com(_con[parent], _con[child])) 
			{
				std::swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
	}

	void Adjust_down(int parent) //向下调整法
	{ //找到左、右孩纸中最大一个 -》假设法，假设左孩纸大，在与右孩纸进行比较
		int child = parent * 2 + 1;  
		if (child + 1 < _con.size() && _com(_con[child], _con[child + 1]))
			++child;

		while (child < _con.size()) 
		{
			if (_com(_con[parent] ,_con[child])) // 默认情况下为大堆，大的优先级高
			{
				std::swap(_con[child], _con[parent]);
				parent = child;
    			child = parent + 1;
			}
			else
				break;  //前提:该堆已经是个大堆(小堆)了
		}
	}

	void pop() //堆顶元素和堆中最后一个元素交换，在删除最后一个元素，在采用向下调整法
	{
		std::swap(_con[0], _con[size() - 1]);
		_con.pop_back();

		Adjust_down(0);
	}

	void push(const T& val) //在堆的底部插入元素，在采用向上调整法
	{
		_con.push_back(val); 

		Adjust_up(size() - 1);
	}

	const T& top()const //获取优先队列中顶部元素，即：堆顶元素
	{
		return _con.front();
	}

	bool empty()const  //判断优先队列是否为空
	{
		return _con.empty();
	}

	int size()const  //获取优先队列中总元素个数
	{
		return _con.size();
	}

private:
	Container _con;  //底层容器创建的对象
	Compare _com;  //仿函数类创建的对象
};

deque

定义

• deque是双端队列，是一种双开口的“连续”空间的数据结构，可以在头尾进行插入和删除操作，时间复杂度为O(1),与vector相比，头插效率高，不需要挪动数据，与list相比，空间利用率高，缓存命中率高。
• deque实际上并不是连续的空间，而是由一段段连续的小空间拼接而成，为了维护其”整体的连续”以及随机访问。deque底层类似于动态二维数组。
  

底层分析

• 与list相比 ，缓存命中率高，空间利用率高，因为deque底层空间连续。deque支持随机访问。
• 与vector相比 ，对于在头、尾部插入和删除上，效率高于vector，因为不需要挪动数据。对于在扩容消耗上，效率高于vector，因为不需要频繁挪动数据，只要”中控”满了扩容就可以了，且只需要拷贝指针(4个字节)。
• stack和deque为容器适配器，不需要遍历数据，所以它们没有迭代器，只需要在固定一端或者两端进行插入和删除数据。在插入元素时，deque效率高于vector(扩容消耗小），相比于list，deque不仅头、尾插效率高，且内存利用率高。综上所述，选择deque作为stack和deque默认的底层容器更有优势。

容器适配器

定义

• 适配器是一种设计模式，该模式是将一种接口转换成另一种接口。
• 容器适配器是一个对特定的类进行封装的类模板，它在底层容器的基础上提供了一些其他的功能。它是适配其他容器来提供不同的功能，通过调用底层容器提供的一系列成员函数来实现我们需要的功能。
• stack和queue都可以存储元素，但未将他们划分到容器序列，而是将他们称为容器适配器，是因为stack和queue是对其他容器进行了封装，默认情况下，stack和queue的底层容器为deque。
  
• 💡Tips : 容器适配器中不存在迭代器。

种类

三种容器适配器：stack、queue、priority_queue。

仿函数

• 💡仿函数：又称为函数对象，是一个重载了operator()运算符的类。
• 仿函数，不是函数，在语法上与普通函数调用的语法调用一样，在功能上仿函数通过创建的对象去调用operator()运算符，从而达到函数一样的功能。

//仿函数
template<class T>
class less { //小于
public:
    bool operator()(int x, int y)
    {
    	return x < y;
    }
};

 template<class T>
class greater {  //大于
public:
    bool operator()(int x, int y)
    {
    	return x > y;
    }
};

void test()
{
	less<int> LessFu;
	cout << LessFu(3, 4) << endl;

	greater<int> GreaterFu;
	cout << GreaterFu(3, 4) << endl;
}

int main()
{
    test();

	return 0;
}

控制类里面数据的比较逻辑

回调函数

• 回调函数就是一个通过函数指针调用的函数。如果你把函数的地址作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，我们就说被调用的函数称为回调函数。回调函数不是由该函数的实现方直接调用，而是在特定的事件或条件发生时由另外的一方调用的，用于对该事件或条件进行响应。

namespace yun {
	bool Less(int x, int y)
	{
		return x < y;
}

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

	//在A这个类中调用
	class A1 {
	public:
		A1(bool(*pf)(int, int))
			:_pf(pf)
		{ }

		void fun(int x, int y)
		{
			cout << _pf(x, y) << endl;  //回调函数
		}

		bool(*_pf)(int, int);
	};

	//通过回调函数去调用:缺点-》函数指针类型抒写太复杂、需要通构构造函数参数传递(成员变量_pf为虚拟指针，无值）
	void test1()
	{
		A1 aa1(Less); 
		aa1.fun(3, 4);
		A1 aa2(Greater);
		aa2.fun(3, 4);
	}
}

int main()
{
	yun::test1();  //回调函数
    
	return 0;
}

仿函数

namespace yun {
    //仿函数
	template<class T>
	class less { //小于
	public:
		bool operator()(int x, int y)
		{
			return x < y;
		}
	};

	template<class T>
	class greater {  //大于
	public:
		bool operator()(int x, int y)
		{
			return x > y;
		}
	};

	template<class T, class Compare = less<T>> 
	class A2{  
	public:
		void fun(int x, int y)
		{
			cout << _com(x, y) << endl;  //调用仿函数，实际上就是通过类对象去调用operator()运算符
		}

	private:
		Compare _com; //创建仿函数对象
	};


	void test2() 
	{
		A2<int, less<int>> aa2;
		aa2.fun(5, 6);
		A2<int, greater<int>> aa3;
		aa3.fun(5, 6);
	}
}

int main()
{
	yun::test2();  //仿函数
    
	return 0;
}

两者区别

• 回调函数缺点：函数指针类型相对比较复杂、只能通过函数参数传递（在类中，通过构造函数参数传递，且需要定义函数指针类型的成员变量，进行值的接收，从而实现回调。在普通函数中，通过函数参数直接传递)。
• 仿函数优点：类型相对比较简单、只需要在类中创建对象，通过该对象去调用operator()运算符，就可以实现回调。

铁铁们，就到此结束啦，若博主有不好的地方，请指正，欢迎铁铁们留言，请动动你们的手给作者点个👍鼓励吧，你们的鼓励就是我的动力✨