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

#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
	};

}

#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;
	};

}

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

#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;

	};


}

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


}