[数据结构与算法] STL中的stack和queue和priority

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

namespace wbx
{
	template<class T, class container = std::vector<T>>
	class stack
	{
	public:
		stack()
			:con()
		{}
		void push(const T& data)
		{
			con.push_back(data);
		}
		void pop()
		{
			con.pop_back();
		}
		size_t size()
		{
			return con.size();
		}
		T& top()
		{
			return con.back();
		}
		bool empty()
		{
			return con.empty();
		}
		stack& swap(stack &s)
		{
			con.swap(s.con);
			return *this;
		}
	private:
		container con;
	};
}

void test_stack()
{
	wbx::stack<int> s;
	s.push(1);//插入元素
	s.push(2);
	s.push(3);
	s.push(4);
	cout << s.size() << endl;//打印元素个数
	cout << s.top() << endl;//打印栈顶元素
	s.top() += 1;//修改栈顶元素
	cout << s.top() << endl;//打印栈顶元素
	s.pop();//出栈
	s.pop();
	s.pop();
	cout << s.size() << endl;
	cout << s.top() << endl;
	wbx::stack<int> s2;
	s2.push(9);//插入元素
	s2.push(9);
	s2.push(9);
	s2.push(9);
	s2.swap(s);
	cout << s.size() << endl;
	cout << s.top() << endl;
}

int main()
{
	test_stack();
	return 0;

运行结果：
4.queue的模拟实现：

因为队列要进行头删和尾插，因此使用vector封装来实现效率太低，故可以借助list来模拟实现queue。

namespace wbx
{
	template<class T, class container = std::list<int>>
	class queue{
	public:
		queue()
		: con()
		{}
		void push(const T& data)
		{
			con.push_back(data);
		}
		void pop()
		{
			con.pop_front();
		}
		bool empty()
		{
			return con.empty();
		}
		size_t size()
		{
			return con.size();
		}
		T& front()
		{
			return con.front();
		}
		T& back()
		{
			return con.back();
		}
		queue& swap(queue &q)
		{
			con.swap(q.con);
			return *this;
		}
	private:
		container con;
	};
}

void test_queue()
{
	wbx::queue<int> q;
	q.push(1);//插入元素
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	cout << q.size() << endl;//打印队列中元素个数
	cout << q.front() << endl;//打印队头元素
	cout << q.back() << endl;//打印队尾元素
	q.front() += 1;//修改队头元素
	q.back() += 1;//修改队尾元素
	cout << q.front() << endl;//打印队头元素
	cout << q.back() << endl;//打印队尾元素
	q.pop();//出队列
	q.pop();
	cout << q.size() << endl;//打印队列中元素个数
	cout << q.front() << endl;//打印队头元素
	cout << q.back() << endl;//打印队尾元素
	wbx::queue<int> q1;
	q1.push(9);//插入元素
	q1.push(9);
	q1.push(9);
	q1.push(9);
	q1.push(9);
	wbx::queue<int> q2;
	q2=q.swap(q1);
}	

int main()
{
	test_queue();
	return 0;
}

运行结果：
5.priority_queue:(优先级队列同样也是容器适配器------>就是包装其他结构)
5.1priority_queue的使用：
用priority_queue创建大堆和小堆（传入less（当然默认传入的就是less）创建大堆，传入greater创建小堆）
这里的greater是一个比较方式的模板，返回x>y的结果。
当我们往堆中传入自定义类型的时候是需要我们在自己的自定义类型中重载">"和"<"运算符的，因为greater和less是要返回'<'和'>'的结果的
上面这里不加const所报的错
当我们传入的参数不是自定义类型，而是诸如指针之类的参数时，我们自定义类型中的重载运算符就不够用了，就需要我们自己定义比较函数

5.2priority_queuede模拟实现：

#include<iostream>
#include<queue>
#include<stdio.h>
#include<algorithm>
#include<functional>
#include<assert.h>
using namespace std;

namespace wbx
{

	template<class T,class container=vector<T>,class Com=less<T>>
	class priority_queue
	{
	public:
		priority_queue()
			:_con()
		{}
		template<class iterator>
		priority_queue(iterator first,iterator last)
		:_con(first,last)
		{
			size_t csize = size();
			for (int i = (csize - 2) / 2; i >= 0; i--)
			{
				AdjustDonw(i);
			}
		}
		~priority_queue()//这里不用写析构函数也会自动生成一份析构函数，调用_con的析构函数对资源进行销毁
		{
			_con.~_con();
		}
		size_t size()const
		{
			return _con.size();
		}
		void push(T data)
		{
			_con.push_back(data);
			AdjustUp(size() - 1);
		}
		void pop()
		{
			if (empty())
			{
				return;
			}
			std::swap(_con[0], _con[size() - 1]);
			_con.pop_back();
			AdjustDonw(0);
		}
		bool empty()const
		{
			return _con.empty();
		}
		const T& top()const
		{
			if (empty())
			{
				assert(false);
			}
			return _con[0];
		}
	private:
		//用于构造堆和删除元素
		//不可以用于插入元素因为当用于插入元素时，这里模拟一个场景，如果此时堆是一个大堆，其堆顶是最大元素
		//当插入元素大于堆顶元素的时候，交换插入元素和堆顶元素那么此时向下调整是无法执行的，因为此时交换
		//之后还满足堆的特性
		void AdjustDonw(int root)
		{
			size_t csize = size();
			int parent = root;
			int child = parent * 2 + 1;//左孩子
			//Com com;//这里Com是一个比较的模板类是一个类型，初始化一个com对象进行比较
			while (child < csize)
			{
				//找出左右孩子中较大的一个,因为默认比较是less返回左<右，如果条件成立则就标记大的
				//一个，创建大堆而当我们传入的是greater时返回的就是右>左，如果条件成立则标记较小
				//的一个创建小堆。
				if (child+1 < csize&&_com(_con[child] , _con[child + 1]))
				{
					child = child + 1;
				}
				//如果不满足堆的特性则交换父子节点
				if (_com(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
				}
				else
				{
					return ;
				}
				parent = child;
				child = parent * 2 + 1;
			}
		}
		//用于插入元素
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;
			//Com com;
			size_t csize = size();
			while (parent >= 0)
			{
				if (child+1<csize&&_com(_con[child], _con[child+1]))
				{
					child = child + 1;
				}
				if (_com(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
				}
				else
				{
					return;
				}
				child = parent;
				parent = (child - 1) / 2;
			}
		}
		container _con;
		Com _com;
	};
	class Date
		{
		public:
			Date(int year,int month,int day)
				:_year(year),
				_month(month),
				_day(day)
			{}
			bool operator<(const Date& d)const
			{
				if ((_year < d._year)||
					(_year == d._year&&_month < d._month) ||
					(_year == d._year&&_month == d._month&&_day < d._day))
				{
					return true;
				}
				return false;
			}
			bool operator>(const Date& d)const
			{
				if ((_year > d._year) ||
					(_year == d._year&&_month > d._month) ||
					(_year == d._year&&_month == d._month&&_day > d._day))
				{
					return true;
				}
				return false;
			}
		private:
			int _year;
			int _month;
			int _day;
		};
}

void test_priority_queue1()
{
	wbx::priority_queue<int> q1;//默认传递的比较方式为(priority_queue<int,vector<int>,less<int>>)
	//less，创建一个大堆
	q1.push(6);
	q1.push(9);
	q1.push(0);
	q1.push(-1);
	q1.push(5);
	cout << q1.top() << endl;
	wbx::priority_queue<int, vector<int>, greater<int>> q2;//创建一个小堆
	q2.push(6);
	q2.push(9);
	q2.push(0);
	q2.push(-1);
	q2.push(5);
	vector<int> array = { 1, 2, 4, 5,6, 8, 7, 9 };
	vector<int> array1 = { 9,8,7,6,5,4,3,2,1 };
	wbx::priority_queue<int, vector<int>, greater<int>> q3(array1.begin(), array1.end());//用数组中元素创建一个堆
	q3.push(0);
	q3.pop();

}
void test_priority_queue2()
{
	wbx::priority_queue<wbx::Date, vector<wbx::Date>, less<wbx::Date>> q1;
	wbx::Date d1(1999, 3, 3);
	wbx::Date d2(1988, 3, 3);
	wbx::Date d3(2000, 3, 3);
	wbx::Date d4(2011, 4, 4);
	q1.push(d1);
	q1.push(d2);
	q1.push(d3);
	q1.push(d4);
	wbx::priority_queue<wbx::Date, vector<wbx::Date>, greater<wbx::Date>> q2;
	q2.push(d1);
	q2.push(d2);
	q2.push(d3);
	q2.push(d4);
}

//bool Isless(const wbx::Date& left,const wbx::Date& right)
//{
//	return left < right;
//}
//
//typedef bool(*com)(wbx::Date& left, wbx::Date& right);

template<class T>
//仿函数
class com
{
public:
	bool operator()(const T& left,const T& right)
	{
		return left < right;
	}
};
void test_priority_queue3()
{
	wbx::priority_queue<wbx::Date, vector<wbx::Date>, com<wbx::Date>> q1;
	wbx::Date d1(1999, 3, 3);
	wbx::Date d2(1988, 3, 3);
	wbx::Date d3(2000, 3, 3);
	wbx::Date d4(2011, 4, 4);
	q1.push(d1);
	q1.push(d2);
	q1.push(d3);
	q1.push(d4);
	wbx::priority_queue<wbx::Date, vector<wbx::Date>, greater<wbx::Date>> q2;
	q2.push(d1);
	q2.push(d2);
	q2.push(d3);
	q2.push(d4);
}

int main()
{
	test_priority_queue1();
	test_priority_queue2();
	test_priority_queue3();
	return 0;
}

6.STL库中创建堆的函数及其使用：
当然函数指针使用起来太麻烦一般我们使用仿函数
1.什么是仿函数
仿函数---->也称为函数对象----->可以像函数调用一样使用的对象，在类中将（）重载（）：称为函数调用运算符
关于栈和队列几个问题：
- 1.为什么栈没有提供迭代器呢？
- 答案：栈的特性：只需要在一段进行数据的插入和删除操作，栈是不需要遍历的，所以是不需要迭代器的。string，list，vector的迭代器主要的目的是为了方便对迭代器中的元素进行遍历配合算法透明化使用容器。
- 2.逆波兰表达式———————后缀表达式
- 答案：1+2：中缀表达式---->运算符在两个操作数中间人更加直观的识别
- 1 2 +：后缀表达式----->逆波兰表达式 RPN
- 计算机在对四则运算进行混合求值的时候，会将中缀表达式转化为后缀表达式来求值
- 3.双端队列：为什么标准库中stack要用deque作为底层结构，而不使用vector？为什么queue要用deque作为底层结构，而不使用list？
- 答案：
- 1.什么是双端队列：
  - 双端队列就是一个可以进行头插头删，尾插尾删操作的队列。
  - 双端队列存储元素：
  - 双端队列的迭代器：
- 2.双端队列的优势：
  - 1、例如vector在扩容时如果vector中放的不是内置类型元素，则需要将vector中的元素全部搬移深拷贝到新的空间（例如我们将vector中放入string类元素。那么当我们拷贝时要调用string类中的‘=’运算符重载，而不可以直接memcpy），这里处理大量的元素是十分耗费时间的，而deque的话当它扩容时将存储元素的小空间再重新开辟一小段即可，如果存储小空间首地址的map存储满了之后可以将map的空间增大，将原来map中的地址逐字节拷贝即可，不会耗费大量时间。
  - 2、因为双端队列在头部和尾部都可以直接插入元素而不需要遍历，因此头插和尾插的效率都是O（1）。
  - 3、因为存储元素时在一小段一小段存储空间中存储，不像是list一个节点一个节点的存储，不容易造成内存碎片。
- 3.双端队列的缺点：
  - 1、代码实现复杂，实现双端队列的实现需要实现存储空间，和存储小段存储空间的map，类似于一个动态的二维数组。，而且双端队列的迭代器需要维护四个迭代器。实现复杂。
  - 2、其次双端队列的遍历十分复杂每次遍历都需要进行判断，或跳转，因此不适用于遍历元素的操作，例如我们要想对其中元素进行排序时，可以先将其中元素放入vector当中去，然后排序之后再将其拷贝回去。
- 4.所以综上所述，用deque而不用vector的原因是：
- 一、stack使用deque不使用vector的原因
- 1.stack不需要对其全部元素进行遍历，只需要对它的尾部进行操作，因而避免了deque的缺点。
- 2.deque扩容时比vector 的效率高，因为deque扩容时不需要搬移元素，只需要memcpy即可。
- 二、queue使用deque不使用list的原因：
- 1.deque中不需要存储一些额外的元素，假如用list存储元素还要存储它的前后节点的指针，而deque中只存储了元素。无需存储其他元素。
- 2.deque是分段存储的，缓存效率高。
- 3.队列不需要遍历，deque的劣势规避。
- 4.为什么堆要删除堆顶的元素，而不是删除末尾元素？
- 答案：因为堆顶元素就是所有元素中最大的或者最小的，所以删除的肯定是堆顶元素对其他元素操作没有意义，这个是堆的特性。