C++stack与queue的模拟实现

??樊梓慕:个人主页

 ??个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

??每一个不曾起舞的日子,都是对生命的辜负


前言

stack与queue的实现比较简单,本篇不会有太大的篇幅,但值得我们学习的是『 适配器』的概念。


欢迎大家??收藏??以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。

=========================================================================

GITEE相关代码:??fanfei_c的仓库??

=========================================================================


1.适配器

stack与queue并不属于容器,而是『 适配器』。

适配器其实就是对已经存在的容器进行封装得到的。

在STL标准库中,stack与queue的底层默认使用deque容器。

 deque我们本篇文章不介绍,大家只需要知道他类似于vector与list,并且deque具有他们两个容器的特性即可。

适配器就像是我们的充电器,我国家庭电路电压为220v,但却可以通过不同的电源适配器达到不同的功率。

模板参数的这一用法我们上篇文章提到过:

当我们不传模板参数时,stack与queue都默认使用deque容器来构建栈或者队列,但我们也可以自己设定模板参数,就如同之前学习『 数据结构』时,栈或者队列既有顺序结构也有链式结构一样,在『 C++』中,我们只需要设定模板参数,即可实现顺序栈、顺序队列或者链栈、链队列,这就体现出了模板参数的妙用。


2.模拟实现源码

2.1stack

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()
	{
		return _con.back();
	}

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

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

private:
	Container _con;
};

2.2queue

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()
	{
		return _con.size();
	}

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

private:
	Container _con;
};

2.3如何实现底层基于vector或list的栈或队列呢?

其实非常简单,就是将对应的模板参数设定为vector或list即可,比如:

int main()
{
	stack<int,vector<int>> s;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);
	while (!s.empty())
	{
		cout << s.top() << " ";
		s.pop();
	}
	cout << endl;
	return 0;
}

另外注意:

  • 函数参数传参是在『 使用时传参』,传递的是『 对象』;
  • 模板参数传参是在『 编译时传参』,传递的是『 类型』。