队列
队列是一种非凡的线性表，非凡之处在于它只容许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作
队列的实现形式
1、链表队列
2、动态队列（数组）
实现动态队列
class Queue { private int front; private int rear; private Object[] objects; private int size; public Queue(int size) { front = 0; rear = 0; this.size = size + 1; objects = new Object[size]; } public void add(Object o) { if (isFull()) { System.out.println("队列已满，无奈增加"); return; } objects[rear] = o; rear = (rear + 1) % size; } public Object get() throws EmptyException { if (isEmpty()) { throw new EmptyException("队列为空，无奈取出元素"); } Object o = objects[front]; front = (front + 1) % size; return o; } public boolean isEmpty() { return front == rear; } public boolean isFull() { return (rear + 1) % size == front; } public int getCount() { return (rear - front + size) % size; } public void show() { int count = getCount(); for(int i = 0; i < count; i++) { System.out.println(objects[front]); front = (front + 1) % size; } }}class EmptyException extends Exception { public EmptyException() { } public EmptyException(String s) { super(s); }}简要剖析代码
参数的意义
front 永远指向队列的第一个元素
rear 永远指向队列的最初一个元素的下一个地位
构造方法
队列进行初始化，front = 0，rear = 0;
为什么要 this.size = size + 1; 前面在解释
isEmpty() 和 isFull() 办法
依据 front rear 的意义，不难得出判断队列是否为空就是 front == rear
咱们来看下判断队满的条件
如图，此时在增加元素5，队列就满了，同时 rear = 0
这个时候咱们发现，rear == front
因而队列满的条件为：rear == front
这与判断队列空的条件雷同，然而此时队列是有元素的
队列元素：2，6，3，0，1，5
因而队列满的条件不能是：rear == front
咱们通常会舍弃一个空间（不用来存放数据），也就是说，大小为 n 的数组，寄存的元素的个数为 n - 1
这样判断队满的条件就变为：(rear + 1) % size == front
这也就是为什么 this.size = size + 1
因为他人不晓得，你只能寄存 n - 1 个数据
getCount() 办法
获取元素的个数
当 rear > front
元素个数为：rear - front
元素个数为：5 - 0 = 5
当 rear < front
第一段为：size - front
第二段为：rear - 0
因而，元素个数为：(rear - front + size)
联合两种状况：
rear > front
(rear - front + size) % size = rear - front
rear < front
(rear - front + size) % size = rear - front + size
因而，通用公式为：(rear - front + size) % size
show() 办法
遍历队列，如果咱们晓得队列中元素的个数，那么循环次数就确定了下来，通过后面剖析，队列个数为 (rear - front + size) % size
每循环一次，就取出队列中 front 所指向的元素
取完之后，front = (front + 1) % size，指向下一个队列中的元素