STL之stack+queue的使用及其实现

STL之stack+queue的使用及其实现

• 1. stack，queue的介绍与使用
• • 1.1stack的介绍
  • 1.2stack的使用
  • 1.3queue的介绍
  • 1.4queue的使用
  • 2.stack，queue的模拟实现
  • • 2.1stack的模拟是实现
    • 2.2queue的模拟实现
    • 3.总结

      所属专栏：C“嘎嘎" 系统学习❤️

      🚀 >博主首页：初阳785❤️

      🚀 >代码托管：chuyang785❤️

      🚀 >感谢大家的支持，您的点赞和关注是对我最大的支持！！！❤️

      🚀 >博主也会更加的努力，创作出更优质的博文！！❤️

      1. stack，queue的介绍与使用

      1.1stack的介绍

      stack的文档介绍

      1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行

         元素的插入与提取操作。

      2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定

         的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

      3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下

         操作：

         empty：判空操作

         back：获取尾部元素操作

         push_back：尾部插入元素操作

         pop_back：尾部删除元素操作

      4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，

         默认情况下使用deque。

      1.2stack的使用

      函数说明	接口说明
      stack()	构造空的栈
      empty()	检测stack是否为空
      size()	返回stack中元素的个数
      top()	返回栈顶元素的引用
      push()	将元素val压入stack中
      pop()	将stack中尾部的元素弹出

      1.3queue的介绍

      queue的文档介绍

      1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端

         提取元素。

      2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的

         成员函数来访问其元素。元素从队尾入队列，从队头出队列。

      3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操

         作:

         empty：检测队列是否为空

         size：返回队列中有效元素的个数

         front：返回队头元素的引用

         back：返回队尾元素的引用

         push_back：在队列尾部入队列

         pop_front：在队列头部出队列

      4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标

         准容器deque。

      1.4queue的使用

      函数声明	接口说明
      queue()	构造空的队列
      empty()	检测队列是否为空，是返回true，否则返回false
      size()	返回队列中有效元素的个数
      front()	返回队头元素的引用
      back()	返回队尾元素的引用
      push()	在队尾将元素val入队列
      pop()	将队头元素出队列

      2.stack，queue的模拟实现

      适配器:

      适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总

      结)，该种模式是将一个类的接口转换成客户希望的另外一个接口

      

      用简单话来概括适配器就是——用现有的东西适配出一个新的东西。

      2.1stack的模拟是实现

      • 补充知识点：

        我们知道函数传参的时候是可以有缺省参数并给定默认参数值的，所以我们的类模板参数同样是可以的。

      • 既然是利用现有的东西适配出一个新的东西，用来适配的STL就需要可以满足被适配出来的所属功能。这里stack栈要实现的是fist in last out先进后出的功能，也就是push_back和pop_back这两个主要的功能，所以只要可以满足这两个主要的功能，基本上可以用来适配出stack容器了。
      • 既然是适配，我们的类模板参数就需要传递一个STL容器的类型过来，用来适配，所以就需要一个Container参数类型用来接收用来适配的容器的类型，并在内用这个类型创建对象，并用这个对象来实现所需要的功能。
      • 这里用到的默认适配器是deque双端队列，这个在后期的章节会进行讲解，这里就简单的理解一下，deque是兼容了vector和list的所用功能，可以理解是vector和list的结合体。

        #pragma once
        #include 
        namespace qfw
        {
        	template
        	class stack
        	{
        	public:
        		void push(const T& x)
        		{
        			_con.push_back(x);
        		}
        		void pop()
        		{
        			_con.pop_back();
        		}
        		T& top()
        		{
        			return _con.back();
        		}
        		const T& top() const
        		{
        			return _con.back();
        		}
        		size_t size() const
        		{
        			return _con.size();
        		}
        		bool empty() const
        		{
        			return _con.empty();
        		}
        	private:
        		Container _con;
        	};
        }
        

        2.2queue的模拟实现

        #pragma once
        #include 
        namespace qfw
        {
        	template 
        	class queue
        	{
        	public:
        		void push(const T& x)
        		{
        			_con.push_back(x);
        		}
        		void pop()
        		{
        			_con.pop_front();
        		}
        		T& back()
        		{
        			return _con.back();
        		}
        		const T& back()const
        		{
        			return _con.back();
        		}
        		T& front()
        		{
        			return _con.front();
        		}
        		const T& front() const
        		{
        			return _con.front();
        		}
        		size_t size() const
        		{
        			return _con.size();
        		}
        		bool empty() const
        		{
        			return  _con.empty();
        		}
        	private:
        		Container _con;
        	};
        }
        

        3.总结

        1. 本章节的主要核心点是适配器的使用，有了适配器大大代码的冗余性，大大提高了代码的复用性，并且使得我们的代码结构变得多样性。只要使用的适配器可以满足我们所需要的功能就可以进行适配。比如stack我们不仅可以用deque进行适配，也可以用vector和list进行适配，不同的适配器，使用不同的结构，但是都可以得到我们想要的结果，当然这是在有类模板的前提下。
        2. 所以其实绕个弯过来核心还是模板的使用，模板的使用让代码程序变得更加的灵活多变，减少了很多程序员的代码成本，但是编译器底层还是会将模板展开并进行一次类型匹配，也就是将原本我们的工作量交给了编译器帮我们做了。