稀疏数组、队列的概念与实践
目录
一、前言
数据结构包括：线性结构和非线性结构。
1.1 线性结构
- 线性结构是最常见的数据结构，其特点是数据元素与下标之间存在一一对应的关系；
- 线性结构有两种不同的存储结构，即顺序存储结构（数组）和链式存储结构（链表）。顺序存储的的线性表称为顺序表，顺序表中存储的数据在存储空间上是连续的；链式存储的线性表称为链表，链表中的数据在存储空间上不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
- 线性结构常见的有：数组、队列、链表和栈。
1.2 非线性结构
- 非线性结构包括：二维数组、多维数组、广义表、图结构和树结构。
二、稀疏数组的概念与实践
当一个二维数组存在大量无意义的数据时，可以选择稀疏数组来保存该数组。
2.1 实际需求
在五子棋程序的实现中，存在存盘退出和续上盘的功能。
因为该二维数组的默认值是0，因此记录了很多没有意义的数据，故可以使用稀疏数组来保存该数组。
2.2 基本介绍
2.2.1 稀疏数组的处理方式是
- 记录数组有几行、几列，有多少个不同的值；
- 把具有不同值得元素的行列及值记录在一个小规模的数组中，从而实现缩小二维数组的规模。
2.2.2 应用举例
转换过后的数组说明：
- [0]列：表示原二维数组有6行7列，其中有8个数据值不是默认值。
- [1]列：表示原二维数组0行3列位置的数据值是22。其后的数据表示方式与此相似。
2.2.3 代码实现
2.2.3.1 思路分析
- 二维数组 转 稀疏数组的思路
- 遍历 原始的二维数组，得到有效数据的个数 sum
- 根据sum 就可以创建 稀疏数组 sparseArr int[sum + 1] [3]
- 将二维数组的有效数据数据存入到 稀疏数组
- 稀疏数组转原始的二维数组的思路
- 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2 = int [11][11]
- 在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可.
2.2.3.2 code
代码实现：//github.com/goSilver/daydayup/blob/master/datastructure/src/hanshunping/chapter03/SparseArray.java
三、队列的概念及实践
3.1 队列简介
- 队列是一个有序列表，可以用数组或是链表来实现；
- 遵循先入先出的原则；
3.2 数组模拟队列思路
队列是有序的，使用数组机构来模拟队列时，需要对数组作以下声明：
-
maxSize是该队列的最大容量；
-
因为队列的输入、输出分别是从前后两头来处理，因此需要两个变量front及rear来分别记录队列前后端的下标。front代表队列头，随着数据输出而改变；rear代表队列尾，随着数据输入而变化。如下图：
-
当我们将数据存入队列是需要两个步骤：首先判断队列是否已满，若指针rear小于队列的最大容量maxSize-1，则可以存入，否则不可以存入数据；第二步将尾指针往后移一位（rear++）。
-
在取数据的时候需要判断队列是否为空，若front==rear则表示队列为空。
3.2.1 code
3.3 使用数组模拟环形队列优化
对于3.2中的实现，存在一个问题就是数组只能使用一次就不能复用了，这里可以使用一个简单的算法，改进成一个环形的数组。（取模）
思路说明：
- front变量的含义做一个调整：front直接指向队列的第一个元素，front的初始值变为0；
- rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为需要空出一个空间作为约定，rear的初始值为0；
- 当队列满时，条件是(rear + 1) % maxSize = front 【满】；
- 队列为空时，rear == front 【空】；
- 队列中有效的数据个数：(rear + maxSize – front) % maxSize
