C嘎嘎探索篇：栈与队列的交响：C++中的结构艺术

C嘎嘎探索篇：栈与队列的交响：C++中的结构艺术

C嘎嘎探索篇：栈与队列的交响：C++中的结构艺术

前言：

小编在之前刚完成了C++中栈和队列（stack和queue）的讲解，忘记的小伙伴可以去我上一篇文章看一眼的，今天小编将会带领大家吹奏栈和队列的交响，完成对于他们的模拟实现，使各位更容器去了解它们为什么被叫做容器适配器。

正文：

1.stack的模拟实现

首先我们就要先实现stack的模拟实现，栈我们以前在数据结构阶段是用顺序表进行实现的，小编此时也是要用一个容器来对其进行实现的，我们在它的众多接口中，不难发现stack是和vector是很像的，所以我们想要实现出stack，就是要给予vector容器进行模拟实现的，当然通过上图我们知道系统是用双端队列（deque）进行实现的，但是比其它，我还是更喜欢使用vector进行模拟实现，小编建议读者朋友在看我模拟实现之前，倘若不了解vector是如何进行使用的，可以先看我之前写过的文章来回顾一下（我先不放上链接了，因为在我写本文之前我还没有发布那篇文章），因为等会我会使用vector的一些接口来帮助我实现出stack，下面开始进入stack类的模拟实现。

1.1.stack类初步书写

我们首先需要先把我们自己写的stack定义在一个命名空间里面，避免和std命名空间里面的stack起冲突，因为stack是一个模版类，所以我们应该用模版类的方式来书写这个类，里面的参数我们对照着标准库书写即可，在我们写完外层以后，就是要书写内层了，此时我们先定一个成员变量，它的类型自然就是Container类型（这个类型可以是vector，可以是list，甚至是string），这个成员变量是为了后续数据的增删而写，下面小编给出这部分代码的书写：

代码语言：javascript代码运行次数：0运行复制

namespace wang   //保存在命名空间里面，避免出现名字冲突，防患于未然
{
  template<class T,class Container = std :: vector<T>>  //默认使用的容器是vector，也可以是list，毕竟也有链式栈的存在
      class stack
      {
        private:
          Container s1;  //s1是为了保存数据的，增删还是需要靠它。
      };
}

1.2.入栈函数push()的实现

可能到这里可能很多读者朋友会疑惑我为什么没有书写stack的构造函数，对于对此有疑惑的读者朋友，请好好的去复习一下类和对象的知识，还记着类和对象知识的读者朋友都知道，对于自定义类型的成员变量，编译器是会自己去调用它的构造函数的，如果成员变量没有构造函数的，那么编译器会直接报错，自定义类型需要自己写，当然不写的话系统会调用默认构造函数（默认构造函数有三种，这只是特殊情况之一），所以各位记住这一点，此时s1是vector类型的，它是会自己去调用自己的构造函数的，我们不用瞎操心，下面我们正式堆push()的实现进行讲述。

其实push()函数的实现，我们仅需去复用s1中的接口即可，看看上图stack的构造，我们不难发现此时我们仅需在一个vector类型的尾部插入数据即可，此时我们就可以去调用vector当中的尾插函数即可，根本不用我们自己思考了，所以这就是我前面说stack很好实现的原因，我们仅需套用成员变量的接口即可，这也是我让各位复习一下vector的原因，下面给出代码：

代码语言：javascript代码运行次数：0运行复制

void push(T x)  //此时我们不晓得插入啥类型的元素，这就看我们显示实例化我们想要显示的了
{
    s1.push_back(x);
}

1..出栈函数pop()的模拟实现

和小编上面实现入栈函数一样，对于出栈函数，我们也是仅需套用一下s1的接口即可，通过上图我们可以知道此时的出栈操作，对应着的就是把vector对象的尾部删除，所以我们调用尾删函数即可，下面给出代码：

代码语言：javascript代码运行次数：0运行复制

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

1.4.判空函数empty()的模拟实现

对于判空函数的模拟实现，也和上面的接口类似，了解vector的朋友都知道，vector里面也是有一个叫做empty()的接口的，我们仅需套用这个接口就好了，下面小编给出代码：

代码语言：javascript代码运行次数：0运行复制

bool empty()
{
    return ();
}

1.5.个数函数size()的模拟实现

对于它的模拟实现，我们同样也可以套用vector的相关接口，就可以实现这个个数函数，由于难度不大，不再多说给出代码：

代码语言：javascript代码运行次数：0运行复制

int size()
{
    return s1.size();
}

1.6.栈顶函数top()的模拟实现

对于栈顶函数的模拟实现，我们需要先知道栈顶是vector哪个位置的元素，通过上图便可以轻松的看出来栈顶就是vector对象最后一个位置的元素，此时我们仅需返回尾部元素即可，此时我们可以套用vector中的back接口，这个接口我虽然没讲，它的功能就是返回vector最后一个位置的元素，名字其实就可以知晓了。下面小编给出代码写法：

代码语言：javascript代码运行次数：0运行复制

T top()
{
    return s1.back();
}

以上便就是对于stack的模拟实现，是不是灰常的简单，小编当时在经历完某几个容器的模拟实现之后，这一模拟实现stack，就感到了一阵舒爽，我们仅需疯狂的套用接口就好了，剩下的全靠编译器的调用了，等会queue的讲解也会非常的舒服，不过在讲述queue之前，小编先给各位说一个小的知识点，避免读者朋友踩坑。

2.小警示

对于接下来无论是容器还是适配器的模拟实现，各位读者朋友千万不要让模版的声明和定义分离，我忘记我模版说没说过了，对于模板类型的类和函数，它们的声明和定义是不可以去分离的，这涉及到了分离编译的知识，这部分的知识点小编通过一个图带各位简单的了解下，更为详细的知识我会在模版进阶文章进行讲述，其中的过程通过下图便可以知晓为什么模版的声明和定义是无法分离的。

所以我们在进行模拟实现的时候，直接把声明和定义放在一个头文件即可，这个知识点要牢记，防止一些读者朋友犯迷糊。

.queue的模拟实现

在讲述这个小警示以后，紧接着我们就要开始进入queue的模拟实现了，相信看完前文的stack的模拟实现后，各位应该对于queue的模拟实现也会信心满满，因为queue的接口中设计了一端进一端出，因此此时我们用vector封装的话效率会变的很低，根据以前我们数据机构队列的实现的检验来看，用双链表是一个不错的选择，而恰好我们之前list就是一个典型的双链表结构，所以此时我们就是用list来帮助我们实现queue的模拟实现，下面我们就进入queue的模拟实现。

.1.queue类的初步实现

首先我们需要先完成queue的外部的书写，此时和stack一样，为了防止命名冲突，我们需要把它放置在我们自己的命名空间内，然后完成一个模板类的书写，之后我们再和标准库的queue一样书写模版参量，之后我们在写一个Container类型的对象就好了，把它作为我们的成员变量，通过它实现出队列的增删等操作，下面给出这层外套：

代码语言：javascript代码运行次数：0运行复制

namespace wang
{
    template<class T,class Container = list<T>>
        class queue
        {
          private:
            Container s1;
        };
}

.2.入队列函数push()的模拟实现

对于入队列函数，此时我们需要按照队列的结构来对于list对象接口进行合理使用，此时我们知道入队列是从队尾入，所以此时我们需要用到list里面的尾插接口来帮助我们实现这个功能，下面小编给出这个代码的书写：

代码语言：javascript代码运行次数：0运行复制

void push(T x)
{
    s1.push_back(x);
}

..出队列函数pop()的模拟实现

对于出队列函数，我们依照队列的结构，发现它是从队头进行出队列操作，所以此时我们就要借助list对象的头删函数来帮助我们完成出队列操作，下面小编给出这个代码的书写：

代码语言：javascript代码运行次数：0运行复制

void pop()
{
    s1.poo_front();
}

.4.取队头函数front()的模拟实现

这个函数的功能名字就可以体现出来，此时我们如果想要取出队头，就需要知道是s1的一个我也没讲过的接口，front()接口，它的功能就是取出双链表第一个有效结点的元素，所以它正好就可以取出队头元素，下面给出代码书写：

代码语言：javascript代码运行次数：0运行复制

T front()
{
    return s1.front();
}

.5.取队尾函数back()的模拟实现

这个函数的功能同样通过名字就可以体现出来，此时我们想要取出队尾，就需要知道s1的back()接口，他和vector一样，都是取出最后一个位置的元素，用它便可以取出队尾的元素，下面给出代码：

代码语言：javascript代码运行次数：0运行复制

T back()
{
    return s1.back();
}

.6.判空函数empty()的模拟实现

对于判空函数，无非就是判断队列里面是否为空，无非就是检查成员变量是否为空，此时我们仅需调用list对象的判空函数即可，下面小编给出代码：

代码语言：javascript代码运行次数：0运行复制

bool empty()
{
    return ();
}

.7.个数函数size()的模拟实现

我们如果想要知道队列里面有几个有效元素，直到成员对象里面有几个有效元素即可，此时我们仅需套用它的size()函数即可，下面给出代码：

代码语言：javascript代码运行次数：0运行复制

int size()
{
    return s1.size();
}

以上便就是小编对于queue的模拟实现，此时此刻的你是不是感受到了“套娃”的魅力，对于适配器的模拟实现，我们仅需知道合适的容器就好了，剩下的就是无限的套用，只能说用起来十分的舒适，容器的模拟实现我认为是很复杂的，这就是我到现在都没有书写容器的模拟实现的原因（咳咳其实也是懒的写），下面我把这些代码整合起来来帮助各位知晓一个完整的模拟实现。

4.代码展示

4.1.stack

代码语言：javascript代码运行次数：0运行复制

namespace wang
{
	template<class T,class Container = std :: vector<T>>
	class stack
	{
	public:
		void push(T x)
		{
			s1.push_back(x);
		}
		
		void pop()
		{
			s1.pop_back();
		}

		bool empty()
		{
			return ();
		}

		int size()
		{
			return s1.size();
		}

		T top()
		{
			return s1.back();
		}
	private:
		Container s1;
	};
}

4.2.queue

代码语言：javascript代码运行次数：0运行复制

namespace wang
{
	template<class T,class Comtainer = std :: list<T> >
	class queue
	{
	public:
		void push(T x)
		{
			s1.push_back(x);
		}

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

		int size()
		{
			return s1.size();
		}

		T front()
		{
			return s1.front();
		}

		T back()
		{
			return s1.back();
		}

		bool empty()
		{
			return ();
		}


	private:
		Comtainer s1;
	};
}

`

5.总结

此时此刻小编就完成了栈和队列的模拟实现，是不是很轻松，这直接套用别的容器接口的感觉就是舒服，如果容器的模拟实现也是这样该多好（当然不可能），希望后来的我可以完成各种容器的模拟实现文章的书写，感觉写一篇相关类型的文章可以帮助我更好的成长，如果文章有错误，可以在评论区点出，我会定期的回复读者朋友，那么各位大佬们，我们下一篇文章见啦！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-11-28，如有侵权请联系 cloudcommunity@tencent 删除前往查看c++容器队列函数接口