這次我就使用數(shù)組來實現(xiàn)靜態(tài)隊列了。值得注意的是：往往實現(xiàn)靜態(tài)隊列，我們都是做成循環(huán)隊列。這道題也是我多次面試過程中遇到的，比如字節(jié)跳動和猿輔導(dǎo)，希望大家掌握。
為什么靜態(tài)隊列要做成循環(huán)隊列呢？試想，底層依賴數(shù)組，如果不做成循環(huán)的，會非常浪費空間，那我們得申請多大的內(nèi)存??？既然做成循環(huán)的，首先我們得解決幾個問題，如何判空？如何判滿？最多可以存放多少元素個數(shù)？
通過這幅圖，想必大家很容易理解，下面通過代碼說明。
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);
}
}
輸出結(jié)果：
從上面的設(shè)計我們可以發(fā)現(xiàn)：rear并不指向最后一個有效的元素，在循環(huán)隊列中這樣設(shè)計是非常方便的！因為這樣設(shè)計可以讓我們分得清隊頭和隊尾(不然循環(huán)隊列不斷入隊或出隊，位置是變化很快的)
由于我們是循環(huán)隊列，所以front和rear值會經(jīng)常變動，我們得把front和rear的值限定在一個范圍內(nèi)，不然會超出隊列的長度的。
我們通過這種方式：rear=（rear+1)%數(shù)組長度
比如rear的下標(biāo)是2，數(shù)組的長度是6，往后面移一位是3，那么rear = （rear+1) % 6，結(jié)果還是3。
