【C++】学习STL中的stack和queue-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++】学习STL中的stack和queue。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

❤️前言

今天这篇博客的内容主要关于STL中的stack、queue和priority_queue三种容器。

正文

stack和queue的使用方式非常简单，我们只要根据之前学习数据结构的经验和文档介绍就可以轻松上手。于是我们直接开始对它们的模拟实现。

stack和queue的模拟实现

stack和queue我们在数据结构阶段就曾经学习过，它们的底层结构都可以基于其他的基本数据结构进行实现。这时候我们就可以用到上篇文章中提到过的适配器模式来实现这两个模板。

实现方式只要遵从栈和队列的规则即可，代码如下：

template<typename T, typename Container = deque<T>>
class stack
{
public:
	bool empty() const
	{
		return _con.size() == 0;
	}

	size_t size() const
	{
		return _con.size();
	}

	T& top()
	{
		return *(--_con.end());
	}

	const T& top() const
	{
		return *(--_con.end());
	}

	void push(const T& x)
	{
		_con.insert(_con.end(), x);
	}

	void pop()
	{
		_con.erase(--_con.end());
	}

private:
	Container _con;
};


template<typename T, typename Container = deque<T>>
class queue
{
public:
	void push(const T& x)
	{
		_con.insert(_con.end(), x);
	}

	void pop()
	{
		_con.erase(_con.begin());
	}

	T& back()
	{
		return *(--_con.end());
	}

	const T& back() const
	{
		return *(--_con.end());
	}

	T& front()
	{
		return *(_con.begin());
	}

	const T& front() const
	{
		return *(_con.begin());
	}

	size_t size() const
	{
		return _con.size();
	}

	bool empty() const
	{
		return _con.size() == 0;
	}
private:
	Container _con;
};

这里我们在使用这两个模板的时候可以传入两个模板参数，分别为数据类型和空间适配器类型，对于stack这样的容器，我们可以传入vector作为空间适配器，因为它的规则是后进先出，我们只需要关注尾插尾删即可，这样使用vector的效率是很高的。同理，我们在使用queue时可以传入list作为空间适配器。使用了适配器模式，我们的代码更加的简洁高效。

除此之外，这里我们需要简单了解一下双端队列(deque)，也就是上面给出的默认空间适配器。deque结合了数组和链表的特点，本来是设计出来准备替代它们的产物，但是显而易见，它失败了(不然现在我们就不会学数组和链表了)。作为结合数组和链表的产物，它的随机访问效率低于vector，中间插入删除效率也很低，虽然它缓解了一些vector和list本身的问题，但是它总归替代不了vector和list。可以说，deque的优势就是头插头删、尾插尾删效率很高，这非常适合用来适配stack和queue。

优先级队列priority_queue

优先级队列(priority_queue)在数据结构中对应我们之前学的数据结构中的堆，堆的使用也非常简单，我们只要大概看看文档即可。除此之外堆根据堆内元素之间的关系被分为大根堆和小根堆，堆的堆顶元素是整个堆中的最值，这可以帮我们解决经典的Top-k问题。

优先级队列的模拟实现

在数据结构二叉树的学习阶段我们已经实现过堆的各种接口，只要稍加改动设计就成了一个优先级队列的模板，代码实现如下：

template<typename T, typename Container = std::vector<T>, typename Compare = std::less<T>>
class priority_queue
{
private:
	void AdjustDown(int parent)
	{
		int child = 2 * parent + 1;
		while (child < _con.size())
		{
			if (child + 1 < _con.size() && _cmp(_con[child], _con[child+1])) child++;
			if (_cmp(_con[parent], _con[child]))
			{
				std::swap(_con[parent], _con[child]);
				parent = child;
				child = 2 * parent + 1;
			}
			else
			{
				break;
			}
		}   
	}

	void AdjustUp(int child)
	{
		int parent = (child - 1) / 2;
		while (parent >= 0)
		{
			if (_cmp(_con[parent], _con[child]))
			{
				std::swap(_con[parent], _con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}
public:
	priority_queue() {}

	template <typename InputIterator>
	priority_queue(InputIterator first, InputIterator last)
	{
		while (first != last)
		{
			_con.insert(_con.end(), *first);
			first++;
		}
	}

	bool empty() const
	{
		return _con.empty();
	}

	size_t size() const
	{
		return _con.size();
	}

	const T& top() const
	{
		return *(_con.begin());
	}

	void push(const T& x)
	{
		_con.insert(_con.end(), x);
		AdjustUp(_con.size() - 1);
	}

	void pop()
	{
		std::swap(_con[0], _con[_con.size() - 1]);
		_con.erase(--_con.end());
		AdjustDown(0);
	}

private:
	Container _con;
	Compare _cmp;
};

首先我们看到优先级队列有三个模板参数，除了存储数据类型以外，还有空间适配器和仿函数。空间适配器想必大家比较熟悉了，对于堆来说，比较适合的类型就是数组vector。仿函数之前大家没有遇到过，这里为大家附上一个博客链接，大家可以看看：

C++ 仿函数_仿函数 c++_恋喵大鲤鱼的博客-CSDN博客https://blog.csdn.net/K346K346/article/details/82818801 简单来说，仿函数就是一类可以当作函数使用的类，它具有和函数指针类似的作用，让我们可以轻松地控制生成许多效果不同的类，减少了代码冗余。

而在优先级队列中，这个仿函数的作用是比较堆节点的大小关系，于是通过改变仿函数的种类，我们能够控制大小堆以及元素间比较的方式，优先级队列的默认仿函数为less，也就是默认的大根堆，这点需要注意。

当然，在实现优先级队列的过程中，调整位置的算法是比较难的点，也希望大家能够多加练习巩固。