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