C++初阶——简单实现stack和queue

目录

1、Deque(了解)

1.1 起源

1.2 结构

1.3 优缺点

1.4 应用

2、Stack

3、Queue

4、Priority_Queue

注意：stack，queue，priority_queue是容器适配器(container adaptor) ，封装一个容器，按照某种规则使用，一般不实现迭代器。

1、Deque(了解)

1.1 起源

vector和list优缺点，挺互补的，能不能实现一个容器，都具备他们的优点，就这样，deque诞生了，但是从现在来看，deque，并不算成功 。

1.2 结构

中控数组(map)，是一个指针数组，指针指向一个buffer数组的地址，通过迭代器遍历。

细节：

1. map中的指针，一开始放在中间位置，方便头插数据。

2. 使用两个迭代器，start，finish。

3. 通过，取模，除，找到是在第几个buffer数组的第几个位置。

1.3 优缺点

优点：

1. 头插尾插效率高。

2. 随机下标访问也不错。

缺点：

3. 中部位置插入删除，需挪动数据，效率低。

4. 遍历数据，需频繁检查，效率低。

1.4 应用

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

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

2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；

    在queue中元素增长时，deque不仅效率高，而且内存使用率高。(一次开更多的空间，只存数据，不存节点)

2、Stack

#pragma once
#include <deque>

using namespace std;

namespace Lzc
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top() const
		{
			return _con.back();
		}
		size_t size() const
		{
			return _con.size();
		}
		bool empty() const
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

3、Queue

#pragma once
#include <deque>

using namespace std;

namespace Lzc
{
	template<class T,class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_front();
		}
		const T& front() const
		{
			return _con.front();
		}
		const T& back() const
		{
			return _con.back();
		}
		size_t size() const
		{
			return _con.size();
		}
		bool empty() const
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

4、Priority_Queue

容器适配器，封装vector，采用堆的结构。堆+堆排序+topK问题_大顶堆小顶堆java-CSDN博客

先介绍一下仿函数：本质是一个类，这个类重载operator()，他的对象可以像函数一样使用。

如：Less le;    le.operator()(x,y) 等价于 le(x,y);

#include <algorithm>
#include <vector>

using namespace std;

// less(<) 升序
// greater(>) 降序
template<class T>
struct Less
{
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

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

int main()
{
	vector<int> v = {3,2,4,5,1,6,7,8,9};

	// void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

	sort(v.begin(),v.end(),Less<int>()); // 升序 函数模板，传对象(匿名对象)
	sort(v.begin(),v.end(),Greater<int>()); // 降序

	return 0;
}

std::priority_queue，默认less，建大堆。

#pragma once
#include <vector>

using namespace std;

namespace Lzc
{
	template<class T, class Container = vector<T>, class Compare = less<T>> // 使用std中的less<T>和greater<T>
	class priority_queue
	{
	public:
		void AdjustUp(size_t child)//建大堆，child为插入元素的下标
		{
			size_t parent = (child - 1) / 2;
			Compare com;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (com(_con[parent], _con[child])) //建大堆
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (parent - 1) / 2;
				}
				else
					break;//没有交换，则就是在这个位置
			}
		}

		void AdjustDown(size_t parent)//建大堆,n为a的元素个数，parent为要向下调整的元素下标
		{
			size_t child = 2 * parent + 1;
			Compare com;
			while (child < size())
			{
				//if (_con[child] < _con[child + 1] && child + 1 < n) // 假设法，建大堆
				if (com(_con[child], _con[child + 1] && child + 1 < size()))
					child++;
				// if (_con[parent] < _con[child]) // 建大堆
				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = 2 * child + 1;
				}
				else
					break;
			}
		}

		void push(const T& val)
		{
			_con.push_back(val);
			AdjustUp(size() - 1);
		}
		void pop()
		{
			swap(_con[0], _con[size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}
		const T& top() const
		{
			return _con.front();
		}
		size_t size() const
		{
			return _con.size();
		}
		bool empty() const
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}