精通C++ STL（八）：stack和queue的模拟实现

目录

容器适配器

stack的模拟实现

queue的模拟实现

容器适配器

        stack 和 queue 是 C++ 标准模板库（STL）中的容器适配器，而不是容器本身。这是因为它们并不像 vector、deque 或 list 那样直接管理元素的存储，而是基于其他底层容器来提供特定的接口功能。

容器适配器的特点：

• 包装容器的接口：stack 和 queue 通过包装底层容器的接口来提供特定的操作，例如 stack 提供后进先出（LIFO）的接口，而 queue 提供先进先出（FIFO）的接口。
• 不直接管理存储：这些适配器不直接处理元素的存储，而是依赖于另一个底层容器来管理元素。默认情况下，stack 和 queue 使用 deque 作为底层容器。

类模板声明中的两个模板参数：

1. 元素类型：表示适配器中存储的元素类型。例如，stack<int> 表示存储 int 类型元素的栈。
2. 容器类型：指定底层容器的类型。如果未指定，stack 和 queue 默认使用 deque 作为其底层容器。例如，stack<int, deque<int>> 表示一个使用 deque<int> 作为底层容器的 stack。

        简单理解就是：stack 和 queue 实际上是对其他容器（如 vector、deque 或 list）的包装，以便实现特定的操作行为。

        学过数据结构后我们知道，stack（栈）可以通过顺序表或链表实现，queue（队列）同样如此。在 C++ 中，如果我们定义一个 stack 并指定使用 vector 作为底层容器，那么定义出来的 stack 就是对 vector 容器进行包装，提供了栈的操作接口（如 push、pop、top 等）。

双端队列类deque

        双端队列（deque） 虽然名字中有“队列”，但实际上它更像是一个可以在两端插入数据的结构。

        为了实现下标的随机访问，双端队列需要分配连续的内存空间。如果只是在连续空间中进行操作，它的行为与 vector 类似，但在插入数据时仍需要考虑是否扩容。为了解决这个问题，双端队列采用了分段内存的策略，即分配多个连续的小块内存。这些小块内存由指针维护，类似于 list 的设计。为了保证下标访问的连续性，双端队列还引入了一个中央控制数组，用于存储指向这些小块内存的指针。这样一来，就实现了既能在两端高效插入数据，又能随机访问元素的功能。设计如下图所示：

        假设每个数据数组已经装满了整型数据。

在双端队列的头部插入一个 20 的过程如下：

1. 检查空间：首先，检查双端队列头部是否有足够的空间容纳新元素。如果头部的当前块有空闲位置，则直接插入 20；如果没有空间，则需要分配新的块。

2. 分配新块：如果没有足够的空间容纳新元素，双端队列会在头部前面分配一个新的内存块，并将这个新块链接到中央控制数组中。

3. 更新指针：将新块的指针更新到中央控制数组中，以保证下标的连续访问。

4. 插入数据：将 20 插入到新分配的块或现有块的空闲位置上。

5. 更新头部指针：插入完成后，更新头部指针，指向新插入元素的位置。

6. 

 在双端队列的尾部插入一个 30 的过程如下：

1. 检查尾部空间：首先，检查双端队列尾部的当前块是否有空余位置。如果有空闲空间，可以直接在此处插入 30。

2. 分配新块：如果尾部当前块已满，则需要在尾部分配一个新的内存块，用于存放新元素。

3. 更新中央控制数组：将新分配的块的指针添加到中央控制数组中，以保持下标访问的连续性。

4. 插入数据：将 30 插入到新分配的块或现有块的尾部空闲位置。

5. 更新尾部指针：插入完成后，更新尾部指针，指向新插入元素的位置。

6. 

        在介绍了双端队列（deque）的数据头部插入和尾部插入后，接下来讨论如何使用迭代器遍历 deque。

        双端队列的迭代器（此处仅讨论非 const 迭代器，const 迭代器的设计与此类似）结构设计如下：

 对于遍历 deque 的迭代器，其遍历思路如下：

1. 初始化：迭代器的 cur 指针最初指向 begin() 位置的元素，即第一个数据块中的第一个元素。同时，node 指向中央控制数组中第一个块的指针。

2. 遍历当前块：从 cur 指向的开始位置，一直遍历当前块中的元素，直到 cur 到达当前块的 last 位置。此时，cur 指向的元素已经全部访问完毕。

3. 移动到下一个块：

   • 如果当前块不是最后一个块，更新 node 使其指向下一个数据块的指针。
   • 将 cur 更新为下一个块的 first 位置，继续从下一个块的第一个元素开始遍历。

4. 继续遍历：重复步骤 2 和 3，依次遍历每个数据块，直到 node 指向最后一个数据块。

5. 终止遍历：当 cur 指向最后一个数据块的最后一个元素的下一个位置（即 pos 所标记的位置）时，遍历结束。

 在 STL 中，deque 被选择作为 stack 和 queue 的默认底层数据结构，主要有以下原因：

1. 操作需求：

   • stack 是一种后进先出（LIFO）的数据结构，只需要在一端进行操作，具体是 push_back() 和 pop_back() 操作。
   • queue 是一种先进先出（FIFO）的数据结构，需要在两端进行操作，具体是 push_back() 和 pop_front() 操作。

2. 性能优势：

   • deque 与 vector 比较：
     • 对于 stack，deque 在元素增长时比 vector 更高效，因为 deque 在扩容时不会像 vector 那样需要搬移大量数据。
     • deque 的内部结构支持在两端高效插入和删除操作，这对于 stack 和 queue 的操作是理想的。
   • deque 与 list 比较：
     • 对于 queue，deque 既能支持高效的两端操作，又能避免 list 在内存使用上的高开销和性能上的劣势。
     • deque 在内存使用上比 list 更加紧凑，因为 list 的每个节点都有额外的指针开销。

3. 内存管理：

   • deque 的设计使得它在内存管理上比 vector 和 list 更加高效。deque 的分段内存结构允许在两端动态扩展而不需要频繁搬移数据。
   • 对于 stack 和 queue 这种仅需在固定的一端或两端进行操作的容器类型，deque 的内存使用率较高且性能优越。

stack的模拟实现

        了解了容器适配器的概念后，stack 的模拟实现确实变得相对简单。实际上，我们只需要利用底层容器的成员函数来实现 stack 的各个接口函数即可。

具体实现代码如下： 

namespace RussLeo // 防止命名冲突
{
	template<class T, class Container = std::deque<T>>
	class stack
	{
	public:
		// 元素入栈
		void push(const T& x)
		{
			_con.push_back(x); // 将元素 x 添加到容器的末尾
		}
		
		// 元素出栈
		void pop()
		{
			_con.pop_back(); // 从容器的末尾移除最后一个元素
		}
		
		// 获取栈顶元素
		T& top()
		{
			return _con.back(); // 返回容器末尾的元素，即栈顶元素
		}
		
		const T& top() const
		{
			return _con.back(); // 返回容器末尾的元素，即栈顶元素（const 版本）
		}
		
		// 获取栈中有效元素个数
		size_t size() const
		{
			return _con.size(); // 返回容器中元素的数量
		}
		
		// 判断栈是否为空
		bool empty() const
		{
			return _con.empty(); // 如果容器为空，则返回 true；否则返回 false
		}
		
		// 交换两个栈中的数据
		void swap(stack<T, Container>& st)
		{
			_con.swap(st._con); // 交换当前栈和给定栈中的元素
		}
		
	private:
		Container _con; // 底层容器，默认为 std::deque<T>
	};
}

• push：将元素 x 添加到栈顶。_con.push_back(x) 将元素添加到底层容器的末尾，等同于栈的顶部。
• pop：移除栈顶元素。_con.pop_back() 从底层容器中移除末尾元素，等同于栈的顶部。
• top：获取栈顶元素。返回底层容器的末尾元素，_con.back()。
• size：返回栈中的元素数量。使用 _con.size() 来获取底层容器的元素数量。
• empty：检查栈是否为空。使用 _con.empty() 来检查底层容器是否为空。
• swap：交换当前栈和另一个栈中的数据。通过 _con.swap(st._con) 交换两个底层容器的内容。

queue的模拟实现

        在深入理解容器适配器的概念后，模拟实现队列（Queue）变得相对简单。实际上，我们只需利用底层容器的成员函数来实现队列的各个接口函数。

具体实现代码如下： 

namespace RussLeo // 防止命名冲突
{
	template<class T, class Container = std::deque<T>>
	class queue
	{
	public:
		// 队尾入队列
		void push(const T& x)
		{
			_con.push_back(x); // 将元素 x 添加到容器的末尾
		}
		
		// 队头出队列
		void pop()
		{
			_con.pop_front(); // 从容器的前端移除第一个元素
		}
		
		// 获取队头元素
		T& front()
		{
			return _con.front(); // 返回容器前端的元素，即队头元素
		}
		
		const T& front() const
		{
			return _con.front(); // 返回容器前端的元素，即队头元素（const 版本）
		}
		
		// 获取队尾元素
		T& back()
		{
			return _con.back(); // 返回容器末尾的元素，即队尾元素
		}
		
		const T& back() const
		{
			return _con.back(); // 返回容器末尾的元素，即队尾元素（const 版本）
		}
		
		// 获取队列中有效元素个数
		size_t size() const
		{
			return _con.size(); // 返回容器中元素的数量
		}
		
		// 判断队列是否为空
		bool empty() const
		{
			return _con.empty(); // 如果容器为空，则返回 true；否则返回 false
		}
		
		// 交换两个队列中的数据
		void swap(queue<T, Container>& q)
		{
			_con.swap(q._con); // 交换当前队列和给定队列中的元素
		}
		
	private:
		Container _con; // 底层容器，默认为 std::deque<T>
	};
}

• push：将元素 x 添加到队列的尾部。使用 _con.push_back(x) 将元素添加到底层容器的末尾。
• pop：移除队列的头部元素。使用 _con.pop_front() 从底层容器的前端移除第一个元素。
• front：获取队列头部的元素。返回底层容器的第一个元素，_con.front()。
• back：获取队列尾部的元素。返回底层容器的末尾元素，_con.back()。
• size：获取队列中元素的数量。使用 _con.size() 来获取底层容器的元素数量。
• empty：检查队列是否为空。使用 _con.empty() 来判断底层容器是否为空。
• swap：交换当前队列和另一个队列中的数据。通过 _con.swap(q._con) 交换两个底层容器的内容。