稀疏(sparse array)数组

压缩数组

当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组的处理方法是：

• 记录数组
• 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

队列

• 队列是一个有序列表，可以用数组或是链表来实现。
• 遵循先入先出的原则。

环形队列

通过取模的方法来实现

• 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的时候要注意

  • (tail+1)%maxSize == head满

• 分析思路

  • 1、 什么时候表示队列满 (tail + 1) % maxSize = head
  • 2、tail==head表示空
  • 3、初始化时，tail=0 head=0
  • 4、怎么统计该队列有多少个元素(tail + maxSize - head)%maxSize

• 链表

可以利用链表做一个内存数据库

链表是一个有序的列表

• 单链表

单链表 一般来说 为了比较好的对单链表进行增删改查的操作，我们都会给他设置一个头结点，头结点的作用主要是用来标识链表头，本身这个结点不存放数据。

• 双向链表

• 选择排序

• 插入排序

把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素， 把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

• 快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小， 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。