stack_queue常用接口及模拟实现

目录

容器适配器

a.概念

b.底层结构

c.deque

① 原理

② 缺陷

d.底层默认容器

stack

a.基础构造

b.常用接口

c.模拟实现

queue

a.基础构造

b.常用接口

c.模拟实现

priority_queue

a.基础构造

b.常用接口

① less & greater

② 使用方法

c.模拟实现

容器适配器

a.概念

        适配器是一种设计模式（设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结），该种模式是将一个类的接口转换成客户希望的另外一个接口

b.底层结构

STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：

c.deque

① 原理

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

迭代器遍历的实现

② 缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的

与list比较，deque底层是连续空间，空间利用率比较高，不需要存储额外字段

deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率较低

d.底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list

STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

① stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。

② 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高

stack

a.基础构造

        栈是一种特殊的线性表，它遵循“后进先出”（Last In First Out，LIFO）的原则，具有压栈和弹栈两种基本操作

b.常用接口

大家可以配合C++官网的介绍来看下面的内容

stack - C++ Reference

c.模拟实现

// 除 deque 以外，也可以复用 vector
#include<deque>

namespace tianci
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_back();
		}

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

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

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

	private:
		Container _con;
	};
}

queue

a.基础构造

        队列是一种遵循“先进先出”（First In First Out，FIFO）原则的线性数据结构。与栈不同，队列允许在一端插入元素（入队），而在另一端删除元素（出队）

b.常用接口

大家可以配合C++官网的介绍来看下面的内容

queue - C++ Reference

c.模拟实现

// 除 deque 以外，也可以复用 list
#include <deque>

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

		void pop()
		{
			_con.pop_front();
		}

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

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

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

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

	private:
		Container _con;
	};
}

priority_queue

a.基础构造

priority_queue是一种基于容器适配器的优先队列数据结构，类似于堆，并且默认是大堆

priority_queue默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue可以考虑使用在需要堆的问题中

（关于堆算法，大家可以看看我数据结构里的堆的实现这篇文章，里面有详细的介绍）

b.常用接口

大家可以配合C++官网的介绍来看下面的内容

priority_queue - C++ Reference

① less & greater

关于priority_queue的使用还有一个点，就是选择大堆or小堆

C++中 less 和 greater 是用来专门比较大小的类

② 使用方法

大家需要注意的是，greater对应的是小堆，less对应的是大堆，这里设计的有点奇怪

c.模拟实现

对于priority_queue的模拟实现相对麻烦一点，因为涉及到堆算法和模版的使用

（大家可以先看看我另外两篇文章，堆的实现和模版，里面有介绍堆算法以及模版的一些知识点，再来看模拟实现会理解的通透一点）

#include<vector>

namespace tianci
{
	template <class T>
	struct less
	{
		bool operator() (const T& x, const T& y) const
		{
			return x < y;
		}
	};

	template <class T>
	struct greater
	{
		bool operator() (const T& x, const T& y) const
		{
			return x > y;
		}
	};


	template<class T, class Container = vector<T>, class Compare = less<int>>
	class priority_queue
	{
	public:

		// 强制生成
		priority_queue() = default;

		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)
		{
			// 建堆
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				AdjustDown(i);
			}
		}

		void Adjustup(size_t child)
		{
			Compare com;

			size_t parent = (child - 1) / 2;
			
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void push(const T& x)
		{
			_con.push_back(x);
			Adjustup(_con.size() - 1);
		}

		void Adjustdown(size_t parent)
		{
			Compare com;

			size_t child = parent * 2 + 1;

			while (child < _con.size())
			{
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++child;
				}

				//if (_con[parent] < _con[child])
				if(com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			Adjustdown(0);
		}
		
		size_t size()const
		{
			return _con.size();
		}

		const T& top()
		{
			return _con[0];
		}

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

	private:
		Container _con;
	};
}

本篇文章到这里就结束啦，希望这些内容对大家有所帮助！

下篇文章见，希望大家多多来支持一下！

感谢大家的三连支持！