稀疏数组和队列
一、稀疏数组
1、稀疏数组实际需求
编写一个五子棋程序，有存盘退出和续上盘的功能。
分析问题：因为这个二维数组中很多的默认值都是0，因此记录了很多没有意义的数据，这时就可以用到稀疏数组
2、稀疏数组基本介绍
当一个数组中大部分元素都是0，或者都是同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是：
1. 稀疏数组的第一行是 记录数组一共有几行几列（这里不是索引，从1开始），有多少个不同的值
2. 把具有不同值得元素的行列及值记录在一个小规模的数组（稀疏数组）中，从而缩小程序的规模 --->
3. -------------------->原来的二维数组是42个值，使用稀疏数组后变成27个值（节省了很大空间）
4. 稀疏数组 永远是一个 行不确定（有效值的数量+1 = 真实行数），但是就三个列(行，列，值)的一个二维数组
5. 稀疏数组第二行及以下 都是存放原始二维数组中 有效值的坐标（行和列分别是 下标[索引]）
3、稀疏数组的应用实例
1. 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
2. 把稀疏数组存盘，并且可以从新恢复原来的二维数组数
3. 整体思路分析
4、二维数组转稀疏数组的思路：
• 遍历原始的二维数组，得到要保存的有效的数据的个数 sum。
• 根据sum就可以创建稀疏数组 sparseArray，
• 创建稀疏数组： 行是有效数据+1，列永远是3 || int[][] sparseArray = new int[sum+1][3] ;
• 将二维数组的 有效数据的 坐标 和 值 存入到稀疏数组中
4、稀疏数组转原始的二维数组的思路：
• 读取到稀疏数组的第一行，读到这个原始二维数组 有几行 几列，几个有效值
• 根据第一行的数据创建原始二维数组，int[][] chessArray = new int[行][列];
• 在读取稀疏数组后几行的数据，并赋给这个原始的二维数组，【根据下标赋值】
二、稀疏数组代码实现
1、原始二维数组转换稀疏数组
//创建原始二维数组
int[][] chessArray = new int[11][11];
//给里面赋值，这个里面就是一个棋盘，有两个棋子
chessArray[1][2] = 1;
chessArray[2][3] = 2;
//查看棋盘
for (int[] ints : chessArray) {
for (int anInt : ints) {
System.out.print(anInt + "\t");
}
System.out.println("\n");
}
//现在将这个原始二维数组转换成 稀疏数组
//1.先遍历数组，找到有多少有效数据【非0的数据】
//sum：有效值数量
int sum = 0;
for (int[] ints : chessArray) {
for (int anInt : ints) {
if (anInt != 0){
sum ++;
}
}
}
System.out.println("有效数据共有：" + sum + "个");
//得到原始二维数组的行和列
int hang = chessArray.length;
int lie = chessArray[0].length;
//2.创建稀疏数组
//稀疏数组的行永远是 有效数据的数量+1 ， 列永远是 3
int[][] sparseArray = new int[sum + 1][3];
//3.给稀疏数组里面添加数据
//分别是 原始二维数组的 行数，列数，有效数据有几个
sparseArray[0][0] = hang;
sparseArray[0][1] = lie;
sparseArray[0][2] = sum;
//4.把原始二维数组里面的数据坐标 及 数据放到 稀疏数组里面
//定义一个计数器,用来做稀疏数组的下标使用
int count = 0;
for (int i = 0; i < chessArray.length; i++){
for (int j = 0; j < chessArray[i].length; j++){
//如果原始二维数组里面的数据不为0，表示可以放到稀疏数组里面
if (chessArray[i][j] != 0){
count++;
// 把原始数据的行 放到 稀疏数组
sparseArray[count][0] = i;
//列
sparseArray[count][1] = j;
//有效数据
sparseArray[count][2] = chessArray[i][j];
}
}
}
//查看稀疏数组
for (int[] ints : sparseArray) {
for (int anInt : ints) {
System.out.print(anInt + "\t");
}
System.out.println();
}
2、稀疏数组转二维数组
//先获得一个稀疏数组
int[][] sparseArray = new int[3][3];
sparseArray[0][0] = 11;
sparseArray[0][1] = 11;
sparseArray[0][2] = 2;
sparseArray[1][0] = 1;
sparseArray[1][1] = 2;
sparseArray[1][2] = 1;
sparseArray[2][0] = 2;
sparseArray[2][1] = 3;
sparseArray[2][2] = 2;
//1.读取稀疏数组第一行，得到原始数组的行和列，并创建原始数组
int hang = sparseArray[0][0];
int lie = sparseArray[0][1];
int[][] chessArray = new int[hang][lie];
//2.把稀疏数组里面的值拿出来 给原始二维数组赋上
for (int i = 1; i < sparseArray.length; i++){
//稀疏数组里面第二行 前两列都是 值得下标，
chessArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
for (int[] ints : chessArray) {
for (int anInt : ints) {
System.out.print(anInt + "\t");
}
System.out.println();
}
三、队列
1、队列是使用场景
• 例如 银行排队叫号
• 先进先出，后进后出
2、队列介绍
1. 队列是一个有序列表，可以用数组或者是链表来实现
2. 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
3. 示意图：(使用数组模拟队列示意图) ----------->
4. 队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
5. 队列是一种先进先出（first in first out） 的线性表，简称 fifo，允许插入的那一端为队尾，允许删除的那一段叫对头
3、数组模拟队列
• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
• 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 头 及 rear 尾 分别记录队列前后端的下标， front 会随着数据输出而改变[取]，而 rear 则是随着数据输入而改变[加]，如图所示:
当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析
1. 将尾指针往后移：rear+1, 当 front == rear 【空】 【头和尾相同时，表示此队列为空】
2. 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。 rear ==maxSize-1[队列满] 【尾== 数组.length-1 说明队列满了】
4、普通队列出现的问题：
1. 普通队列的缺点： 该队列只能使用一次【不能重复使用】，front 【头部下标】不会回溯，而要解决这个问题就需要使用到 环形队列
2. 将原来的数组，使用一个算法，变成环形队列。 使用取模的方式：%
5、数组模拟环形队列思路分析：
1. front 【头部】变量做一个调整：front就指向队列的第一个元素下标， 之前是指向-1，现在是指向0， 也就是说 arr[front] == 队列中的第一个元素 【front的初始值是 0 】
2. rear 【尾部】变量做一个调整：rear就指向队列中的最后一个元素的后一个位置下标，因为希望空出一个空间做约定 【rear的初始值是 0】
3. 能储存的数据量是 长度 - 1 ， 因为rear 要预留一个空的
4. 当队列满时的条件是， (rear + 1) % maxSize == front 【true 则满】
• 代数： maxSize 是 4， 长度是4，下标为 0，1，2，3 因为rear要预留出一个空间，所以按照上面的 最后一个元素的后一个位置下标 只能是 3 【下标为2 的后面一个元素的下标】
• rear因为是指向最后一个元素的后面那个位置的下标，rear指向下标为2的元素的后面那个位置的下标，所以是3
• 带入条件 (3 + 1) % 4 == 0; 如果当前这个环形列队中的头部变量是 0 则表示此队列满了
5. 当队列为空的条件， rear == front 【true 则空】
6. 按照上面分析的话，队列中有效的数据的个数是 ：(rear + maxSize - front) % maxSize
• 代数：如果 rear = 1，则表示在队列中下标为 0 的位置有1个 数据【为什么是rear = 1，因为他指向最后一个元素的后一个位置的下标】
• (1 + 3 - 0) % 3 = 1 所以等于1
四、队列代码实现
1、普通队列代码实现
//此类为队列
public class ArrayQueue {
private int maxSize; //队列最大容量
private int front; //队列头部下标 最初是指向 -1
private int rear; //队列尾部下标 没有元素则是指向 -1
private int[] arrayQueue; //队列
//通过构造方法 来指定队列的长度，并且初始化一些成员变量
public ArrayQueue(int maxSize){
this.maxSize = maxSize;
front = -1;
rear = -1;
arrayQueue = new int[maxSize]; //创建指定大小的数组【队列】
}
//判断此队列是不是为空的方法
public boolean isEmpty(){
//如果头部下标 == 尾部下标 则表示队列中没有数据，为空
return front == rear;
}
//判断队列是否已满的方法
public boolean isFull(){
//如果尾部下标 == 数组.length - 1 则表示队列满了
return rear == maxSize - 1;
}
//往队列里面放数据的方法
public void addQueue(int n){
if (isFull()){
throw new RuntimeException("队列已满，无法加入数据");
}
//存数据从尾部存，后存后出
rear ++; //最初是指向-1的，每添加一次数据时 自增1
arrayQueue[rear] = n;
}
//从队列里面取出数据
public int getQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空，没有数据可取");
}
front ++; //取数据是往头部取，先进先出
return arrayQueue[front];
}
//查看队列全部元素
public void showQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空，没有数据展示");
}
for (int i = 0; i < maxSize; i++){
System.out.println("arr["+ i +"]:" + arrayQueue[i] + "\n");
}
}
//显示队列头部数据
public int headQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空，没有数据展示");
}
return arrayQueue[front+1];
}
}
// -------------------------------------------------------测试
public class ArrayQueueTest {
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(3);
boolean loop = true;
Scanner scanner = new Scanner(System.in);
while (loop){
System.out.println("-------------------------------->");
System.out.println("s 查看队列中所有元素");
System.out.println("a 向队列中添加一个元素");
System.out.println("g 向队列中得到一个元素");
System.out.println("h 得到队列中的头部元素");
System.out.println("e 退出循环");
String next = scanner.next();
switch (next){
case "s":
try{
queue.showQueue();
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case "a":
try{
queue.addQueue(scanner.nextInt());
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case "g":
try{
int queue1 = queue.getQueue();
System.out.println("得到的元素是： " + queue1);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case "h":
try{
int queue1 = queue.headQueue();
System.out.println("头部的元素是： " + queue1);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case "e":
scanner.close();
loop = false;
break;
}
}
System.out.println("退出成功");
}
}
2、环形列队代码实现
public class CircleQueue {
private int maxSize; //队列最大容量
private int front; //队列头部下标 最初是指向 0
private int rear; //队列尾部下标 没有元素则是指向 0
private int[] arrayQueue; //队列
//通过构造方法 来指定队列的长度，并且初始化一些成员变量
public CircleQueue(int maxSize){
this.maxSize = maxSize;
arrayQueue = new int[maxSize]; //创建指定大小的数组【队列】
}
//判断此队列是不是为空的方法
public boolean isEmpty(){
//如果头部下标 == 尾部下标 则表示队列中没有数据，为空
return front == rear;
}
//判断队列是否已满的方法
public boolean isFull(){
//如果尾部下标 == 数组.length - 1 则表示队列满了
return (rear + 1) % maxSize == front ;
}
//往队列里面放数据的方法
public void addQueue(int n){
if (isFull()){
throw new RuntimeException("队列已满，无法加入数据");
}
//直接上数据放到 尾部
arrayQueue[rear] = n;
//将rear后移，因为要考虑到 如果rear在最后面位置的话，可能要往头部放
rear = (rear + 1) % maxSize;
}
//从队列里面取出数据
public int getQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空，没有数据可取");
}
// 这里需要分析出 front 是指向队列的第一个元素
// 1. 先把 front 对应的值保留到一个临时变量
// 2. 将 front 后移, 考虑取模
// 3. 将临时保存的变量返回
int value = arrayQueue[front];
front = (front + 1)%maxSize;
return value;
}
//查看队列全部元素
public void showQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，没有数据展示");
}
// 思路：从 front 开始遍历，遍历多少个元素
// 动脑筋
for (int i = front; i < front + size(); i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arrayQueue[i % maxSize]);
}
}
//求出当前队列的有效数据
public int size(){
return (rear + maxSize - front) % maxSize;
}
//显示队列头部数据
public int headQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空，没有数据展示");
}
return arrayQueue[front];
}
}
//-------------------------------------------------------------------测试
下面为测试上面的那个队列
public class CircleQueueTest {
public static void main(String[] args) {
CircleQueue queue = new CircleQueue(3);
boolean loop = true;
Scanner scanner = new Scanner(System.in);
while (loop){
System.out.println("-------------------------------->");
System.out.println("s 查看队列中所有元素");
System.out.println("a 向队列中添加一个元素");
System.out.println("g 向队列中得到一个元素");
System.out.println("h 得到队列中的头部元素");
System.out.println("e 退出循环");
String next = scanner.next();
switch (next){
case "s":
try{
queue.showQueue();
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case "a":
try{
queue.addQueue(scanner.nextInt());
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case "g":
try{
int queue1 = queue.getQueue();
System.out.println("得到的元素是： " + queue1);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case "h":
try{
int queue1 = queue.headQueue();
System.out.println("头部的元素是： " + queue1);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case "e":
scanner.close();
loop = false;
break;
}
}
System.out.println("退出成功");
}
}