C++中stack类和queue类

感谢大佬的光临各位，希望和大家一起进步，望得到你的三连，互三支持，一起进步

数据结构习题_LaNzikinh篮子的博客-CSDN博客

初阶数据结构_LaNzikinh篮子的博客-CSDN博客

收入专栏：C++_LaNzikinh篮子的博客-CSDN博客

其他专栏：c语言基础_LaNzikinh篮子的博客-CSDN博客

个人主页：LaNzikinh-CSDN博客

文章目录

• 前言
• 一.容器适配器
• 二.栈的实现stack
• 三.队列的实现queue
• 四.优先级队列priority_queue（）
• 五.deque（双向队列）
• 总结

  ---

  前言

  前面我们讲解了C++中List，Vector,和string类的使用和底层逻辑，今天我们来利用前3个类，来搭建栈和队列，在讲解前，我们先来引入一个容器适配器的概念

  ---

  一.容器适配器

  适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的，代码设 计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

  ​

  ​

  虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL标准库中stack和queue的底层结构中stack和queue默认使用deque。

  二.栈的实现stack

  接口函数

  1.push()将元素val压入stack中

  2.top()返回栈顶元素的引用

  3.pop()将stack中尾部的元素弹出

  4.size()返回stack中元素的个数

  5.empty()检测stack是否为空

  实现

  我们之前说过，栈他是一种适配器，stack只是对其他容器的接口进行了包装，所以我们从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。

  #include
  namespace yyz
  {
  template
  class stack
  {
  public:
  //不写，用编译器自己的默认构造
  stack() {}
  void push(const T& x) {_c.push_back(x);}
  void pop() {_c.pop_back();}
  T& top() {return _c.back();}
  const T& top()const {return _c.back();}
  size_t size()const {return _c.size();}
  bool empty()const {return _c.empty();}
  private:
  std::vector _c;
  };
  }

  三.队列的实现queue

  接口函数

  队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

  empty：检测队列是否为空

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

  front：返回队头元素的引用

  back：返回队尾元素的引用

  push_back：在队列尾部入队列

  pop_front：在队列头部出队列

  实现

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

  #include 
  namespace yyz
  {
  template
  class queue
  {
  public:
  //用编译器默认的构造函数
  queue() {}
  void push(const T& x) {_c.push_back(x);}
  void pop() {_c.pop_front();}
  T& back() {return _c.back();}
  const T& back()const {return _c.back();}
  T& front() {return _c.front();}
  const T& front()const {return _c.front();}
  size_t size()const {return _c.size();}
  bool empty()const {return _c.empty();}
  private:
  std::list _c;
  };
  }
  

  四.优先级队列priority_queue（）

  优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

  empty()：检测容器是否为空

  size()：返回容器中有效元素个数

  front()：返回容器中第一个元素的引用

  push_back()：在容器尾部插入元素

  pop_back()：删除容器尾部元素

  这里我们的实现是用堆去实现的，堆的本质是数组，所以优先级队列作为适配器，只需要通过对vector进行通用的封装即可   

  ​            

  #include
  template
  class Less
  {
  public:
  	bool operator()(const T& x, const T& y)
  	{
  		return x  y;
  	}
  };
  namespace yyz
  {
  	// 默认是大堆
  	template
  	class priority_queue
  	{
  	public:
  		void AdjustUp(int child)
  		{
  			Compare com;
  			int parent = (child - 1) / 2;
  			while (child > 0)
  			{
  				//if (_con[parent] = n说明孩子不存在，调整到叶子了
  			{
  				// 找出小的那个孩子
  				//if (child + 1  
   
  五.deque（双向队列）
   
   
   
  我们前面说了，栈和队列在STL标准库中stack和queue的底层结构中stack和queue默认使用deque。所以我们这次来看看deque到底是什么
   
   
  ​​
   
   
   
  deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端 进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与 list比较，空间利用率比较高。
   
   
  ​
   
  在标准库里实现的stack和queue
   
   
   
  namespace yyz
  {
  	template
  	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;
  	};
  }
   
   
   
   
  namespace yyz
  {
  	// Containerתstack
  	template
  	class stack
  	{
  	public:
  		void push(const T& x)
  		{
  			_con.push_back(x);
  		}
  		void pop()
  		{
  			_con.pop_back();
  		}
  		const T& top() const
  		{
  			//return _con.func();
  			return _con.back();
  		}
  		size_t size() const
  		{
  			return _con.size();
  		}
  		bool empty() const
  		{
  			return _con.empty();
  		}
  	private:
  		Container _con;
  	};
  }
   
   
   
   
  总结
   
  这次讲解了C++中栈和队列的使用，下次对模板在做一点补充