C++之stack/queue-EW帮帮网

封装容器：容器适配器通过封装底层容器，允许用户以一种标准化的方式访问数据，而无需关注容器的实现细节。例如，可以使用容器适配器来将栈（stack）、队列（queue）等数据结构的行为抽象化，统一接口。
适配不同容器：容器适配器能够将不同类型的容器（如数组、链表等）进行适配，使得操作接口一致，便于使用。例如，标准库中的队列（queue）可以使用不同的容器作为底层实现，容器适配器保证了相同的行为接口。
简化操作：通过提供简洁的操作接口，容器适配器可以帮助开发者避免直接操作底层容器的复杂性，简化代码的开发和维护。

容器适配器的优势：

统一接口：通过适配不同的容器，提供统一的接口，减少不同容器间的差异。
代码简化：开发者不需要理解底层容器的细节，可以专注于高层次的功能开发。
可扩展性：可以灵活替换底层容器而不影响外部接口，增加系统的可扩展性和灵活性。

常见的容器适配器：

栈（Stack）：在许多编程语言（如C++、Java）中，栈通常是通过底层容器（如deque 或 vector）实现的。栈的操作是基于后进先出（LIFO）原则，而容器适配器会提供push、pop等操作接口，简化栈的使用。
队列（Queue）：队列通常使用底层容器（如deque 或 list）实现，提供先进先出（FIFO）的行为。容器适配器会提供enqueue（入队）和dequeue（出队）等方法，用户通过这些方法与队列交互，而无需关心底层实现。
优先队列（Priority Queue）：优先队列也是容器适配器的一种，通常采用堆（heap）作为底层容器，允许按优先级顺序处理元素。容器适配器会提供插入、访问最大（或最小）元素等操作接口。

总结来说，容器适配器通过封装具体的容器实现，简化了程序的使用和管理，并能为用户提供统一的操作接口，使得各种数据结构的操作更加一致和灵活。

1.2 STL标准库中stack和queue的底层结构

stack与queue也能够像vector和list那样能够存储数据以及对数据的处理，但是在STL中并没有将它们分类为容器，而是将它们分类为容器适配器，它们的底层结构是通过容器进行封装实现的，它们就像是一个适配器，将那个底层的容器封装，从而实现一个新的结构。在STL中默认使用deque作为底层容器进行封装。

我们给了模板一个容器的参数，并给了一个缺省值deque。我们传递过去的容器参数必须要确保能够实现我们容器适配器的基本接口，我们之前所学习的容器vector与list的接口种类有所差异，而且有些接口vector而list没有，有些接口list有而vector没有。但是deque相当于它们两个的一个结合体，对于vector与list的接口，deque都有。因此deque作为缺省值就能够很好地满足那些容器适配器的需求了。

1.2.1 deque的简单介绍

deque的基本原理：

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与 list比较，空间利用率比较高。

上面那些接口是deque的所有接口，我们之前vector,list所学习的接口是不是都在上面呢？它不仅能够支持下标运算符，还能支持头插尾插/头删尾删等操作。这就依赖于它独特的存储结构。deque并不是一个连续的空间，而是由一个个小空间拼接起来的，它就相当于我们之前所学习的二维数组的一个动态版本。如下图，是deque的一个空间展示图。

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

那deque是如何借助其迭代器维护其假想连续的结构呢？

我们可以通过上面两张图片来理解deque的迭代器实现原理。deque有两个迭代器，分别是start，finish。每个迭代器上有四个指针：cur,first,last,node。我们将node指针指向我们的中控数组map的中间位置，然后map数组中的指针再指向缓冲区buffer数组，我们的start迭代器中的first指针与last指针分别指针buffer数组的起始位置与终止位置，cur指针指向我们当前元素的位置，finish指针则是指向我们map数组中最后一个buffer数组起始与终止位置。这么一看，deque的迭代器实现确实有点麻烦，但是不得不说它也很巧。我们如果想要头插或者尾插的话，我们不用进行移动数据，我们如果想要头插的话，我们直接再start迭代器中node指针所指向位置的前一个位置加一个指针指向buffer数组，然后再数组的最后一个位置插入数据就行，然后修改一下start迭代器中的first,last,cur指针即可。对于尾插与头插的操作差不多。

deque的缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。我们如果想要遍历deque中某个数据的位置，我们可以通过 / 运算与 % 运算来找到那个数据的具体位置，但那是对于“满打满算”的deque而言的，我们可以直接算出来那个数据的位置，如果我们中间插入/删除了一些数据，一些buffer数组就不是满的了，就会出现某个数组出现就几个的情况，那样我们再使用下标运算符就不太适合了，计算那个数据的位置也不合适了。

为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如 list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。

2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

结合了deque的优点，而完美的避开了其缺陷。

二、stack

2.1 satck的介绍

stack就是我们在数据结构中学习的栈，在C++中，我们将stack分类为容器适配器，上面是stack在官方文档上的介绍，上面主要介绍的是stack是一个后进先出的结构而且是容器适配器的一种，它的接口主要是上面那五种。上面那几种接口使用也是十分简单的，由于容器适配器是在容器的基础上封装实现的，因此它们对于接口的使用和容器是一样的。这里我就来介绍一下它的构造函数。

stack的构造函数只有一个无参构造函数，因此我们在使用构造函数来实例化一个stack对象时，我们就不能给它传递参数了，否则它就会报错，我们只能够实例化出来一个空的stack，然后再往栈里面插入元素。（我们不能够像之前那样，直接使用初始化列表将我们想要的内容直接初始化）

其实对于stack的介绍，我们在数据结构已经详细学习过了，这里我们在C++中就直接将我们在数据结构实现的那一套直接拿过来用来，我们在后面做题也不用自己来手搓一个栈再来使用了，这样就使得代码更加简洁明朗。

2.2 stack的模拟实现

#pragma once
#include<vector>
#include<list>
#include<deque>

/*
* 头文件在预处理的时候，编译器不会展开的，只有我们在源文件中添加了头文件了，编译器才会展开它的头文件
* 因此下面我们模板参数中给定的一个容器参数deque，即使我们已经包含了它的头文件了，但是在头文件中它并不会进行展开的
* 只有在源文件中它们才会展开出来
* 因此头文件报错，并不会导致编译错误
*/

/*
stack与queue都是容器适配器，它们都不是容器，因此它们都是不能够使用迭代器来进行遍历的
对于上面两个都是不可以使用下标运算符的，因为它们两个的物理结构特殊
*/

namespace hjc
{
	//容器deque是一个双端队列，它是一个容器，具有许多接口，因此它可以作为我们模拟实现stack的容器参数的缺省值
	//我们给定的缺省值，要确保我们模拟实现的接口它可以提供，否则它们就会报错
	template<class T, class Container = deque<T>>  //我们在参数处设置两个参数，一个是元素的类型，一个是复用的容器类型
	//我们这里模拟实现stack这个容器适配器是通过其他容器复用实现的
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

		bool empty() const
		{
			return _con.empty();
		}
	private:
		Container _con;  //我们定义的成员变量即一个容器变量，后面我们就通过这个变量来调用它的接口来实现我们stack的功能
	};
}

在我们模拟实现stack之前，我先来介绍一个小知识：我们模拟实现stack时，是将它们放到一个头文件中，然后实现的。我们在头文件中的代码在编译时是不会运行的，因此我们在源文件中编译时即使头文件有报错也不会有影响的（如果我们没有包含那个报错的头文件，但是两个文件在同一个编译器上）如果我们将头文件包含到了源文件了之后，编译器在编译的时候就会将头文件展开到源文件中了，这时如果头文件中出现报错了，那么源文件编译时也会出现报错。

现在我来介绍一下stack的模拟实现：其实我们可以根据stack作为容器适配器这个特点来模拟实现它，我们在定义类模板参数的时候，我们除了定义类对象的数据类型，再定义一个容器类型参数，我们在上面已经说过了我们将deque这个容器作为它的缺省值参数。我们的成员变量就定义一个容器类型的变量，对于它的成员方法，我们直接使用那个容器变量来复用它的接口即可。总而言之，对于容器适配器的模拟实现是十分简单的，我们直接使用容器来复用它的接口就行了。

三、queue

3.1 queue的介绍

这是queue在官方文档上的介绍，主要介绍它是一种容器适配器，它是一种先进先出的结构。我们只能够在队首出数据，队尾进数据。它的接口即上面六种接口。

queue的构造函数也只有一种无参构造函数，因此我们在构造初始化时，只能够构造一个空的queue。（我们同样不能够使用初始化列表进行初始化）

3.2 queue的模拟实现

#pragma once
#include<vector>
#include<list>
#include<deque>

namespace hjc
{
	//同样的，和stack一样，我们在模板参数中也设置两个参数，第二个参数放置容器参数，然后我们使用这个容器来复用实现queue
	//由于deque这个容器的接口种类很全，因此我们使用这个容器作为我们的容器类型缺省值
	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() const 
		{
			return _con.front();
		}

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

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

		bool empty() const
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

对于queue的模拟实现，我就不多介绍了，我们同样使用容器deque作为底层容器来模拟实现出来queue。deque对于queue的接口都是有的，因此我们是可以将其作为缺省值的。

四、priority_queue

4.1 priority_queue的介绍

priority_queue（优先队列）也是一种容器适配器，这个队列遵循弱排序标准，队列的第一个元素总是最大的，它类似于我们数据结构中所学习的堆（大堆）。priority_queue对于stack和queue的模板参数多了一个仿函数参数（class Compare），这个参数是确定了优先队列遵循什么排序标准来进行排序，这个容器适配器我们使用vector作为它的底层实现容器。优先队列它与队列（queue)的主要区别就是优先队列它的队列元素是按照某种顺序进行排列的。（less仿函数--->队列按照从大到小的顺序进行排列，greater仿函数--->队列按照从小到大的顺序进行排列）

我们从上面的类原型，我们可以看到，优先队列的的底层容器不再是deque而是vector了，因为priority_queue遵循的是随机迭代器的访问规则（容器适配器中没有迭代器），而deque遵循的是反向迭代器的访问规则，因此我们选择同是随机迭代器的vector(vector中有所有priority_queue的接口）

4.2 priority_queue的模拟实现

#pragma once
#include<vector>

namespace hjc
{
	//下面两个是仿函数（就是使用模板写出两个类，然后类中包含函数（对括号进行运算符重载））
	template <class T>
	struct less
	{
		bool operator() (const T& x, const T& y) const
		{
			return x < y;
		}
	};

	template <class T>
	struct greater
	{
		bool operator() (const T& x, const T& y) const
		{
			return x > y;
		}
	};

	template<class T, class Container = vector<T>, class Compare = less<T>>  //模板参数这里多了一个仿函数参数
	class priority_queue
	{
	public:
		// 强制生成一个无参构造函数（因为编译器是当我们显示写了构造函数之后就不会再默认生成构造函数了，但是我们这样写就可以了）
		//这个是C++11开始适用的
		priority_queue() = default;

		//写一个使用迭代器区间来进行的构造函数
		//在这个构造函数体中直接进行建堆操作，直接生成大堆/小堆的形式
		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)
		{
			// 建堆
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				AdjustDown(i);
			}
		}

		void AdjustUp(int child)
		{
			Compare com;  //由于仿函数是一个类，因此我们需要实例化一个对象，给后面操作使用
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (parent - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp(_con.size() - 1);
		}

		void AdjustDown(int parent)
		{
			Compare com;

			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				// 假设法，选出左右孩子中小的那个孩子
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++child;
				}

				//if (_con[parent] < _con[child])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();

			AdjustDown(0);
		}

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

		const T& top()
		{
			return _con[0];
		}

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

	private:
		Container _con;
	};
}

虽然priority_queue也是容器适配器，但是它的模拟实现不像前面两种那样只是使用容器复用一下就可以了，由于优先队列具有特殊的性质（能够使队列按从大到小或从小到大的顺序进行排列），这个类似于我们数据结构阶段学习的堆，于是我们在模拟实现中就需要使用一些堆排序算法对我们插入/删除后的队列进行一下调整。

这里我们在定义priority_queue的类模板参数的时候，我们多定义了一个仿函数参数，这个仿函数是为了我们仅通过修改这个参数就能够改变优先队列的排列顺序，这个仿函数我们会在后面会详细讲解的，这里我们只需要知道如何定义使用它就行了，具体使用方式可以参考上面的模拟实现代码。我们在上面的模拟代码中写了两个构造函数：一个无参的，一个有参的（参数为迭代器区间）。对于无参的构造函数，编译器一般都是会默认生成的，但是如果我们已经显示实现了一个构造函数的话，编译器就不再会默认生成那个无参构造函数了，但是在C++11中，如果我们将无参构造函数后面加上一个default,那么就能够强制生成一个无参构造函数。上面比较重要的就是堆排序算法，这个在数据结构阶段我们已经详细讲解了，这里我们就不多赘述了。

C++之stack/queue

前言

一、容器适配器

1.1 什么是容器适配器