【STL源码剖析-空间配置器】stack、queue简单实现

举头天外望

无我这般人

目录

stack 的概述

stack 的实现

queue 的概述

queue 的实现

契子✨

我们之前学过了 vector、list 这些 STL 的（容器）

而我们今天将要学习空间配置器 -- stack、queue，那什么是空间配置器呢？

简单来讲就是 stack、queue 的底层完成工作具有<修改其他容器所形成的另一种风貌>的性质，所以被称为 adapter （配置器）

stack 的概述

stack 是一种先进后出的结构，它只有一个出口。stack 允许新增元素、移除元素、取得最顶端元素。但除了最顶端之外，没有任何其他方法可以存取 stack 的其他元素。换而言之 stack 不允许有走访行为

将元素推入 stack 的动作叫做 push，将元素推出 stack 的动作叫做 pop

以某种既有容器作为底部，将其介面改变，使符合 [先进后出] 的特性，形成一个 stack，是很容易做到的。比如：vector (顺序栈)、list (链栈)、deque，我们以 vector 为例：vector 是面向开口的资料节点，若以 vector 的头部为封闭的 stack 的底部，尾部为 stack 开口的顶部，就轻而易举地形成了一个 stack 。因此，我们可以将 vector 作为预设情况下的 stack 的底层结构，stack 的实现非常简单这里完整列出：

stack 的实现

	template<class T, class Sequence = vector<T> >
	class stack
	{
	public:
		void push(const T& val)
		{
			c.push_back(val);
		}

		void pop()
		{
			c.pop_back();
		}

		const T& top() const
		{
			return c.back();
		}

		bool empty() const
		{
			return c.empty();
		}

		size_t size() const
		{
			return c.size();
		}

	private:
		Sequence c;
	};

我们发现 stack 会意底层容器完成所有工作，而这种具有 [ 修改/套用 其他容器，形成的另一种风貌] 的性质称之为空间配置器：container adapter

	template<class T, class Sequence = vector<T> >

我们右边的赋值行为其实就是传缺省值，对的 ~ 模板也能传缺省值哦

除了能传 vector 还可以传 list、deque（这个容器之后会讲）

如果不传就会默认用 vector 的底层，传了就会用你所指定的底层操作

如果你真的想要传的话 ~ 就是这个酱紫的

stack<int, list<int>> str;

可能有老铁会问：为什么没有看到构造和析构呢？因为不写即正义：

默认构造函数会自动调用自定义类型成员变量的构造函数

默认析构函数会自动调用自定义类型成员变量的析构函数

这里先提一下：

stack 没有迭代器！ stack 的所有元素的进出都符合 [后进先出] 的条件，只有 stack 的顶端元素，才会被外界取用。所以 stack 不提供走访功能，也不提供迭代器

代码测试：

void stack_test()
{
	stack<int> str;
	str.push(1);
	str.push(2);
	str.push(3);
	str.push(4);
	while (!str.empty())
	{
		std::cout << str.top() << " ";
		str.pop();
	}
	return 0;
}

我们知道 stack 有很多与之匹配的容器，我这里就不一一展示了，直接拿过来测试一下呗

void stack_test()
{
    stack<int,list<int>> str;
	str.push(1);
	str.push(2);
	str.push(3);
	str.push(4);
	while (!str.empty())
	{
		std::cout << str.top() << " ";
		str.pop();
	}
	std::cout << std::endl;
	stack<int, deque<int>> arr;
	arr.push(5);
	arr.push(6);
	arr.push(7);
	arr.push(8);
	while (!arr.empty())
	{
		std::cout << arr.top() << " ";
		arr.pop();
	}
	std::cout << std::endl;
}

queue 的概述

queue 是一种先进先出的结构，它有两个出口。queue 允许新增元素、移除元素、从最底层加入元素、取得最顶端的元素。但除了最低端可以加入、最顶端可以取出，没有任何其他方法可以存取 queue 的其他数据。换而言之 queue 不允许有走访行为，也就不提供迭代器

将元素推入 queue 的动作称为 push、将元素推出 queue 的动作称为 pop

以某种既有的容器作为底层，将其介面改变，使其符合 [先进先出] 的特性，形成一个 queue 很容易做到。比如：list、deque（deque 是一个双端队列，可以在队列的两端进行元素的插入和删除操作），我们若以 list 为底部为入口增数据，头部为出口删数据，就可以形成 queue。我们可以将 list 作为预设情况下的 queue 的底层结构，queue 的实现非常简单这里完整列出：

queue 的实现

	template <class T, class Sequence = list<T> >
	class queue
	{
	public:
		bool empty() const
		{
			return c.empty();
		}

		size_t size() const 
		{
			return c.size();
		}

		T& front()
		{
			return c.front();
		}

		const T& front() const
		{
			return c.front();
		}

		T& back()
		{
			return c.back();
		}

		const T& back() const
		{
			return c.back(); 
		}

		void push(const T& x)
		{
			c.push_back(x); 
		}

		void pop() 
		{
			c.pop_front(); 
		}

	private:
		Sequence c;
	};

这就完成了 ~ 是不是很简单 -- 因为空间配置器的底层都是依据某种容器，简单来说就是容器套个壳，功能受到了限制罢了

代码测试：

void queue_test()
{
	queue<int> str;
	str.push(1);
	str.push(2);
	str.push(3);
	str.push(4);
	while (!str.empty())
	{
		std::cout << str.front() << " ";
		str.pop();
	}
}