当前位置：首页 > article >正文

移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——8.stackqueuepriority_queue(模拟实现）

article 2024/11/14 9:10:41

1.stack

可通过模板使用其他类来建立stack（如vector，list）

#include<vector>


namespace zone
{
	template<class T,class container>   //两个模板参数
	class stack
	{
	   public:

		   void push(const T& x)
		   {
			   it.push_back(x);  //使用it的pushback
		   }


		   void pop()
		   {
			   it.pop_back();  //使用it的popback
		   }

		   const T& top()
		   {
			   return it.back();    //使用it的back取栈顶
		   }

		   bool empty()
		   {
			   return it.empty();   //使用it的empty
		   }

		   size_t size()
		   {
			   return it.size();      //使用it的size
		   }

	  private:
		  container it;    //it可以是list，vector
	};

}

注意：

能不能使用其他类来建立新的类取决于其他类已有的函数能否满足新的类的需求（如增查删改）

2.queue

可通过模板使用其他类来建立stack（如vector，list）

#include<vector>
#include<list>


namespace space
{
	template<class T, class container>// 适配器！！！！！！！！！相当于用其他类（list，vector）来建立队列
	class queue
	{
	public:

		void push(const T& x)
		{
			it.push_back(x);
		}


		void pop()
		{
			//it.erase(it.begin());      //若container为vector或list
			it.pop_front();              //若container为list，这里只能用list，因为vector 没有pop_front()函数
		}

		const T& top()
		{
			return it.front();
		}

		bool empty()
		{
			return it.empty();
		}

		size_t size()
		{
			return it.size();
		}

	private:
		container it;
	};

}

特别注意：

void pop()
       {
           it.erase(it.begin()); //若container为vector或list
           it.pop_front(); //若container为list，这里只能用list，因为vector 没有pop_front()函数
       }

test.cpp：

#include<iostream>
#include<vector>
#include<list>


using namespace std;

#include"stack.h"
#include"queue.h"

int main()
{
	/*zone::stack<int, vector<int>> arr;
	arr.push(1);
	arr.push(2);
	arr.push(3);
	arr.push(4);
	arr.push(5);
	int num = arr.size();
	for (int i = 0; i < num; i++)
	{
		cout << arr.top() << ' ';
		arr.pop();
	}*/

	
	space::queue<int, list<int>> arr;
	arr.push(1);
	arr.push(2);
	arr.push(3);
	arr.push(4);
	arr.push(5);
	int num = arr.size();
	for (int i = 0; i < num; i++)
	{
		cout << arr.top() << ' ';
		arr.pop();
	}
}

3.priority_queue

3.1 priority_queue的本质

优先级队列本质为堆！！！！！！！！！！！！！！

3.2 模拟实现

1.仿函数

仿函数本质是类，目的是为了替代c语言中的函数指针

#include<vector>
#include<queue>

namespace zone
{
	template<class T>
	class less
	{
	   public:
		   bool operator()(const T& x, const T& y)
		   {
			   return x < y;
		   }
         
	};   //仿函数，判断大小

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

	};   //仿函数，判断大小


	template<class T, class container = vector<T>,class compare=less<int>>//这里传的都是类型，不是变量，只用于构建模板
	class priority_queue
	{
	   public:
		   priority_queue()
		   {}


		   template<class inputiterator>
		   priority_queue(inputiterator first, inputiterator last)
			   : arr(first, last)
		   {
			   for (int i = (arr.size() - 1 - 1 )/ 2; i >= 0; i--) //向下调整原地建堆
			   {
				   adjustdown(i);
			   }

		   }      //迭代器区间建堆



		   void adjustup(int child)
		   {
			   compare com;      //这里才是建立变量
			   int parent = (child-1)/2;
			   while (child > 0)
			   {
				   if (com(arr[child],arr[parent]))
				   {
					   swap(arr[parent], arr[child]);
					   child = parent;
					   parent = (child - 1) / 2;
				   }

				   else
				   {
					   break;
				   }

			   }

		   }

		   void adjustdown(int parent)
		   {
			   int child = 2 * parent + 1;
			   compare com;
			   while (child < arr.size())
			   {
				   if (child < arr.size() - 1 && com(arr[child + 1], arr[child]))
					   child++;
				   if (com(arr[child],arr[parent]))
				   {
					   swap(arr[parent], arr[child]);
					   parent = child;
					   child = 2 * parent + 1;
				   }

				   else
				   {
					   break;
				   }
			   }

		   }


		   void pop()   //删堆顶的数据
		   {
			   swap(arr[0], arr[arr.size() - 1]);
			   arr.pop_back();
			   adjustdown(0);
		   }


		   void push(const T& x)
		   {
			   arr.push_back(x);
			   adjustup(arr.size() - 1);
		   }



		   const T& top()  //取堆顶的数据
		   {
			   return arr[0];
		   }


		   bool empty()
		   {
			   return arr.empty();
		   }


		   size_t size()
		   {
			   return arr.size();
		   }


	  private:
		container arr;

	};


}

test.cpp:

#include<iostream>
//#include<vector>
//#include<queue>

using namespace std;

#include"priority_queue.h"

int main()
{
	//priority_queue<int> arr;
	//priority_queue<int> arr;    //std中的大堆
	priority_queue<int,vector<int>,greater<int>> arr;      //std中使用仿函数建立小堆
	arr.push(1);
	arr.push(5);
	arr.push(4);
	arr.push(7);
	arr.push(2);
	arr.push(8);
	arr.push(6);
	arr.push(3);


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


}