[C++] STL ：stack&&queue详解 及 模拟实现

标题：[C++] STL ：stack&&queue详解

@水墨不写bug

---

---

目录

（一）stack简介

（二）queue简介

（三）容器适配器

（四）stack和queue的模拟实现

---

/**
 *                    _ooOoo_
 *                   o8888888o
 *                   88" . "88
 *                   (| -_- |)
 *                    O\ = /O
 *                ____/`---'\____
 *              .   ' \\| |// `.
 *               / \\||| : |||// \
 *             / _||||| -:- |||||- \
 *               | | \\\ - /// | |
 *             | \_| ''\---/'' | |
 *              \ .-\__ `-` ___/-. /
 *           ___`. .' /--.--\ `. . __
 *        ."" '< `.___\_<|>_/___.' >'"".
 *       | | : `- \`.;`\ _ /`;.`/ - ` : | |
 *         \ \ `-. \_ __\ /__ _/ .-` / /
 * ======`-.____`-.___\_____/___.-`____.-'======
 *                    `=---='
 *
 * .............................................
 *          佛祖保佑             永无BUG
 */

正文开始：

（一）stack简介

        通过查询cplusplus我们可以发现stack与以往的容器不同，比如vector；

        比较上图，vector是一种容器；而栈是一种容器适配器。什么是容器适配器？在这里我们放在后文解释，我们首先了解一下什么是栈：

        1.STL的栈是一种容器适配器，栈是一种数据结构，数据遵循后进先出，并且只能从栈的一端进行数据的插入与提取。

        2.栈的功能实现比较简便，我们发现我们可以把vector或者是list当成是一个栈：能把vector或list当成一个栈，是可以把栈实现为容器适配器的原因。

        容器适配器就是将一种特殊的类作为底层容器，并提供一组特定的成员函数来访问元素。

        3.stack的成员函数比较少，功能简单：

        这些成员函数的具体功能如果你有疑问，可以参考这一篇文章：《栈详解及C实现》

---

（二）queue简介

        1.队列也是一种容器适配器，队列是一种数据结构，数据遵循先进先出，数据从容器一端进入，从另一端提取。

        2.STL中，队列通过容器适配器方式实现，在这里，容器适配器就是通过封装一个特定的类，同时提供特定的接口成员函数来访问内部的元素数据。

        3.常见的队列的成员函数有：

（三）容器适配器

        通过上文对两个容器适配器的讲述，你或许已经对容器适配器有了一定的认识。但是容器适配器到底是什么？

        容器适配器是C++中一种特殊类型的容器，它通过封装现有的容器类实现不同的数据结构和功能。容器适配器通过提供不同的接口和封装现有容器的功能，使得程序员可以根据需求选择合适的数据结构。常见的容器适配器有栈（stack）、队列（queue）和优先队列（priority_queue）。

        我们在使用容器适配器的时候，可以选择底层的容器，但是在使用容器适配器的时候，不需要关心底层实现的容器到底是什么。

        比如：我们可以用vector容器或者list容器来实现stack的适配器，如果我们已经成功实现，在使用stack的时候，就不需要关心底层究竟是vector还是list了。

（四）stack和queue的模拟实现

        我们可以通过使用模板参数T，来使得容器内的数据类型更加灵活；通过设置一个参数Container来接受我们选择的容器。

模拟实现STL的stack源码：

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

模拟实现queue：

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

        在模拟实现中，我们发现模板参数Container给了一个缺省参数deque；deque是STl的一种容器，它具有比vector和list更加复杂的结构，这里我们放在下次分享。

---

完~

未经作者同意禁止转载