队列

[Zakariyya]

• 有序列表，可以用 数组 或者 链表 来实现
• 遵循 先入先出 的原则

因为队列的输出、输入分别是从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变。

构建队列思路

• 将尾指针往后移，rear+1，当front == rear [空]

• 若尾指针rear 小于队列的最大下标 maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据

  rear == maxSize-1[队列满]

环形队列（取模：%）

思路

1. front变量的含义做一个调整：front指向队列第一个元素，也就是arr[fornt]就是队列第一个元素，front的初始值 = 0
2. rear变量的含义做一个调整：rear指向队列的最后一个元素的最后一个位置，因为希望空出一个空间作为约定，rear的初始值 = 0
3. 当队列满时，条件是 (rear + 1) % maxSize == front [满]
4. 队列为空的条件， rear == front [空]
5. 当我们这样分析，队列中有效的数据的个数 (rear + maxSize - front) % maxSize

添加数据

1. 判断是否满： (rear + 1) % maxSize == front
2. 添加数据

//直接将数据加入 arr[rear] = n;

//将rear后移，这里必须考虑取模 rear = (rear+1)%maxSize;

### 取出数据
> 这里需要分析出 front 是指向队列的第一个元素

1. 先把front对应的值保留到一个临时变量
1. 先把front后移： **front = (front+1)% maxSize;** 
1. 将临时保存的变量返回
```java
//显示队列的所有数据

public void showQueue(){
    if(isEmpty()){
        sout("空队列");
        return;
    }

    //遍历
    // 思路：从front开始遍历，遍历多少个元素
    for(int i = front; i < front + size(); i++){
        sout("arr[%d]=%d\n", i % maxSize, arr[i%maxSize]);
    }

}
// 求出当前队列的有效数据个数
public int size(){
    return (rear + maxSize - front) % maxSize;
}