stack、queue(priority_queue)的模拟实现和deque的简单介绍

stack和queue(priority_queue)

1. 容器适配器

适配器(Adapter):一种用来修饰容器(Containers)或仿函数(Functors)或迭代器(Iterator)接口的东西。

适配器是一种设计模式,该模式将一个类的接口转换成客户希望的另外一个接口。

现实中拿插座来说,一个插座可以适配不同的插头,以适应不同电器的电压或者其他要求。

在这里插入图片描述

STL中的适配器相当于一个插座,以适应不同容器,可以"插入"vector, 也可以插入 list,等等。


虽然stackqueue也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器

例如stack只提供LIFO(先进先出)的概念,对其他容器的接口进行了包装,并没有完全重新创建了一个容器。在STL中,stackqueue默认使用deque,而priority_queue默认使用vector

在这里插入图片描述

类似于listiterator的实现,实际上是更高一层的封装。__list_iterator是对Node*的封装,以支持运算符重载;相对应的,stack是对其Container的封装,以支持LIFO的上下文。

2. stack 的介绍和实现

2.1 stack 的介绍

stack文档介绍

  1. stack 是一种容器适配器,设计用于在具有后进先出操作的上下文中,其删除和插入只能从容器的末尾进行操作。

  2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,元素特定从容器的尾部(即栈顶)被压入和弹出。

  3. stack的底层容器可以是任何标准的容器类模板或者一些特殊设计的容器类。这些容器应该支持如下操作:

    empty()			// 判空操作
    size()  		// 得到元素个数操作
    back()  		// 得到容器尾部元素操作
    push_back()		// 尾插操作
    pop_back()		// 尾删操作
    
  4. 标准容器list,vectordeque均满足这些要求。默认情况下,如果没有为stack指定特定的底层容器,默认使用deque作为底层容器。

在这里插入图片描述

2.2 stack 的实现

stack 有如下成员函数(不包括C++11)

在这里插入图片描述

利用适配器概念进行实现:

#pragma once
#include <deque>

namespace wr
{
  template <class T, class Con = deque<T>>	
  class stack
  {
  public:
    void push(const T &x)
    {
      _con.push_back(x);
    }

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

    T &top()
    {
      return _con.back();
    }

    T &top() const
    {
      return _con.back();
    }

    size_t size()
    {
      return _con.size();
    }

    bool empty()
    {
      return _con.empty();
    }

  private:
    Con _con;	// 底层的容器类对象作为成员变量
  };
}

可以看到,适配器模式下设计的stack十分简洁,相比用C语言实现的stack,完全体现了适配器模式的优势。

总结:从使用者角度来看,不需要知道stack底层使用的是什么容器实现,只需要知道其可以实现对应适合LIFO的操作。无论是STL中的容器,还是自定义类容器,只要拥有对应的接口,就可以作为stack的底层容器。


2. queue的介绍和实现

2.1 queue 的介绍

queue文档介绍

  1. queue 是一种容器适配器,专门用于在FIFO(先进先出)的上下文中操作,其中从容器一端插入元素,另一端提取元素。

  2. queue作为容器适配器实现,用一个底层是特定容器类的封装类来实现,queue提供了特定了成员函数来访问它的元素。元素队尾入队列,从队头出队列。

  3. queue的底层容器可以是标准容器中的一种,或者是经过特别设计的容器类。底层容器应该至少指出如下操作:

    empty()				// 判空操作
    size()				// 得到元素个数操作
    front()				// 得到容器头部元素
    back()				// 得到容器尾部元素
    push_back()			// 容器尾插元素操作
    pop_back()			// 容器头删元素操作
    
  4. STLdequelist可以满足这些需求。默认情况下,如果没有容器类被指定,默认使用deque作为queue的底层容器。

在这里插入图片描述

2.2 queue 的实现

queue有如下成员函数:

在这里插入图片描述

实现如下:

#pragma once

#include <deque>

namespace wr
{
  template <class T, class Con = deque<T>>
  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:
    Con _con;
  };	
}

stack的实现差不多,唯一需要注意的是 queue的底层容器不能是vector,因为vector类根本不支持pop_front()的操作。并且vector的头删效率太低,需要挪动后面的所有元素。

3. priority_queue 的介绍和使用

3.1 priority_queue 的介绍

priority_queue文档介绍

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

  2. 此上下文类似于heap(堆),在这种上下文中,元素可以随时被插入到堆中,并且只有最大的堆元素可以被访问(位于优先队列的top())。

  3. priority_queue被作为容器适配器实现,并将特定容器类封装作为其底层容器类,同时提供了特定的一组成员函数来访问其元素。元素从特定容器的“尾部”弹出,其成为优先队列的顶部。

  4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:

    empty()				// 判空操作
    size()				// 得到元素个数操作
    front()				// 得到容器头部元素
    push_back()			// 容器尾插元素操作
    pop_back()			// 容器头删元素操作
    
  5. STLvectordeque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector

  6. 需要支持随机访问迭代器,一边始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

优先级队列默认使用vector作为其底层的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue

需要注意的是,下面是优先级队列的模板参数,第三个参数默认使用less仿函数,以构造大堆。若指定Comparegreater仿函数,则构成小堆。

在这里插入图片描述

// 默认情况下构造小堆
priority_queue<int> pq1;		
// 相当于
priority_queue<int, vector<int>, less<int>> pq1;

// 指定底层容器构造大堆
priority_queue<int, deque<int>, greater<int>> pq2;

如果需要使用priority_queue存放自定义类元素,需要自行重载><


3.2 priority_queue 的实现

之前已经用C语言实现过堆,C++实现的重点是对STL的使用、仿函数的使用以及适配器模式概念的理解。

数据结构:堆的实现和堆排序及TopK问题

堆的插入元素和删除元素的时间复杂度是O(logN) ,默认情况下优先级队列是大堆,先不考虑使用仿函数去实现大小堆兼容的问题。首先先来实现大堆,最后在代码基础上加上仿函数的设计就可以了。


priority_queuequeue的区别主要是在pushpop上,优先级队列需要进行额外的向上调整向下调整以满足堆序。

push:先将元素尾插到容器,随后将该元素进行向上调整以满足堆序。

pop:直接将容器最后一个元素覆盖堆顶元素,随后对此时的堆顶元素进行向下调整以满足堆序。注意:不能直接将堆顶元素删除,因为不能保证左孩子和右孩子之间也满足堆序,两个孩子之间没有关系,它们只和他们的父亲有关系。

void push(const T &x)
{
	_con.push_back(x);
	adjust_up(_con.size() - 1);
}

void pop()
{
    assert(!_con.empty());
	_con[0] = _con[_con.size() - 1];
	_con.pop_back();
	adjust_down(0);
}

随后就是向上调整和向下调整算法,这里先直接用不等号直接实现大堆。

// 向上调整算法
void adjust_up(int child)
{
  int parent = (child - 1) / 2;
  while (parent >= 0)
  {
    // 默认less,大堆,a[child] > a[parent] 交换
    if (_con[parent] < _con[child])
    {
      swap(_con[parent], _con[child]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

// 向下调整算法
void adjust_down(int parent)
{
  int child = parent * 2 + 1;
  while (child < _con.size())
  {
    // 默认less, 如果_con[child+1] > _con[child], 更新child
    if (child + 1 < _con.size() && _con[child] < _con[child+1])
    {
      child++;
    }

    // 如果_con[parent] < _con[child] 交换
    if (_con[parent] < _con[child])
    {
      swap(_con[parent], _con[child]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

具体实现细节在以前博客,这里不过多赘述。


随后是其他一些简单接口。注意:top()的参数和返回值都是const,保证数据不被修改。

bool empty() const
{
  return _con.empty();
}

size_t size() const
{
  return _con.size();
}

const T &top() const
{
  return _con.front();
}

这是固定死了的大堆,如果要使用小堆,难道需要再写一个类或者在需要时再修改吗?答案显然是否定的。

在C语言阶段,可以用函数指针进行实现,通过对comp()函数的回调实现特定的需求。例如实现bubble_sort()函数时通过传入函数指针来指定比较方法。

//通用冒泡排序
void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(const char*, const char*))

C++中有更好的实现方法,称为仿函数。

3.2.1 仿函数

仿函数就是仿造的函数,它并不是一个真正意义上的函数。它是一个类中的operator()重载,使之它具有类似于函数的功能。

就如仿羊皮一样,仿函数不是函数,而是一个类中的operator()重载,既然在类中,那么就可以使用模板参数,这相比函数指针就更加的范式化。

下面是greater和less的模拟实现

template <class T>
struct greater
{
    // 运算符()重载
    bool operator()(const T &a, const T &b)
    {
      return a > b;
    }
};

template <class T>
struct less
{
    bool operator()(const T &a, const T &b)
    {
      return a < b;
    }
};

使用仿函数就可以构建一个对应的类对象,随后调用operator()即可

less<int> le;
cout << le(100, 200) << endl;

将仿函数类模板放入priority_queue的模板参数列表中,就可以实现在构建优先级队列的时候指定堆序了。因为模板参数传入的是类型,在编译的时候进行传递,随后程序运行都是基于传入模板的参数类型下进行运行的。

下面是引入了仿函数的完整priority_queue完整实现:

template <class T>
class greater
{
public:
    bool operator()(const T &a, const T &b)
    {
      return a > b;
    }
};

template <class T>
class less
{
public:
    bool operator()(const T &a, const T &b)
    {
      return a < b;
    }
};

template <class T, class Con = vector<T>, class Compare = less<T>>
class priority_queue
{
    void adjust_up(int child)
    {
      int parent = (child - 1) / 2;
      while (parent >= 0)
      {
        // 默认less,大堆,a[child] > a[parent] 交换
        if (_comp(_con[parent], _con[child]))
        {
          swap(_con[parent], _con[child]);
          child = parent;
          parent = (child - 1) / 2;
        }
        else
        {
          break;
        }
      }
    }

    void adjust_down(int parent)
    {
      int child = parent * 2 + 1;
      while (child < _con.size())
      {
        // 默认less, 如果_con[child+1] > _con[child], 更新child
        if (child + 1 < _con.size() && _comp(_con[child], _con[child + 1]))
        {
          child++;
        }

        if (_comp(_con[parent], _con[child]))
        {
          swap(_con[parent], _con[child]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
        {
          break;
        }
      }
    }

public:
    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last)
    {
      while (first < last)
      {
        push(*first);
        first++;
      }
    }

    bool empty() const
    {
      return _con.empty();
    }

    size_t size() const
    {
      return _con.size();
    }

    const T &top() const
    {
      return _con.front();
    }

    void push(const T &x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);
    }

    void pop()
    {
      _con[0] = _con[_con.size() - 1];
      _con.pop_back();
      adjust_down(0);
    }

private:
    Con _con;
    Compare _comp;
};

4. deque 的简单介绍

deque 的文档介绍

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

在这里插入图片描述

4.1 deque 的实现原理

deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的。

实际的deque类似于一个动态的二维数组,如下图所示:

在这里插入图片描述

所有的小空间使用一个指针数组map进行管理的,相当于一个中控。

第一块空间的首地址存放在map的中间,第二块空间的首地址在map下一个位置,若需要头插元素,则新创建的空间首地址放在map中第一块空间首地址的前面。


双端队列底层是一段假象的连续空间,实际上是分段连续的,为了维护其“整体连续”以及随机访问的假象,这个任务落在了deque的迭代器身上,因此deque的迭代器设计就比较复杂,如下图所示:

在这里插入图片描述

queueiterator封装了四个指针,分别是cur、first、last、node;

first:当前元素所处缓冲区的开始

last:当前元素所处缓冲区的结束

cur:当前元素值

node:指针的指针,指向map中指向buffer的指针


deque通过迭代器startfinish维护其整体结构:

在这里插入图片描述

deque::begin()返回迭代器startdeque::end()返回迭代器finish,这两个迭代器都是deque的成员变量。

如果要头插元素,而此时迭代器startnode指向为第一个buffer的首地址,则需要创建一个新的buffer空间。node指向map前一个空间,*node指向新buffer的首元素地址,同时更新first、cur、last

4.2 deque 与 vector和 list 的比较

deque的优势就是头插头删,尾插尾删,只有O(1)的时间复杂度。

但由于其复杂的底层结构,导致实现其随机访问(即[])很困难,有以下两点不足,或者说是冲突:

  • 规定deque的每一个buffer的空间一样大(为n),那么访问第i个数据的思路:如果i不是第一个buffer中的数据,则i -= 第一个buffer的长度后,第i个数据的下标为[i/n, i%10]规定deque的每一个buffer不一样大,则需要依次将i减去buffer的长度,直至i小于下一个buffer的长度,才能找到第i个元素对应的位置
  • deque中间插入数据,若需要每个buffer的空间一样大,需要挪动所有该位置前面或者后面的数据。若不需要每个buffer空间一样大,则可以只挪动当前buffer的元素。

由此可以看到,对dequebuffer的长度是否一致的规定会影响随机访问中间插入元素的效率。但无论怎么说,deque的随机访问是始终不如vector的,中间插入元素是始终不如list的。

容器优点缺点
vector物理结构连续存储 1.下标随机访问 2.缓存命中率高1.前面部分插入删除效率低 2.扩容有损耗,还会存在一定程度空间浪费
list物理结构不一定连续 1. 任意位置插入删除效率高 2. 按需申请空间,1.不支持下标随机访问 2.缓存命中率高
deque1.支持下标随机访问 2. 扩容损耗小 3. 头部和尾部对元素处理效率高 4. 缓存命中率高1.中间插入效率低 2.下标随机访问不如vector

本章完。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/567995.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

serverLess

第一步 安装依赖 npm install serverless-devs/s g 第二步 配置秘钥&#xff1a; 第三步 执行终端 执行命令 s config add 选择 alibaba cloud &#xff08;alibaba&#xff09; 把对应的ID secret填写&#xff0c;第三个别名可以随便写&#xff1a; serverLess 查看是…

ClickHouse 高可用之副本

文章目录 ClickHouse 副本支持副本的引擎配置高可用副本副本应用1.副本表概述2.创建副本表3.写入模拟数据4.副本验证 扩展 —— 在 Zookeeper 中查看副本表信息 ClickHouse 副本 ClickHouse 通过副本机制&#xff0c;可以将数据拷贝存储在不同的节点上。这样&#xff0c;如果一…

Redis底层数据结构之Dict

目录 一、概述二、Dict结构三、Dictht结构四、DictEntry结构五、核心特性 上一篇文章 reids底层数据结构之quicklist 一、概述 Redis 的 Dict 是一个高效的键值对映射数据结构&#xff0c;采用双哈希表实现以支持无锁的渐进式 Rehash&#xff0c;确保扩容或缩容时的高效性能。…

linux autogroup

一&#xff1a;概述 对于linux autogroup的作用&#xff0c;很多同学可能是听说过&#xff0c;但&#xff0c;并未验证过。 考虑下面场景&#xff0c;开两个terminal&#xff0c;T1和T2&#xff0c;在T1中运行进程P1&#xff0c;P1开启9个线程编译代码&#xff0c;在T2中运行…

Datawhale ChatGPT基础科普

根据课程GitHub - datawhalechina/hugging-llm: HuggingLLM, Hugging Future. 摘写自己不懂得一些地方&#xff0c;具体可以再到以上项目地址 LM&#xff1a;这是ChatGPT的基石的基石。 Transformer&#xff1a;这是ChatGPT的基石&#xff0c;准确来说它的一部分是基石。 G…

销售经理与员工:如何展开有效的绩效面谈

在当今竞争激烈的商业环境中&#xff0c;销售经理与员工之间的绩效面谈显得尤为重要。有效的绩效面谈不仅能够提升员工的工作积极性&#xff0c;促进团队的整体绩效&#xff0c;还能够加强销售经理与员工之间的沟通与理解&#xff0c;为企业的发展奠定坚实的基础。本文将探讨销…

7.2K star!一个完全免费,可以本地部署的 AI 搜索聚合器。新手可尝试

原文链接&#xff1a;7.2K star&#xff01;一个完全免费&#xff0c;可以本地部署的 AI 搜索聚合器。新手可尝试 ChatGPT 刚上线的时候我用的很少&#xff0c;还是习惯用 Google。主要还是因为不信任&#xff0c;怕它对我胡说八道。 慢慢的&#xff0c;也没有一个明确的时间…

Linux的学习之路:19、进程信号(1)

摘要 今天这张说一下信号的一部分知识 目录 摘要 一、信号 1、生活角度的信号 2、技术应用角度的信号 3、注意 4、用kill -l命令可以察看系统定义的信号列表 5、信号处理常见方式概览 二、产生信号 1、通过终端按键产生信号 2、调用系统函数向进程发信号 3、由软件…

<前端>Electron-builder为公证后的app打更新信息latest.yml

MacOS下&#xff0c;Electron-builder可以很方便的为测试包app打更新信息&#xff08;latest-mac.yml&#xff09;。 但是&#xff0c;正式发布的时候&#xff0c;不可能用测试包app&#xff0c;因为还没有进行公证。如何为公证的app打latest-mac.yml呢。 其实观察latest-mac.y…

FPGA秋招-笔记整理(1)

一、关键路径 关键路径通常是指同步逻辑电路中&#xff0c;组合逻辑时延最大的路径&#xff08;这里我认为还需要加上布线的延迟&#xff09;&#xff0c;也就是说关键路径是对设计性能起决定性影响的时序路径。也就是静态时序报告中WNS&#xff08;Worst Nagative Slack&…

Git 核心概念与实操

这里写目录标题 1 版本回退2 工作区、暂存区、本地仓库、远程仓库 1 版本回退 原文链接&#xff1a;https://www.liaoxuefeng.com/wiki/896043488029600/897013573512192 首先 git log 查看提交记录 在Git中&#xff0c;用 HEAD 表示当前版本 上一个版本就是 HEAD^ &#xff…

Linux-进程间通信:System V消息队列

目录 System V IPC概述标识符与IPC Key System V消息队列创建或打开一个消息队列发送消息接收消息控制消息队列1、IPC_STAT2、IPC_SET3、IPC_RMID 查看系统当前的消息队列代码示例 System V IPC&#xff08;Inter-Process Communication&#xff09;是一组用于在 Unix-like 操作…

【C语言】手撕二叉树

标题&#xff1a;【C语言】手撕二叉树 水墨不写bug 正文开始&#xff1a; 二叉树是一种基本的树形数据结构&#xff0c;对于初学者学习树形结构而言较容易接受。二叉树作为一种数据结构&#xff0c;在单纯存储数据方面没有 顺序表&#xff0c;链表&#xff0c;队列等线性结构…

sklearn 笔记 metrics

1 分类 1.1 accuracy_score 分类准确率得分 在多标签分类中&#xff0c;此函数计算子集准确率&#xff1a;y_pred的标签集必须与 y_true 中的相应标签集完全匹配。 1.1.1 参数 y_true真实&#xff08;正确&#xff09;标签y_pred由分类器返回的预测标签normalize 默认为 Tr…

Linux:Win10平台上,用VMware安装Centos7.x及系统初始化关键的相关配置(分步骤操作,详细,一篇足以)

VMware安装Centos7.x镜像的详细步骤&#xff1a;VMWare安装Centos系统&#xff08;无桌面模式&#xff09; 我这里是为了安装Hadoop集群&#xff0c;所以&#xff0c;以下这些步骤是必须进行的 如果你是学习Linux&#xff0c;可以跳过非必须的那些配置项 我安装的版本是&…

前端实现将二进制文件流,并下载为excel文件

目录 一、关于二进制流二、项目实践三、常见问题及解决 一、关于二进制流 含义&#xff1a;二进制流是一种计算机文件格式&#xff0c;它的数据以二进制形式存储&#xff0c;与文本文件不同。 二进制文件可以包含任意类型的数据&#xff0c;例如&#xff1a;图像、音频、视频…

智慧园区引领产业智慧化:深入探索智慧技术如何点亮园区创新发展之路,构建未来产业生态圈,驱动区域经济持续升级

目录 一、引言 二、智慧园区的内涵与特征 三、智慧技术点亮园区创新发展之路 1、智慧技术推动产业转型升级 2、智慧技术促进新兴产业发展 3、智慧技术提升园区创新能力 四、智慧园区在产业智慧化中的作用与价值 1、优化资源配置&#xff0c;提高经济效益 2、提升服务品…

Kibana安装部署(Linux)

Kibana是Elasticsearch的开源可视化工具&#xff0c;与存储在Elasticsearch中的数据进行交互。 1. 下载软件 这里使用的Elasticsearch的版本是7.12.0&#xff0c;所以kibana选择同样的7.12.0版本。 官网下载地址&#xff1a;https://www.elastic.co/cn/downloads/past-releas…

【全网首发】Mogdb 5.0.6新特性:CM双网卡生产落地方案

在写这篇文章的时候&#xff0c;刚刚加班结束&#xff0c;顺手写了这篇文章。 前言 某大型全国性行业核心系统数据库需要A、B两个物理隔离的双网卡架构方案&#xff0c;已成为行业标准。而最新发布的MogDB 5.0.6的CM新增支持流复制双网段部署&#xff0c;用于网卡级高可用容灾(…

Meta 向第三方开放 MR 操作系统;黄仁勋:人形机器人成本可能比人们预期要低得多丨 RTE 开发者日报 Vol.190

开发者朋友们大家好&#xff1a; 这里是「RTE 开发者日报」&#xff0c;每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享 RTE&#xff08;Real Time Engagement&#xff09; 领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有…