08 stack、queue和priority_queue的使用和模拟实现

2023-12-27 23:39:21

stack和queue在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque容器。

文章目录

一、容器适配器

容器适配器 是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。 之所以称作适配器类，是因为它可以通过适配容器现有的接口来提供不同的功能。

说白了就是通过一种容器来实现另一种容器的功能，比如用链表实现栈，栈的push操作就可以用链表的push_back来实现，而栈的pop操作用链表的pop_back实现，至于链表的其他接口（栈用不到的接口，比如头插头删）则不对外进行暴露，因此虽然表面上看上去是一个栈，但是在底层实现上确是一个链表。
STL中的stack和queue在底层上默认用的是双端队列deque：
08 stack、queue和priority_queue的使用和模拟实现

Container是一个缺省参数，我们在使用的时候可以自定义这个容器适配器，比如不想用deque而想用vector或list，直接在实例化对象的时候传入vector或list即可。

二、stack

stack是STL中的栈，其功能和数据结构中的栈一样。
常用接口：

成员函数 功能
empty() 判断栈是否为空
size() 获取栈中有效元素个数
top() 获取栈顶元素
push(x) 将元素x入栈
pop() 栈顶元素出栈
swap() 交换两个栈中的数据 
#include <iostream>
#include <stack>
#include <list>
using namespace std;

int main()
{
	stack<int, list<int>> st;//用list作为容器适配器
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	cout << st.size() << endl; //4
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl; //4 3 2 1

	stack<int, list<int>> st1;
	st1.swap(st);//交换st到st1

	cout << st.size() << endl; //0
	while (!st.empty())
	{
		cout << st.top() << " ";//空
		st.pop();
	}
	cout << endl; 

	return 0;
}

模拟实现stack

#include<deque>
namespace hjl //防止命名冲突
{
	template<class T, class Container = std::deque<T>>
	class stack
	{
	public:
		//元素入栈
		void push(const T& x)
		{
			_con.push_back(x);
		}
		//元素出栈
		void pop()
		{ 
			_con.pop_back();
		}
		//获取栈顶元素
		T& top()
		{
			return _con.back();
		}
		const T& top() const
		{
			return _con.back();
		}
		//获取栈中有效元素个数
		size_t size() const
		{
			return _con.size();
		}
		//判断栈是否为空
		bool empty() const
		{
			return _con.empty();
		}
		//交换两个栈中的数据
		void swap(stack<T, Container>& st)
		{
			_con.swap(st._con);
		}
	private:
		Container _con;
	};
}

三、queue

queue是STL中的队列，功能和数据结构中的队列一样。

成员函数 功能
empty() 判断队列是否为空
size() 获取队列中有效元素个数
front() 获取队头元素
back() 获取队尾元素
push(x) 将x入到队尾
pop() 队头出队列
swap() 交换两个队列中的数据 
#include <iostream>
#include <list>
#include <queue>
using namespace std;

int main()
{
	queue<int, list<int>> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	cout << q.size() << endl; //4
	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();//队头出队列
	}
	cout << endl; //1 2 3 4
	return 0;
}

模拟实现queue

#include<deque>
namespace hjl //防止命名冲突
{
	template<class T, class Container = std::deque<T>>
	class queue
	{
	public:
		//队尾入队列
		void push(const T& x)
		{
			_con.push_back(x);
		}
		//队头出队列
		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();
		}
		//获取队列中有效元素个数
		size_t size() const
		{
			return _con.size();
		}
		//判断队列是否为空
		bool empty() const
		{
			return _con.empty();
		}
		//交换两个队列中的数据
		void swap(queue<T, Container>& q)
		{
			_con.swap(q._con);
		}
	private:
		Container _con;
	};
}

四、priority_queue

priority_queue又被称为优先级队列，它和队列的区别在于，默认使用vector作为底层存储数据的容器，并且在vector上又使用了堆算法将vector中元素构成堆的结构，这也就意味着如果入队一组无序的数据，在出队列时会变成有序，默认情况下priority_queue是大堆，也就是降序。
08 stack、queue和priority_queue的使用和模拟实现

它相比于队列多了第三个参数，这个参数默认是less，建大堆（也就是降序，大数先出队列），也可以换成greater，建小堆（升序，小数先出队列）。

其接口和队列一样，只是在入队和出队时作了排序

成员函数 功能
push(x) 插入元素x到队尾然后排序
pop() 弹出队头元素（堆顶元素）
top() 访问队头元素（堆顶元素）
size() 获取队列中有效元素个数
empty() 判断队列是否为空
swap() 交换两个队列的内容 
#include <iostream>
#include <functional>
#include <queue>
using namespace std;
int main()
{
	priority_queue<int> q;
	q.push(3);
	q.push(6);
	q.push(0);
	q.push(2);
	q.push(9);
	q.push(8);
	q.push(1);
	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl; //9 8 6 3 2 1 0

	priority_queue<int,vector<int>,greater<int>> q1;
	q1.push(3);
	q1.push(6);
	q1.push(0);
	q1.push(2);
	q1.push(9);
	q1.push(8);
	q1.push(1);
	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}
	cout << endl; //0 1 2 3 6 8 9
	return 0;
}

使用优先级队列排序日期类

自定义类要使用less，必须要重载操作符<，要使用greater，必须要重载操作符>，并且也可以传入一个自定义的仿函数：

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

class Date
{
public:
	Date(int year = 0, int month = 0, int day = 0);
	void Print();
	//比较日期的大小
	friend bool operator>(const Date& a,const Date& b);
	friend bool operator<(const Date& a, const Date& b);
	friend bool operator==(const Date& a, const Date& b);

	//日期减日期
	int operator-(const Date& d);

	friend ostream& operator<<(ostream& out, const Date& d);

private:
	int _year;
	int _month;
	int _day;
};

//获取某年某月的天数，因为要多次调用，可以写成内联函数
inline int GetMonthDay(int year, int month)
{
	static int dayArray[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
	int day = dayArray[month];
	if (month == 2 && ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)))
	{
		day = 29;
	}
	return day;
}
//构造函数
Date::Date(int year, int month, int day)
{
	//检查日期的合法性
	if (year >= 0
		&& month > 0 && month < 13
		&& day>0 && day <= GetMonthDay(year, month))
	{
		_year = year;
		_month = month;
		_day = day;
	}
	else
	{
		cout << "非法日期";
		cout << year << "-" << month << "-" << day << endl;
	}
}


//比较大小只需要实现>和==即可，其他比较操作符都可以用这两个操作符实现，提高代码复用率
bool operator>(const Date& a, const Date& b)
{
	if (a._year > b._year)
	{
		return true;
	}
	else if (a._year == b._year)
	{
		if (a._month > b._month)
		{
			return true;
		}
		else if (a._month == b._month)
		{
			if (a._day > b._day)
			{
				return true;
			}
		}
	}
	return false;
}

bool operator<(const Date& a, const Date& b)
{
	return !(a == b) && !(a > b);
}

bool operator==(const Date& a, const Date& b)
{
	return a._year == b._year && a._month == b._month && a._day == b._day;
}

ostream& operator<<(ostream& out, const Date& d)
{
	cout << d._year << "-" << d._month << "-" << d._day << endl;
	return out;
}
struct cmp
{
	bool operator()(Date a, Date b) 
	{
		return a > b;
	}
};

int main()
{
	//priority_queue<Date,vector<Date>,greater<Date>> q;
	//priority_queue<Date, vector<Date>, less<Date>> q;
	priority_queue<Date, vector<Date>,cmp> q;//传入仿函数cmp
	q.push(Date(1, 5, 15));
	q.push(Date(10, 4, 6));
	q.push(Date(7, 7, 1));
	q.push(Date(10, 12, 8));
	q.push(Date(5, 11, 9));
	q.push(Date(10, 7, 1));

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

	return 0;
}

08 stack、queue和priority_queue的使用和模拟实现

模拟实现priority_queue

#include<vector>
#include<iostream>
namespace hjl
{
	//比较方式（使内部结构为大堆）
	template<class T>
	struct less
	{
		bool operator()(const T& l, const T& r)
		{
			return l < r;
		}
	};
	//比较方式（使内部结构为小堆）
	template<class T>
	struct greater
	{
		bool operator()(const T& l, const T& r)
		{
			return l > r;
		}
	};
	//仿函数默认为less
	template<class T, class  Container = std::vector<T>,class Compare=less<T>>
	class priority_queue
	{
	public:
		//向上调整算法，每push一个数都要调用向上调整算法，保证插入后是一个大堆
		void AdjustUp(int child)
		{
			Compare com;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[parent],_con[child]))
				{
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent= (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		//向下调整算法，每次调用pop都要进行向下调整算法重新构成大堆
		void AdjustDwon(int 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]))
				{
					std::swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		//迭代器初始化
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)//在这里传迭代器进行初始化
		{
			for (size_t i = 1; i <_con.size(); i++)
			{
				AdjustUp(i);//向上调整建堆
			}
		}

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

			AdjustUp(_con.size() - 1);
		}
		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDwon(0);
		}
		T top()
		{
			return _con[0];
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

08 stack、queue和priority_queue的使用和模拟实现

上一篇：php call_user_func用法


下一篇：practice9