二、稀疏数组与队列，数组模拟队列，模拟环形队列

前言

数据结构学习的第一节便是 稀疏数组和队列。

一、稀疏数组

1.1 实际需求

• 编写的五子棋程序中，有存盘退出和续上盘的功能。
• 实现该功能可以使用二维数组进行存储棋盘，黑子为1，蓝子为2，如图所示：
  
• 但是该二维数组的很多值是默认值0, 因此记录了很多没有意义的数据.->`因此使用稀疏数组，来替代 二维数组。

1.2 基本介绍

• 当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
• 稀疏数组的处理方法是:

1、 记录数组一共有几行几列，有多少个不同的值；
2、 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模；

• 如图所示：
  

1.3 应用实例

1、 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)；
2、 把稀疏数组存盘，并且可以从新恢复原来的二维数组数；
3、 整体思路分析，如图所示：；

4、 稀疏数组记录着二维数组的数据位置稀疏数组的第一行的三列分别代表着二维数组的几行、几列、总共几个数据下面的数据储存的是二维数组的第几行、第几列、为何数；
5、 代码分析逻辑日下：；

> 二维数组 转 稀疏数组的思路 > > 1. 遍历 原始的二维数组，得到有效数据的个数 sum > 2. 根据sum 就可以创建 稀疏数组 sparseArr int[sum + 1] [3]