1.线性结构和非线性结构

数据结构包括：线性结构和非线性结构
线性结构特点：元素之间存在一对一的线性关系
线性结构中有两种不同的存储方式：顺序存储和链式存储，顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的（地址）（有数组、队列、栈）
链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。（有链表、队列）
线性结构常见有：数组、队列、链表和栈

非线性表结构：二维数组、多维数组、广义表、树结构、图结构

2.稀疏数组的应用场景

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
1)记录数组一共有几行几列，有多少个不同的值
2)把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

稀疏数组和队列： 五子棋棋盘 稀疏数组实现
//原始数组
console.log(‘原始数组’)
var_arr=new_Array(); //先声明一维
for (var_i=0; i<11; i++) { //一维长度为11
arr[i] =new_Array(); //再声明二维
for (var_j=0; j<11; j++) { //二维长度为11
arr[i][j] =0; // 赋值，每个数组元素的值为i+j
}
}
//有棋子时的坐标
arr[1][2] =1
arr[2][3] =2
arr[5][6] =2
console.log(arr)
//有几个有效数字
_let_sum=0
for (_let_i=0; i for (_let_j=0; j if(arr[i][j] !=0){
sum++
}
}
}
console.log(‘sum = ‘+sum)
//创建对应的稀疏数组
console.log(‘稀疏数组’)
_var_arr2=new_Array(); //先声明一维
for (var_i=0; i arr2[i] =new_Array(); //再声明二维
for (var_j=0; j<3; j++) { //一共3列
arr2[0][0] =11;
arr2[0][1] =11;
arr2[0][2] =sum;
}
}
_let_count=0//行数
for (_let_i=0; i<11; i++) {
for (_let_j=0; j<11; j++) {
if(arr[i][j] !=0){
count++
arr2[count][0] =i
arr2[count][1] =j
arr2[count][2] =arr[i][j]
}
}
}
console.log(arr2)
//将稀疏数组恢复为原始数组
console.log(‘将稀疏数组恢复为原始数组’)
_const_arr3=new_Array()
for (let_i=0; i arr3[i] =new_Array()
for (_let_j=0; j arr3[i][j] =0//让数组中的其他值为0
for (_let_z=1; z if( i==arr2[z][0] &&j==arr2[z][1]){
arr3[i][j] =arr2[z][2]
}
}
}
}
console.log(arr3)

3.数组实现队列

Ø队列是一个有序列表，可以用数组或是链表来实现。
Ø遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
Ø则队列数组的声明如下图, 其中 maxSize是该队列的最大容量。
Ø因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示:
Ø当我们将数据存入队列时称为”addQueue”，addQueue的处理需要有两个步骤：思路分析
1)将尾指针往后移：rear+1 , 当front == rear 【空】
2)若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear == maxSize - 1[队列满]
但是目前数组使用一次就不能用了，在取出数据之后就不能存数据了，没有达到复用的效果。 所以可以用循环队列来实现复用