队列以及循环队列

队列

队列的一个场景

比如我们在食堂打饭就是一个典型的队列使用场景，排在前面的同学先打着饭，然后先离开，后来的同学只能排在队尾，直到前面的同学打完饭才能轮到自己。

队列介绍

1）队列是一个有序列表，可以用数组或是链表来实现。
2）遵循先入先出的原则。即：先存入队列的数据，要先取出；后存入的数据要后取出。
3）队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列图示

队列可以用数组和链表来实现，在这里我们用数组来实现。
1 2 3 4 5 6依次进队，出队的顺序也是1 2 3 4 5 6

循环队列

循环队列介绍

循环队列其实就是对数组模拟队列的优化（在这里循环队列用数组模拟），充分利用数组，因此将数组看做是一个环形的。（通过取模的方式实现）

循环队列图示

循环队列只是在逻辑上的循环，在内存中并不是真正的循环（即图示中1 和 6 在内存中并不是连续的）。

循环队列操作

1）定义一个整型变量 head 指向队头。
2）定义一个整型变量 rear指向队头。
3）每添加一个元素， rear往后移动一个位置， rear+ 1；考虑在移动的过程中rear往后＋1，但是不能超过队列最大下标，所以需要进行取模操作，rear = (rear + 1) % element.length。
4）每取出一个元素， head 往后移动一个位置， head +1，同样为了防止下标越界也要进行取模操作。
5）每取出一个元素 head 往后移动一个位置，每添加一个元素， rear往后移动一个位置，循环操作，当 head == rear时，队列已满，可是一开始队列为空， head 和 rear也是指向同一个位置的，那么 head 和 rear相等就不能作为判满操作了。在这里为解决这个问题，我们选择浪费一个空间， rear指向的位置不存数据。当( rear+1 ) % element.length == head 时队列已满。

动画演示

代码如下

public class CircleQueue {
    private int[] element;
    private int head;
    private int rear;
    private int max = 6;

    //构造函数
    public CircleQueue() {
        element = new int[max];
    }

    //判空
    private boolean isEmpty() {
        return head == rear;
    }

    //判满
    private boolean isFull() {
        return (rear + 1) % element.length == head;
    }

    //入队
    public boolean push(T value) {
        if (isFull()) {
            System.out.println("队列已满");
            return false;
        }
        element[rear] = value;
        rear = ++rear % element.length;
        return true;
    }

    //出队
    public boolean pop() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
            return false;
        }

        head = ++head % element.length;
        return true;
    }

    //获得队头元素
    public int peek() {
        if (isEmpty()) {
			throw new EmptyStackException();
        }
        return element[head];
    }
    
    //打印队列
    public int show() {
    	while (!isEmpty()) {
            System.out.print(element[head] + " ");
            head++;
        }
    }
}