【C++进阶(六)】STL大法--栈和队列深度剖析&优先级队列&适配器原理

💓博主CSDN主页:杭电码农-NEO💓

⏩专栏分类:C++从入门到精通⏪

🚚代码仓库:NEO的学习日记🚚

🌹关注我🫵带你学习C++

  🔝🔝

栈和队列

• 1. 前言
• 2. 栈和队列的接口函数熟悉
• 3. 适配器介绍
• 4. 栈和队列的模拟实现
• 5. deque的简单介绍
• 6. 优先级队列深度剖析
• 7. 优先级队列的模拟实现
• 8. 总结以及拓展

  1. 前言

  和C语言学习期间的学习顺序一样

  顺序表,链表过了就是栈和队列

  但是栈和队列非常特殊,它的内部结构

  并不是靠自己实现的,而是一种适配器模式

  本章重点:

  本篇文章着重讲解适配器原理

  和栈,队列的接口函数熟悉以及模拟实现

  适配器里有一个特殊容器:deque

  最后讲解优先级队列相关知识和实现

  

  

  ---

  2. 栈和队列的接口函数熟悉

  栈的接口函数熟悉:

  

  由于栈结构只能支持栈顶插入,栈顶pop

  所以它的接口很少,这里就不多介绍了!

  队列的接口函数熟悉:

  

  队列只比栈多了一个接口:back

  队列的front相当于栈的top

  在了解了接口函数后,可以尝试做几个题巩固

  1. 最小栈
  2. 栈的压入,弹出序列
  3. 逆波兰表达式求值
  4. 用两个栈实现队列

  ---

  3. 适配器介绍

  先看栈和队列的类模板:

  

  我们发现第二个模板参数是:Container

  并且它还有缺省值为 deque

  这里就直接引出一个概念: 适配器

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

  一个比较经典的例子就是插头的适配器:

  

  那么在数据结构栈中,这种适配器是什么呢?

  很显然,在C语言阶段实现栈时,我们

  使用的底层是顺序表来实现,也就是

  把顺序表做了一层封装和限制,让它

  的功能变得和栈一样,C++这里也是一样!

  我们在实现栈时不用再去写一个顺序表

  而是直接调用库中的vector!

  ---

  4. 栈和队列的模拟实现

  栈的模拟实现要复用其他数据结构

  所以在定义模板时要定义两个!

  template
  class Stack
  {
  	//......
  private:
  	Container _con;
  }
  

  我们和库中的缺省值保持一致,使用deque

  这个容器我们后面会有所解释!

  这样使用栈非常的方便!因为此时的栈

  就像"富二代"一样,不用写构造和析构函数

  因为默认生成的构造或析构会去调用

  内嵌类型的构造或析构帮助我们完成任务!

  在此之后,只需要实现一些接口函数即可!

  void push(const T& val)
  {
  	_con.push_back(val);
  }
  void pop()
  {
  	_con.pop_back();
  }
  T& top()//可读可写
  {
  	return _con.back();
  }
  const T& top() const
  {
  	return _con.back();
  }
  bool empty() const
  {
  	return _con.empty();
  }
  size_t size() const
  {
  	return _con.size();
  }
  

  注:函数中的push_back或back等

  函数接口是调用适配器中的!如vector中的

  栈的结构实现完成,队列就交给你们了!

  ---

  5. deque的简单介绍

  deque也是一个STL库中的容器

  先来看看它的介绍:

  

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

  

  接下来看看它的接口函数:

  

  deque既有头插头删也有尾插尾删

  这是意料之中,它也支持方括号[]

  其实对于deque的了解到这里就差不多了

  下面的内容属于拓展了解,有兴趣的可以看看

  deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

  

  deque扩容是直接另外开辟一份空间

  再让中控数组指向新开辟的空间

  再将原先空间的内容拷贝至新空间

  注意它有一个中控数组的概念!

  ---

  6. 优先级队列深度剖析

  优先级队列的英文是: priority_queue

  它也是一个容量适配器,文档的大致翻译:

  

  

  优先级队列默认是大堆!

  

  并且它的底层适配器默认是vector

  优先级队列默认有三个类模板,然而第三个

  模板就是决定此优先级队列是大堆还是小堆

  它叫仿函数,我们先不管它,下一篇文章回讲解

  我们需要了解的是,默认的less是大堆

  我们显示传参greater时是小堆!

  优先级队列的接口函数熟悉:

  

  注:如果你想使用小堆,就要将前两个

  模板参数实例化后才能实例化第三个

  当less变成greater时,就是小堆

  ---

  7. 优先级队列的模拟实现

  在学习仿函数之前,先实现无仿函数版本:

  基本结构和框架:

  template
  class Priority_queue
  {
  public:
  	//成员函数
  private:
  	Container _con;//此容器可能是vector可能是deque
  };
  

  由于优先级队列是"富二代",所以

  构造,析构和拷贝构造都可以忽略不写

  优先级队列的插入和删除操作:

  由于优先级队列实际上就是个堆

  所以在插入,删除之后.都需要做一件事

  那就是向上调整或向下调整!所以插入和

  删除的关键其实就在于向上/下调整!

  向上调整:

  void AdjustUp(int* a, int child)
  {
  	int parent = (child - 1) / 2;
  	while (child > 0)
  	{
  		if (a[child] > a[parent])
  		{
  			swap(&a[child], &a[parent]);
  			child = parent;
  			parent = (child - 1) / 2;
  		}
  		else
  		{
  			break;
  		}
  	}
  }
  

  向下调整:

  void AdjustDown(int* a, int n, int parent)
  {
  	int child = parent * 2 + 1;
  	while (child  
  这两个操作在学习堆时就已经实现过了,老朋友了
   
  详情可看: 堆以及topk问题
   
  优先级队列的插入和删除
   
  void push(const T& val)//堆的插入
  {
  	_con.push_back(val);
  	adjust_up(_con.size() - 1);
  }
  void pop()//堆的删除
  {
  	std::swap(_con[0], _con[_con.size() - 1]);
  	_con.pop_back();
  	adjust_down(0);
  }
   
   
   
  插入和删除可谓是和堆的做法一模一样
  其他的函数接口也是如此,这里就不多解读
  我把优先级队列模拟实现的所有代码分享出来:
   
   
  优先级队列模拟实现全部代码
   
  8. 总结以及拓展
   
  其实我们可以感受到,有了前面STL
  容器的学习,现在学习栈和队列要轻松许多
  不仅是模拟实现上可以复用以前的容器
  连使用方法和函数接口都和之前一样
  这就是C++STL的魅力所在!
   
  拓展阅读:
  对于deque我们还有很多未知的地方
  比如它的扩容是怎样完成的?是否是缩容?
  deque是如何支持随机访问的?deque的缺陷?
   
  有兴趣的老铁可以阅读下面这篇文章:
   
  deque深度剖析
   
   
  
    🔎 
    下期预告:模板进阶以及仿函数 🔍