算法专题-手动实现循环队列

这次我就使用数组来实现静态队列了。值得注意的是：往往实现静态队列，我们都是做成循环队列。这道题也是我多次面试过程中遇到的，比如字节跳动和猿辅导，希望大家掌握。

为什么静态队列要做成循环队列呢？试想，底层依赖数组，如果不做成循环的，会非常浪费空间，那我们得申请多大的内存啊？既然做成循环的，首先我们得解决几个问题，如何判空？如何判满？最多可以存放多少元素个数？

通过这幅图，想必大家很容易理解，下面通过代码说明。

public class MyQueue {
 public int[] arrays;
 public int front;//指向第一个有效元素
 public int rear;//指向最后一个有效元素的下一个元素（无效元素）

 public MyQueue(int[] arrays, int front, int rear) {
 this.arrays = arrays;
 this.front = front;
 this.rear = rear;
 }

 /**
 * 判断队列是否满了
 * @param myQueue
 * @return
 */
 public static boolean isFull(MyQueue myQueue){
 if((myQueue.rear + 1) % myQueue.arrays.length == myQueue.front){
 return true;
 }else{
 return false;
 }
 }

 /**
 * 判断是否为空
 * @param myQueue
 * @return
 */
 public static boolean isEmpty(MyQueue myQueue){
 if(myQueue.rear == myQueue.front){
 return true;
 }else{
 return false;
 }
 }

 /**
 * 入队
 * @param myQueue
 * @param value
 */
 public static void enQueue(MyQueue myQueue, int value){
 //不是满的队列才入队
 if(!isFull(myQueue)){
 myQueue.arrays[myQueue.rear] = value;
 myQueue.rear = (myQueue.rear + 1) % myQueue.arrays.length;
 }
 }

 /**
 * 遍历
 * @param myQueue
 */
 public static void traverse(MyQueue myQueue){
 int i = myQueue.front;
 while(i != myQueue.rear){
 System.out.print(myQueue.arrays[i] + " ");
 i = (i + 1) % myQueue.arrays.length;
 }
 System.out.println();
 }

 public static void outQueue(MyQueue myQueue){
 if(!isEmpty(myQueue)){
 int value = myQueue.arrays[myQueue.front];
 System.out.println(value);
 myQueue.front = (myQueue.front + 1) % myQueue.arrays.length;
 }
 }

 public static void main(String[] args) {
 MyQueue myQueue = new MyQueue(new int[6], 0, 0);
 System.out.println(isEmpty(myQueue));
 enQueue(myQueue, 1);
 enQueue(myQueue, 2);
 enQueue(myQueue, 3);
 enQueue(myQueue, 4);
 enQueue(myQueue, 5);
 System.out.println(isFull(myQueue));
 traverse(myQueue);
 outQueue(myQueue);
 }
}

输出结果：

从上面的设计我们可以发现：rear并不指向最后一个有效的元素，在循环队列中这样设计是非常方便的！因为这样设计可以让我们分得清队头和队尾(不然循环队列不断入队或出队，位置是变化很快的)

由于我们是循环队列，所以front和rear值会经常变动，我们得把front和rear的值限定在一个范围内，不然会超出队列的长度的。

我们通过这种方式：rear=（rear+1)%数组长度

比如rear的下标是2，数组的长度是6，往后面移一位是3，那么rear = （rear+1) % 6，结果还是3。