数据结构（还在学习，博客是自己的笔记整理思路用的）

数据结构分为两种

一种是线性结构一种是非线性结构

线性结构的特点是数据元素存在一对一的线性关系线性结构有两种不同的存储结构，即顺序存储和链式存储顺序存储里线性表叫顺序表，顺序表中的存储单元是连续的，链式存储的叫链式表，链式表存储单元不是一定是连续，在一个元素节点中存储元素和相邻元素的地址信息。常见的线性结构有数组队列链表栈

稀疏数组记录数组一共有几行几列表,有多少个不同值应用场景当一个二维数组里面有大量重复的数据时。

创建一个新的二维数组第一行第一列存储原来二维数组的多少行多少列多少个有效值

普通的二维数组转化成稀疏数组的思路
1 遍历原先的二维数组得到有效的个数 sum
2 根据sum 来创建稀疏数组
3 将二维数据的有效数据存入稀疏数组中

int[][]  arry=new int[11][11];//初始化一个二维数组  1 表示黑子; 2 表示白色子 其他数都是零 
arry[1][2]=1;//第二行第三列一个黑子
arry[2][3]=2;//第三行第四列一个白子
arry[5][7]=2;


//打印这个数组
for (int i = 0; i <arry.length ; i++) {
    for (int j = 0; j <arry[i].length ; j++) {
        System.out.print("\t"+arry[i][j]);
    }
    System.out.println();
}

//得到有效数的个数---不是零的数
int sum=0;
for (int i = 0; i <arry.length ; i++) {
    for (int j = 0; j <arry[i].length ; j++) {
        if (!(arry[i][j]==0)){//计数器方法 如果是有效数就加一 最终得到有效数的个数
            sum++;
        }
    }
}
System.out.println("有效数: "+sum);

//生成稀疏数组
int sparse[][]=new int[sum+1][3];//开辟稀疏数组的空间

//给稀疏数组赋值
sparse[0][0]=11;//稀疏数组的第一行第一列 是原始数组的行数
sparse[0][1]=11;//。。。。。第二列是原视数组的的列数
sparse[0][2]=sum;//。。。。第三列是原始数组的有效值的个数


//把有效值写入稀疏数组里面
int count=0;
for (int i = 0; i <arry.length ; i++) {
    for (int j = 0; j <arry[i].length ; j++) {
      if (arry[i][j]!=0){
          count++;//从第二行开始写有效值
          sparse[count][0]=i;//第一列写原始数组中第几行
          sparse[count][1]=j;//第二列写原始数组中的第几列
          sparse[count][2]=arry[i][j];//具体的有效值
      }
    }
}


for (int i = 0; i <sparse.length ; i++) {
    for (int j = 0; j <sparse[i].length ; j++) {
        System.out.print("\t"+sparse[i][j]);
    }
    System.out.println();
}

稀疏数组转化原视的二维数组

1 先读取稀疏数组的第一行根据第一行创建原视的二维数据
2 读取稀疏后面几行的数据，赋值给原始的二维数组

   System.out.println("数据还原");

    int [][] arry2=new int[sparse[0][0]][sparse[0][1]];//还原大小

    for (int i =1; i < sparse.length; i++) {//从第一行开始遍历 稀疏数组的第一行记录的是原始数据的大小
        arry2[ sparse[i][0] ]   [ sparse[i][1] ]= sparse[i][2];//每一个数写入原始数组的指定位置
    }
    for (int[] row : arry2) {
        for (int i : row) {
            System.out.print("\t"+i);
        }
        System.out.println();
    }
}

队列

队列是一个有序列表，可以用链表或者数组实现

遵循先入先出的原则

用数组来模拟队列代码展示

   private int Maxsize;//队列的大小
    private int front;//指向队列第一个位置前面
    private  int real;//指向队列最后一个位置的后面
    private int[] arry;

    //初始化一个队列
    public AryyQueue(int size){
        Maxsize=size;
        front=-1;
        real=-1;//指向队列尾部 即使队列的最后一个数据
        arry =new int[Maxsize];
    }


    //判断队列是否满
    public boolean isFull(){
        return real==Maxsize-1;//最后一个位置和数组长度一致
    }
    //判断队列是否为空
    public  boolean isEempyt(){
       return real==front;
    }
    //往队列里面添加数
    public  void add(int n){
        if (isFull()){
            throw new RuntimeException("队列满了");
        }
        real++;
        arry[real]=n;
    }

    //从队列里面取数
    public int getqueue(){
        if (isEempyt()){//取数之前进行判断
            throw new RuntimeException("队列是空的 取不了数了");
       }
        front++;
        return arry[front];
    }

    //展示队列里面所有的
    public  void  show(){
        if (isEempyt()){
            throw new RuntimeException("队列是空的  无法展示了");
        }
        for (int i = 0; i < arry.length; i++) {
            System.out.println(i+"\t"+arry[i]);
        }
    }
    //查看队列的头信息
    public  int geyhead(){
        return arry[0];
    }
测试
      AryyQueue queue = new AryyQueue(3);
       queue.add(1);
       queue.add(2);
       queue.add(3);
        System.out.println(queue.getqueue());
        System.out.println(queue.getqueue());
        System.out.println(queue.getqueue());


        try {
            queue.show();
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }

        try {
            System.out.println(queue.getqueue());
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }


        try {
            queue.add(4);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
    }
}

问题：

取完队列里面所有的元素之后，但是无法添加新的元素

因为元素被取只是把原先数组那个位置的数，变成了无效值，但是那个位置依然有数，尾部指针没有返回初始状态

环形数组：思路要空出一个空间，你队列存的实际上比你队列大小要少一个。指针的指向永远不会下标越界，也就是说他的取值只能在队列的长度和零之间，用到取模

private int Maxsize;//队列的大小
private int front;//指向队列第一个元素   定义不一样了 初始值改成了零 初始值和定义没有关系
private  int real;//指向队列的最后一个元素的位置
private int[] arry;


public QueueArray(int maxsize){
    Maxsize=maxsize;
    arry=new int[Maxsize];//初始化
}



//判断队列是否满
public boolean isFull(){
    return (real+1)%Maxsize==front;//判断队列满的条件改变了 预留一个空间 
}


//判断队列是否为空
public  boolean isEempyt(){
    return real==front;
}


//往队列里面添加数
public  void add(int n){
    if (isFull()){
        throw new RuntimeException("队列满了");
    }
    arry[real]=n;//直接添加
    //real指针如何移动
    //real++; 数组下标必越界
    //如果指向倒数第二个位置 就让real从新指向头部
    // 但是实际上 队列里面还是有一个空的位置 可以放置元素
    real = (real + 1) % Maxsize;
}


//从队列里面取数
public int getqueue(){
    if (isEempyt()){//取数之前进行判断
        throw new RuntimeException("队列是空的 取不了数了");
    }
   int value=arry[front];//临时变量
    //让front重新指向头部
    front=(front+1)%Maxsize;
    return value;
}

//展示队列里面所有的元素
public  void  show(){
    if (isEempyt()){
        throw new RuntimeException("队列是空的  无法展示了");
    }
    for (int i =front; i <front+siez(); i++) {
        System.out.println(i%Maxsize+"\t"+arry[i%Maxsize]);
    }
}
//队列里面的有效元素
public int siez(){
    return (real+Maxsize-front)%Maxsize;
}

//查看队列的头信息
public  int geyhead(){
    return arry[front];
}