数据结构之队列

队列

​ 队列和栈不同的是，栈遵循先进后出的原则， 而队列为先进先出（FIFO），就像排队买东西一样，先到先得。

​ 队列使用链表实现是比较简单的，用数组结构来实现队列。

​ 通过两个指针，一个指向队头（front），一个指向队尾（rear）。当入队时，让rear前移，当出队时，让front前移。如图所示，规定rear指向队尾的下一个元素。front指向队头元素。

如果是这样操作的话，很明显，出队以后，内存空间就使用不了了，这样得多浪费内存，因此，将队列设计成循环队列。大致长这样

初始化的时候，两个指针指向同一位置，当入队时，rear指针后移，即rear指针永远指向队尾元素的下一个，所以，在循环队列中，有一块空间是不存放数据的。

​ 如何确定队列满了还是空了。只要当 front == rear 则说明队列空了；当rear + 1 == front时，就说明队列满了。但是在不断地入队出队操作，rear值肯定越来越大，可以通过mod的方法来保证rear的值。即（rear + 1） % maxSize == front。

如何得到任意时刻队列中的元素个数。用（rear-front+maxSize） % maxSize就可以得到，加上maxSize是为了防止rear的值小于front的值。

class Queue {
    int maxSize;
    int rear;
    int front;
    int[] queue;
    
    public Queue(int maxSize) {
        this.maxSize = maxSize;
        queue = new int[maxSize];
    }
    
    //判断队列是否满了
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }
    
    //判空
    public boolean isEmpty() {
        return front == rear;
    }
    
    //入队
    public void addQueue(int data) {
        if (isFull()) return;
        queue[rear] = data;
        rear = (rear + 1) % maxSize;
    }
    
    //出队
    public int getQueue() {
        if (isEmpty()) return;
        int data = queue[front];
        front = (front + 1) % maxSize;
        return data;
    }
    
    //查看有效元素个数
    public int size() {
        return (rear - front + maxSize) % maxSize;
    }
    
    //查看队头元素
    public int headOfQueue() {
        if (isEmpty()) return;
        return arr[front];
    }
}

​ 有关队列的应用：

​ 在线程池中，可以规定线程的阻塞队列的类型。在AQS中，也是用到了队列来进行线程的阻塞。

​ 在CPU执行程序时，会把所有运行的程序放在一个队列当中，等等。。。