stack,queue,priority_queue的模拟实现，适配器deque

code-child

发布于 2023-05-30 14:23:00

1580

发布于 2023-05-30 14:23:00

文章被收录于专栏：codechild

在我们模拟实现stack,queue的时候，我们会用deque作为默认的适配器

那么deque的底层是什么呢？可以说是一个指针数组，当然该数组是动态的，它有一个中控指针，中控指针指向首元素的所在的那一行buffer数组，对于改数据结构，我们支持随机访问，如果有频繁的头插（删）和尾插（删)，选择该结构还是不错的。

stack的模拟实现

cpp	template<class T,class Container=deque<T>>
	class stack
	{
		Container c;
	public:
		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();
		}
		bool empty()
		{
			return c.empty();
		}
		size_t size()const
		{
			return c.size();
		}
	};

queue

cpp	template<class T,class Container=deque<T>>
	class queue
	{
		Container c;
	public:
		void push(const T& x)
		{
			c.push_back(x);
		}
		void pop()
		{
			c.pop_front();
		}
		bool empty()
		{
			return c.empty();
		}
		size_t size()const
		{
			return c.szie();
		}
		T& back()
		{
			return c.back();
		}
		const T& back()const
		{
			return c.back();
		}
		T& front()
		{
			return c.front();
		}
		const T& front()const
		{
			return c.front();
		}
	};

priority_queue的模拟实现

priority_queue为优先级队列，它的底层是用堆来实现的，默认用的vector容器来实现的，

cpp	template<class T,class Container=vector<T>,class Compara=less<T>>
	class priority_queue
	{
		Container c;
	public:
		priority_queue(){}
		template<class iterator>
		priority_queue(iterator first, iterator last)
		{
			while (first != last)
			{
				c.push_back(*first);
				++first;
			}

			for (size_t i = (c.szie() - 1-1)/2; i >= 0; i--)
			{
				adjust_down(i);
			}
		}
		void push(const T& x)
		{
			c.push_back(x);
			adjust_up(c.size()-1);
		}
		void pop()
		{
			std::swap(c[0], c[c.size() - 1]);
			c.pop_back();
			adjust_down(0);
		}
		void adjust_up(size_t child)//大堆
		{
			Compara com;
			size_t father = (child - 1) / 2;
			while (child>0)
			{
				if (com(c[father] ,c[child]))
				{
					std::swap(c[father], c[child]);
					child = father;
					father= (child - 1) / 2;
				}
				else
					break;
			}
		}
		void adjust_down(size_t father)//大堆
		{
			Compara com;
			size_t child = 2 * father + 1;
			if (child + 1 < c.size())
			{
				if (com(c[child] , c[child+1]))
					child += 1;
			}
			while (child<c.size())
			{
				if (com(c[father], c[child]))
				{
					std::swap(c[father], c[child]);
					father = child;
					child= 2 * father + 1;
				}
				else
					break;
			}
		}
		size_t size()
		{
			return c.size();
		}
		T& top()
		{
			return c[0];
		}
		const T& top()const
		{
			return c[0];
		}
		bool empty()
		{
			return c.empty();
		}
	};
	//下面为仿函数
	template<class T>
	class less
	{
	public:
		bool operator()(const T& a,const T& b)
		{
			return a < b;
		}
	};
	template<class T>
	class great
	{
	public:
		bool operator()(const T& a, const T& b)
		{
			return a > b;
		}
	};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-05-26c，如有侵权请联系 cloudcommunity@tencent.com 删除

queue