【c++】栈(satck)和队列(queue)

//stack的使用：最小栈
class MinStack
{
public:
	void push(int x)
	{
		//只要有元素压栈，首先将元素保存到_elem中
		_elem.push(x);

		//如果x小于等于_min中栈顶的元素，则也要将x压栈到_min中
		if (_min.empty() || _min.top() <= x)
		{
			_min.push(x);
		}
	}

	void pop()
	{
		//如果_min栈顶元素等于_elem栈顶元素，则删除_elem栈顶元素的同时也要删除_min栈顶元素
		if (_elem.top() == _min.top())
		{
			_min.pop();
		}
		_elem.pop();
	}

	int top()
	{
		return _elem.top();
	}

	int getMin()
	{
		return _min.top();
	}
private:
	//保存栈中的元素
	std::stack<int> _elem;

	//保存栈的最小值
	std::stack<int> _min;
};

3.stack的模拟实现

以vector为底层容器模拟实现stack：

namespace lbj
{
	//以vector为底层容器模拟实现stack
	template <class T>
	class stack
	{
	public:
		stack() {}
		void push(const T& x)
		{
			_s.push_back(x);
		}
		void pop()
		{
			_s.pop_back();
		}
		T& top()
		{
			return _s.back();
		}
		const T& top()const
		{
			return _s.back();
		}
		size_t size()const
		{
			return _s.size();
		}
		bool empty()const
		{
			return _s.empty();
		}
	private:
		std::vector<T> _s;
	};
}

二、queue

1.queue的介绍

（1）queue是一种专门用于上下文先进先出操作的容器适配器，即支持push_back()和pop_back()；

（2）queue的底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器，但是底层容器都需要支持以下操作：empty()、size()、front()、back()、push_back()、pop_front()等；

（3）标准容器类deque和list满足了上述要求。默认情况下使用标准容器deque作为queue的底层容器

2.queue的使用

3.queue的模拟实现

以list为底层容器模拟实现queue：

namespace lbj
{
	//以list为底层容器模拟实现queue：
	template <class T>
	class queue
	{
	public:
		queue(){}
		void push(const T& x)
		{
			_q.push_back(x);
		}
		void pop()
		{
			_q.pop_front();
		}
		T& front()
		{
			return _q.front();
		}
		const T& front()const
		{
			return _q.front();
		}
		T& back()
		{
			return _q.back();
		}
		const T& back()const
		{
			return _q.back();
		}
		size_t size()
		{
			return _q.size();
		}
		bool empty()
		{
			return _q.empty();
		}
	private:
		std::list<T> _q;
	};
}

三、priority_queue

1.priority_queue的介绍

（1）priority_queue（优先级队列）是一容器适配器，根据严格的弱排序标准，默认情况下它的第一个元素是它所包含元素中最大的；

（2）优先级队列的上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素（优先级队列中位于开头位置的元素）

（3）priority_queue的底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。只要容器可以通过随机访问迭代器进行访问，并支持以下操作：empty()、size()、front()、push_back()、pop_back()等；

（4）标准容器类vector和deque均满足上述要求，没有指定的情况下默认使用vector作为priority_queue的底层容器。

2.priority_queue的使用

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

原文地址:https://blog.csdn.net/libj2023/article/details/135569771 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1747963556994879488.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部