【C++】STL——stack，queue

前言 这篇博客我们来看看STL库里的栈和队列结构，我们一起来看一下吧 💓 个人主页：小张同学zkf ⏩ 文章专栏：C++ 若有问题 评论区见📝 🎉欢迎大家点赞👍收藏⭐文章

1.stack介绍和使用

1.1stack介绍

stack的介绍：stack

1.2stack的使用

1.3stack的模拟实现

从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。

栈的模拟实现代码

#include<vector> namespace bite { template < class T > class stack { public : stack () {} void push ( const T & x ) { _c . push_back ( x );} void pop () { _c . pop_back ();} T & top () { return _c . back ();} const T & top () const { return _c . back ();} size_t size () const { return _c . size ();} bool empty () const { return _c . empty ();} private : std::vector < T > _c ; }; }

2.queue介绍和使用

2.1 queue的介绍

文档：queue

1. 队列是一种容器适配器，专门用于在 FIFO 上下文 ( 先进先出 ) 中操作，其中从容器一端插入元 素，另一端提取元素。 2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类， queue 提供 一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。 3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少 支持以下操作 : empty ：检测队列是否为空 size ：返回队列中有效元素的个数 front ：返回队头元素的引用 back ：返回队尾元素的引用 push_back ：在队列尾部入队列 pop_front ：在队列头部出队列 4. 标准容器类 deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器 类，则使用标准容器 deque 。

2.2queue的使用

2.3queue的模拟实现

因为 queue 的接口中存在头删和尾插，因此使用 vector 来封装效率太低，故可以借助 list 来模拟实现queue ，具体如下：

#include <list> namespace bite { template < class T > class queue { public : queue () {} void push ( const T & x ) { _c . push_back ( x );} void pop () { _c . pop_front ();} T & back () { return _c . back ();} const T & back () const { return _c . back ();} T & front () { return _c . front ();} const T & front () const { return _c . front ();} size_t size () const { return _c . size ();} bool empty () const { return _c . empty ();} private : std::list < T > _c ; }; }

3.priority_queue的介绍和使用

3.1 priority_queue的介绍

文档：priority_queue

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。 2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素 ( 优先队列中位于顶部的元素) 。 3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类, queue 提供一组特定的成员函数来访问其元素。元素从特定容器的 “ 尾部 ” 弹出，其称为优先队列的 顶部。 4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作： empty() ：检测容器是否为空 size() ：返回容器中有效元素个数 front() ：返回容器中第一个元素的引用 push_back() ：在容器尾部插入元素 pop_back() ：删除容器尾部元素 5. 标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue 类实例化指定容器类，则使用 vector 。 6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap 、 push_heap 和 pop_heap 来自动完成此操作。

其实优先级队列就是数据结构中的堆!

3.2priority_queue的使用

优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中 元素构造成堆的结构，因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue 。注意：默认情况下 priority_queue 是 大堆 。

3.3priority_queue的模拟实现

#include<vector>
template <class T>
class Less
{
public:
	bool operator()(const T& a, const T& b)
	{
		return a < b;
	}
};
template <class T>
class Greater
{
	bool operator()(const T& a, const T& b)
	{
		return a>b;
	}
};
namespace zkf
{
	template<class T,class container=vector<T>,class com=Less<T>>
	class priority_queue
	{
	public:
		priority_queue()
		{

		}
		template<class inputiterator>
		priority_queue(inputiterator w1, inputiterator w2)
		{
			while (w1 != w2)
			{
				push(*w1);
				w1++;
			}
		}
		com qw;
		void adjustup(int child)
		{
			int parent= (child-1)/2;
			while (child > 0)
			{
				if (qw(_as[parent],_as[child]))
				{
					swap(_as[child], _as[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T& s)
		{
			_as.push_back(s);
			adjustup(_as.size()-1);
		}
		void adjustdown(int parent)
		{
			int child = parent * 2 + 1;
			while (child < _as.size())
			{
				if (child + 1 < _as.size()&&qw(_as[child] , _as[child + 1]) )
				{
					child++;
				}
				if (qw(_as[parent],_as[child]))
				{
					swap(_as[child], _as[parent]);
					parent= child;
					child = parent*2+1;
				}
				else
				{
					break;
				}
			}
		}
		void pop()
		{
			swap(_as[0], _as[_as.size() - 1]);
			_as.pop_back();
			adjustdown(0);
		}
		const T& top()const
		{
			return _as[0];
		}
		size_t size()const
		{
			return _as.size();
		}
		bool empty()const
		{
			return _as.size() == 0;
		}
		const T& operator[](size_t i)const
		{
			return _as[i];
		}
	private:
		container _as;
	};
}

注意在实现优先级队列时，我们可以用仿函数来控制优先级顺序，默认是大堆，可以通过仿函数改编成小堆，我这里把仿函数也模拟实现了一下，注意仿函数没有私密的成员变量，是空类，将括号重载，通过创建个仿函数类的对象（也可以不用创建直接使用匿名对象），调用括号，实现比较，模拟成函数调用的样子，这就是仿函数

template <class T>
class Less
{
public:
	bool operator()(const T& a, const T& b)
	{
		return a < b;
	}
};
template <class T>
class Greater
{
	bool operator()(const T& a, const T& b)
	{
		return a>b;
	}
};

结束语 STL里栈和队列还是比较简单的，下片博客我们来看一下STL里一个特殊的结构deque(双端队列)。 OK，感谢观看！！！