六、基础数据结构

因为很多的问题都遵循同样的规律,所以引入数据结构。

数据结构是组织数据的结构。用来方便我们的操作。

 

一、栈

  • 后进先出
  • 操作:查询栈顶、弹出栈顶、向顶部压入元素

  

  • stl 的栈:不能在栈为空的时候访问栈顶

二、队列

  • 先进先出
  • 操作:查询队首、弹出队首、向尾部插入元素

   (1)  朴素队列:搞一个数组来保存元素。用 fnt, end 分别记录头指针、尾指针。
     但是,q[fnt] 之前的所有空间都被浪费了!

    

   (2)  循环队列:在 end 超出数组大小之后,把数据溢出到数组的头部

     (但要估算好数组大小,任何时刻队列里的元素总数不能超过 SIZE)

      当前队列的大小为 end - fnt + 1。

    

  • stl 的队列

三、链表

  • 数组是顺序表
  • 链表:不以下标来寻址,而是通过相邻元素之间的联系
  • 链表的存储:

   (1)  指针写法:用 new / delete 来动态分配内存;存放对某个元素的索引时,用指针指过去。

   

   (2)  数组写法:预留一个庞大的 数组作为内存池,然后自己手动分配空间;存放对某个元素的索引时,存储目标元素的内存池下标。

   

  • 简单的链表只需要支持以下几个任务: 查询 key 是否存在 、插入 key 、删除 key 。

四、并查集

  • 并查集 是用来维护不相交集合的数据结构,支持两个操作:

   (1)  ask(x, y) 查询 x,y 是否在同一个集合。

   (2)  union(x, y) 将 x,y 所在的集合合并。

 

 

来源:https://www.cnblogs.com/mianing/p/12747572.html