一、队列
1) 队列是一种线性结构，即一个下标对应一个元素
2) 队列是一个有序列表， 可以用数组或是链表来实现。
3) 遵循先入先出的原则。 即： 先存入队列的数据， 要先取出。 后存入的要后取出
（一）普通队列：
如图，以front表示队首的下标，默认值为-1，指向队列中第一个有效元素的前一位；以rear表示队尾下标，默认值是-1，指向队列中的最后一个有效元素。
以MaxSize表示队列的最大容量。当有数据加入时，队尾下标会增加，当front=MaxSize-1时，队列满；当有数据移出时，队首下标会减小，当front=rear时，队列为空。
以数组模拟普通队列时，当增加元素，执行rear++操作；当移出元素，执行front++元素。
代码实现队列的增删查
1 class ArrayQueue{ 2 private int maxNums;//队列的最大容量 3 private int rear;//队列尾 指向队列中的最后一个有效元素 4 private int front;//队列头 指向队列中第一个有效元素的前一位 5 private int[] queues;//用来存储队列中的数据 6 7 public ArrayQueue(int maxNums) { 8 this.maxNums = maxNums; 9 rear=-1; 10 front=-1; 11 queues=new int[maxNums]; 12 } 13 14 //判断队列是否已满 15 public boolean isFull(){ 16 return rear==maxNums-1; 17 } 18 //判断队列是否为空 19 public boolean isEmpty(){ 20 return rear==front; 21 } 22 //增加数据 23 public void addQueue(int n){ 24 if (isFull()) { 25 System.out.println("队列已满"); 26 return; 27 } 28 //队列没满，向队尾添加数据 29 rear++; 30 queues[rear]=n; 31 } 32 //拿出数据 33 public int getQueue(){ 34 if (isEmpty()){ 35 System.out.println("队列已空"); 36 } 37 front++; 38 return queues[front]; 39 40 } 41 //遍历队列 42 public void showQueue(){ 43 if (isEmpty()){ 44 return; 45 } 46 for (int i = 0; i <queues.length ; i++) { 47 System.out.printf("queues[%d]=%d\n",i,queues[i]); 48 } 49 } 50 //查询头数据 51 public int peek(){ 52 if (isEmpty()){ 53 throw new RuntimeException("队列为空，无头数据"); 54 } 55 return queues[front+1]; 56 } 57 }
通过执行上述代码，可以发现在对元素进行移出后，被移出元素所对应的front无法再被利用，因此将其改造为环形队列使其得以复用。
（二）、环形队列
采用front或者rear对MaxSize取模的操作，来达到循环利用。
关于头索引与尾索引的变化：
1、头索引指向队列的第一个有效元素，初始值为0。尾索引指向队列最后一个有效元素的后一位，也就是说，环形队列中需要在最后空出一个位置。
这样做的原因：对于一个长度为n的队列arry[n]来说，若rear指向最后一个有效元素（n-1，那么其中有效元素的数量可能为0,1,2...n共n+1种情况。但若以rear- front的形式表示元素数量，则会有0,1,2...n-1共n种情况，因此需要将最后一位空出，使rear指向最后一位（n-1），才能使情况一一对应。
2、当队列为空的条件为：front=rear
3、队列满的条件为：（rear+1）%maxSize=0
4、进行增删元素操作时，对front与rear的后移： front=（front+1）%maxSize rear=（rear+1）%maxSize
5、队列中有效的数据个数为：（rear+maxSize-front）%maxSize
对于以上操作的代码实现
1 class CircleArraryQueue{ 2 private int maxNums;//队列的最大容量 3 private int rear;//队列尾 指向队列中最后一个有效元素的后一位 4 private int front;//队列头 指向队列的首个元素 5 private int[] circleQueues;//用来存储队列中的数据 最后一个元素为空，最后一个有效元素为倒数第二个元素 6 7 public CircleArraryQueue(int maxNums) { 8 this.maxNums=maxNums; 9 rear=0; 10 front=0; 11 circleQueues=new int[maxNums]; 12 } 13 //判断队列是否已满 14 public boolean isFull(){ 15 return (rear+1)%maxNums==front?true:false; 16 } 17 //判断队列是否为空 18 public boolean isEmpty(){ 19 return rear==front?true:false; 20 } 21 //增加数据 22 public void addQueue(int n){ 23 if (isFull()) { 24 System.out.println("队列已满"); 25 return; 26 } 27 //队列没满，向队尾添加数据 28 circleQueues[rear]=n; //判断队列是否已满，(rear+1)%maxNums==front 29 //此时的rear已经指向队列的最后，取模后赋值给rear 30 rear=(rear+1)%maxNums; 31 } 32 //拿出数据 33 public int getQueue(){ 34 if (isEmpty()){ 35 System.out.println("队列已空"); 36 } 37 //front指向的是队列中的第一个元素。 38 int value=circleQueues[front]; 39 front=(front+1)%maxNums; 40 return value; 41 } 42 //遍历队列 43 public void showQueue(){ 44 if (isEmpty()){ 45 return; 46 } 47 //从front开始遍历，遍历有效元素个数次（有效元素个数为长度-1） 48 for (int i = front; i<front+(rear+maxNums-front)%maxNums ; i++) { 49 //i的大小可能会超过数组的长度，i%maxNums可以保证i在数组中的相对位置不变 50 System.out.printf("queues[%d]=%d\n",i%maxNums,circleQueues[i%maxNums]); 51 } 52 } 53 //查询头数据 54 public int peek(){ 55 if (isEmpty()){ 56 throw new RuntimeException("队列为空，无头数据"); 57 } 58 return circleQueues[front]; 59 } 60 }
对其执行3次添加数据后的结果（队列容量为4，但只能存储3个有效元素）：
queues[0]=10 queues[1]=20 queues[2]=30
执行两次取出数据的操作后，只剩下 queues[2]=30
随后执行2次添加
1 queues[2]=30 2 queues[3]=10 3 queues[0]=20
原文：https://www.cnblogs.com/Cong-l/p/12701329.html