企业网站建设方式,个人网站网站服务器,狼们求个没封的免费网站,深圳怎么做网络推广软仿1.stack使用
1.1empty 作用#xff1a;判断栈中是否为空 我们看到这里s1初始化的时候是空初始化#xff0c;所以用empty来判断出的就是空的栈 1.2size size的作用就是判断栈中的数据个数 1.3push 与vector,string,list不同的是,stack中没有头插尾插的概念 因为栈有一个原则判断栈中是否为空 我们看到这里s1初始化的时候是空初始化所以用empty来判断出的就是空的栈 1.2size size的作用就是判断栈中的数据个数 1.3push 与vector,string,list不同的是,stack中没有头插尾插的概念 因为栈有一个原则后进先出。也就是他像杯子装水一样限制了我们只能从唯一接口进行数据插入与删除。所以也就自然没有push_back了只有push 通过push我们成功给栈插入了一个1 1.4pop 在pop前栈中有一个1 pop之后栈中的1被删掉了 1.5top 我们按照顺序将1,2,3,4依次插入栈中也就是说4应该是最后进栈的他就是栈顶数据 2.容器适配器 适配器是一种设计模式他的目的是将一个接口转换成客户希望的另一个接口 容器适配器就是将一个容器转换成另外一种容器 egvector/list - stack 1只支持一种容器的写法 这里是使用数组实现栈由于底层锁死了vector所以要改成链表实现栈就很麻烦了底层的都要改动 2支持多种容器的写法 这里面我们就可以将其他各种容器给到模板参数container达到可以切换多种容器的目的 eg m_stackint,listint 3.利用容器适配器实现stack 这里我们直接复用大部分容器中都有的方法来实现栈 注意函数参数和模板参数是类似的只不过函数参数传的是值而模板参数传的是类型 所以我们的其中一种使用就是:my_stackint, vectorint m 不过我们其实需要给container一个默认容器类型就像给函数参数一个缺省值一样。 4.deque 标准库中的栈默认的容器既不是数组也不是链表而是用deque。 vector 优势可以实现数据的随机高效访问 劣势插入删除效率较低扩容会有一定空间浪费 list 优势可以实现高效的随机存储没有空间浪费 劣势不支持下标随机访问 deque结合了数组随机读取的优势和链表插入删除方便的优势但是也带来了一些新的问题 当只需要查找和头尾数据操作的时候deque是可以完美替代vector与list的除了这种情况deque就会比较麻烦了 示意图 vector是一段连续的长空间存储所有数据 list是一个个断开的空间存储一个个数据 deque是由中控数组与存储数组组成的中控数组存储着存储数组的指针负责从一个存储数组跳到另一个存储数组访问存储数组是一大段连续空间存储数据且存储数组的长度是一样的 接下来看看他的迭代器 迭代器由四个指针组成其中三个是一级指针一个是二级指针。 cur指向当前访问到的数据first指向存储数组的首元素位置last指向存储数组的尾元素位置 node指向中控数组中指向当前存储数组的指针 下面是更完整的结构 由于deque的应用场景是头尾的插入删除所以这里主要有两个迭代器分别是start与finish他们分别是指向中控数组的第一个元素的指针与最后一个元素的指针 1遍历 从first的cur开始遍历不涉及存储数组转换就是cur涉及存储数组变化就改变node指针的指向然后根据node指针取得first指针的地址并更新cur再根据存储数组固定的元素个数推断出last的指针地址这样就完成了迭代器的更新。 2尾部插入数据 数据没满直接插入数据并cur 数据满了开一个新的存储数组将数据存在新数组开头更新finish迭代器 3头部插入数据 存储数组满了开一个新的数组把数据存在新数组的结尾更新start迭代器 存储数组没满直接插入然后cur-- 4下标随机访问 i/size求出在第几个存储数组i%size求出在存储数组的第几个位置 插入与删除 他们需要把pos后面的数据跨存储数组移动效率很低 下标随机访问 略低于vector 头尾插入删除 优于vector和list 排序 用vector 5.priority_queue priority_queue是优先级队列他的底层是利用堆来实现的默认大数据优先级更高。 5.1框架搭建 我们还是使用容器适配器来构建该容器 5.2插入 由于底层是堆所以我们的插入是先直接插入到堆尾然后向上调整最后完成一个堆结构插入 5.3删除 堆的删除先把首尾元素值交换然后删除尾元素接着向下调整 向下调整用到了假设法我们先假设左孩子是较大的然后进行判断若实际上右孩子更大则让child。不过要注意进行右孩子的访问前需要确定有右孩子 5.4仿函数使用 我们前面实现的插入删除都是针对大堆的大数据优先级高的那如果我们要针对小堆怎么实现 方法一在类中直接修改代码比较逻辑 方法二使用仿函数 方法一的修改需要改动底层且不适合做成模板方法二可以写成模板改动比较逻辑可以从接口处改动不用动底层 接下来我们实现lessfuc仿函数 其实仿函数就是一个类中重载()运算符然后在这个重载函数中实现函数的功能 由于lessfuc是大的数据优先级高所以我们需要注意向上和向下调整中parent和child数据的位置 这里把parent的数据放在child之前若parentchild则交换数据满足大数据优先 这里再讲解一个仿函数的应用 假设我们有一个date类我们的比较逻辑是指针直接比较但是我们希望的是指针指向的内容大小比较我们就可以写一个仿函数重载运算符实现指向内容的比较然后传仿函数给date类 综上仿函数可以增加一些代码的可变性通过传不同的仿函数实现一个类兼容多种情况
