2.队列

举个例子：饭堂打饭，后来的人只能站到队尾，前面的人走了之后，后面的人补上，

介绍

队列是一个方向进一个方向出的数据结构，可以使用数组和链表来实现。先进先出。
一般的实现过程：

• 数组思路：创建一个数组，一个头一个尾部，加入数据尾前进一个，走一个，头加一个。如果使用数据，数据存储到数组大小的时候，就无法存储了。现在我们先写一个数组实现，一会优化。

代码实现

public class Duilie {
    private int maxsize = 10;
    private int front = -1; //tou
    private int rear = -1;  //尾
    private int arr[];
    public Duilie(){
        arr = new int[maxsize];
    }

    public boolean isFull(){
        rear = maxsize - 1; 
    }

    public void addData(int num){
        if (isFull())return;
        rear++;
        arr[rear] = num;
    }

    public int outData(){
        if (isEmpty()){
            return -1;
        }
        front++;
        return arr[front];
    }

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

就是简单的对数组进行操作，增加之前查看是不是满了，取数据之前是不是为空。

优化

上面的代码如果最后到达了结尾，显示满了，队头的数据出去了，空间却得不到使用，所以属于循环数组。

public class XunhuanDuilie {
    private int maxsize = 10;
    private int front = 0; //tou
    private int rear = 0;  //尾
    private int arr[];
    public XunhuanDuilie(){
        arr = new int[maxsize];
    }

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

    public void addData(int num){
        if (isFull())return;
        rear = rear % maxsize;
        arr[rear] = num;
        rear++;
    }

    public int outData(){
        if (isEmpty()){
            return -1;
        }
        front%=maxsize;
        return arr[front];
        front++;
    }

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

将开始的位置都设置为0，还是如何找出下标，如何判断满和空，这个只要合理即可。