算法专题-手动实现循环队列
这次我就使用数组来实现静态队列了。值得注意的是：往往实现静态队列，我们都是做成循环队列。这道题也是我多次面试过程中遇到的，比如字节跳动和猿辅导，希望大家掌握。
为什么静态队列要做成循环队列呢？试想，底层依赖数组，如果不做成循环的，会非常浪费空间，那我们得申请多大的内存啊？既然做成循环的，首先我们得解决几个问题，如何判空？如何判满？最多可以存放多少元素个数？
通过这幅图，想必大家很容易理解，下面通过代码说明。
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。