稀疏数组和队列

稀疏数组(sparse array)

应用场景

存在很多没有意义的相同的数据需要记录时，可以使用稀疏数组。例如一个数组中大部分元素都是0，或者是其他的相同的数据，可以使用稀疏数组来保存该数组。

稀疏数组的处理方法

记录该数组的行列、有效值的个数。
把有效值的行列及其数值记录在一个小规模的数组里，从而达到缩小程序的规模。

一个举例说明如下：

稀疏数组举例

队列

队列介绍

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

模拟队列

普通的思路模拟一个队列结构，是利用固定长度的数组或动态数组来实现模拟，利用固定长度的数组来实现队列当尾指针到达数组的尾部的时候就不能再添加数据了（不管此事数组的前部分是否为空），利用动态数组来模拟队列随着数组数据的存取，会浪费大量的空间。所以最好的模拟队列的方式是 循环队列 。

循环队列

使用 固定大小的数组 和 两个指针 来指示起始位置和结束位置。目的是 重用被浪费的空间 。循环队列也被称为“环形缓冲器”。

① 一个循环队列的实现方法如下：

设定front指针指向队列的第一个元素，rear指针指向队列的最后一个元素的后一个元素。
判断队列满的条件：(rear+1)%size==front,判断队列为空的条件：rear==front。
初始化队列的内部数组的时候，多出一个元素空间（因为逻辑上传入的数值为队列的大小，由于步骤1的设定，总有一个空间是无法使用到的）。

② 实现代码如下：

/**
 * 设计一个循环队列
 */
class MyCircularQueue_1 {
    //front指针指向队列的第一个元素，rear指向队列的最后一个元素的后一个元素。
    //初始化内部数组的大小的时候，多出一个空间用，方便isEmpty和isFull的判断。
    private int front=0,rear=0,size;
    private int[] data;

    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue_1(int k) {
        size=k+1;
        data=new int[k+1];
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        data[rear]=value;
        rear=(rear+1)%size;
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        front++;
        return true;
    }

    /** Get the front item from the queue. */
    public int Front() {
        if(!isEmpty()){
            return data[front];
        }
        return -1;
    }

    /** Get the last item from the queue. */
    public int Rear() {
        if(!isEmpty()){
            //System.out.println("当前的rear指针："+String.valueOf((rear+size-1)%size));
            return data[(rear+size-1)%size];
        }
        return -1;
    }

    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return front%size==rear;
    }

    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return (rear+1)%size==front;
    }

    public static void main(String[] a){
        //* Your MyCircularQueue object will be instantiated and called as such:
        MyCircularQueue_1 obj = new MyCircularQueue_1(3);
        obj.enQueue(1);
        obj.enQueue(2);
        obj.enQueue(3);
        obj.enQueue(4);
        System.out.println(obj.Rear());
        System.out.println(obj.isFull());
        obj.deQueue();
        obj.enQueue(4);
        System.out.println(obj.Rear());
    }
}

文章目录