队列 | 李福腾の博客

线性结构和非线性结构

线性结构

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

非线性结构

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

稀疏数组和队列

稀疏sparsearray数组

基本介绍

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

稀疏数组的转换

稀疏数组共有三列，第一列保存行信息，第二列保存列信息，第三列保存有效值
稀疏数组的第一行，分别保存该二维数组总共有多少行多少列，多少个有效值（n）
下面的n行分别对应n个有效值的行列信息和有效值的信息

稀疏数组代码实现

public class SparseArray {
    public static void main(String[] args) {
        int [][] char1 = new int[5][5];//定义一个五行五列的二维数组
        char1[0][1]=1;
        char1[2][3]=2;
        for (int[] row:char1
             ) {
            for (int a: row
                 ) {
                System.out.printf("%d\t",a);
            }
            System.out.println();
        }
        //将二维数组转成稀疏数组
        int sum = 0;
        for (int i = 0; i <char1.length ; i++) {
            for (int j = 0; j <char1[i].length ; j++) {
                if (char1[i][j]!=0){
                    sum++;
                }
            }
        }
        System.out.println(sum);
        //定义稀疏数组
        int sparseArray[][] = new int[sum+1][3];
        sparseArray[0][0]=5;
        sparseArray[0][1]=5;
        sparseArray[0][2]=sum;
        int count = 1;
        for (int i = 0; i <char1.length ; i++) {
            for (int j = 0; j <char1[i].length ; j++) {
                if (char1[i][j]!=0){
                    sparseArray[count][0]=i;
                    sparseArray[count][1]=j;
                    sparseArray[count][2]=char1[i][j];
                    count++;
                }
            }
        }
        for (int[] row:sparseArray
             ) {
            for (int data: row
                 ) {
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
        //稀疏数组转换成二维数组
        int char2[][] = new int[sparseArray[0][0]][sparseArray[0][1]];
        for (int i = 1; i <sparseArray.length ; i++) {
          char2[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
        }
        for (int[] row:char2
        ) {
            for (int a: row
            ) {
                System.out.printf("%d\t",a);
            }
            System.out.println();
        }
    }
}

队列

队列的应用场景

银行排队叫号系统

队列介绍

队列是一个有序列表，可以用数组或是链表来实现
遵循先入先出的原则：先存入队列的数据，要先取出。后存入的要后取出

数组模拟队列

编写一个ArrayQueue类
定义属性：maxSize:最大容量；front:队列头；rear:队列尾；arr[]：存放数据，模拟队列
创建队列的构造器
判断队列是否满
判断队列是否为空
添加数据到队列（int n）要先判断队列是否是满的
数据出队列要先判断队列是否空通过抛出异常
显示队列数据

代码实现

class  ArrayQueue{
    private int maxSize;//数组最大的容量
    private int front;//队列头
    private int rear;//队列尾
    private int[] arr;//该数组用于存放数据，模拟队列

    //创建队列的构造器
    public  ArrayQueue(int arrMaxsize){
        maxSize = arrMaxsize;
        arr = new int[maxSize];
        front = -1;
        rear = -1;
    }
    //判断队列是否满
    public boolean isFull(){
        return rear == maxSize-1;
    }

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

    //添加数据到队列
    public void addQueue(int n){
        //判断队列是否满
        if(isFull()){
            System.out.println("队列满");
        }
        rear++;
        arr[rear]=n;
    }

    //出队列
    public int getQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列空，不能取数据");
        }
        front++;
        return arr[front];
    }

    //显示队列
    public void showQueue(){
        if (isEmpty()){
            System.out.println("队列空，不能遍历");
            return;
        }
        for (int i = 0; i <arr.length ; i++) {
            System.out.printf("arr[%d]=%d\n",i,arr[i]);
        }
    }
    
}

目前数组没有达到复用的效果，改进：使用算法将该数组改成一个环形数组

数组模拟环形队列

front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素
rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，空出一个空间作为约定。
当队列满时，条件是（rear+1）%maxSize=front
当队列为空的条件 rear=front
队列中有效数据的个数（rear+maxSize-front）%maxSize

代码实现

class  CircleArray {
    private int maxSize;
    private int front;
    private int rear;
    private int[] arr;

    public CircleArray(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
    }

    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    public boolean isEmpty() {
        return rear == front;
    }

    public void addQueue(int n) {
        if (isFull()) {
            System.out.println("队列满");
            return;
        }
        arr[rear] = n;
        rear = (rear + 1) % maxSize;
    }

    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列空，不能取数据");
        }
        int count = arr[front];
        front=(front+1)%maxSize;
        return count;
    }

    public void showQueue(){
        if (isEmpty()){
            System.out.println("队列空");
            return;
        }
        for (int i = front; i <front+size() ; i++) {
            System.out.printf("arr[%d]=%d\n",i,arr[i]);
        }
    }

    public int size(){
        return (rear+maxSize - front)%maxSize;
    }
}