隊列
- 隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。
- 遵循先入先出的原則。即：先存入隊列的數(shù)據(jù)，要先取出。后存入的要后取出
使用數(shù)組實現(xiàn)隊列
- 靜態(tài)隊列
- 環(huán)形隊列
靜態(tài)隊列實現(xiàn)
- 了解到隊列的基本概念之后，就需要準(zhǔn)備以下參數(shù)
- int front = -1;(隊頭)
- int rear = -1;(隊尾)
- int maxSize(最大數(shù)量)
- int [] array(數(shù)組)
這里我默認(rèn)隊頭和隊尾默認(rèn)值為-1，可按自己想法確定
- 解析幾個必要方法
/**
* 判斷隊列是否為空
*
* @return
*/
public boolean isEmpty() {
return front == rear;
}
用于出隊列時的判斷，如果沒有隊列中沒有數(shù)據(jù)，則不能出隊列
/**
* 判斷隊列是否滿
*
* @return
*/
public boolean isFull() {
return rear == maxSize - 1;
}
用于加入隊列的判斷，如果隊列已經(jīng)滿了，則不能加入隊列
/**
* 加入隊列 從隊尾開始添加 rear往后移動
*
* @param value
*/
public void addQueue(int value) {
if (isFull()) {
System.out.println("隊列已滿！");
return;
}
rear++;
array[rear] = value;
System.out.println("添加成功");
}
加入隊列，如果隊列已滿無法加入；否則隊尾位置后移，添加到數(shù)組中
/** 取出隊列 從隊頭開始取 font往后移動 */
public int getQueue() throws Exception {
if (isEmpty()) {
throw new RuntimeException("隊列為空！");
}
front++;
int value = array[front];
return value;
}
出隊列，如果隊列為空無法移出；否則隊頭位置后移，獲取結(jié)果
/** 輸出隊列 */
public void showQueue() {
if (isEmpty()) {
System.out.println("隊列為空！");
return;
}
for (int i = front; i < array.length; i++) {
System.out.printf("array[%d]：%d\n", i, array[i]);
}
}
輸出隊列結(jié)果，如果隊列為空不輸出；否則從隊頭位置開始，到數(shù)組最后位置進行輸出
3.以上就是靜態(tài)隊列的重要幾個方法的實現(xiàn)，可以發(fā)現(xiàn)使用數(shù)組實現(xiàn)靜態(tài)隊列，這個隊列只能使用一次，因為當(dāng)加入隊列到達隊列的最大值時，就已經(jīng)無法添加了；下面繼續(xù)使用數(shù)組來實現(xiàn)環(huán)形隊列解決這個問題
環(huán)形隊列實現(xiàn)
- 重點：使用%取模實現(xiàn)簡單算法，對實現(xiàn)靜態(tài)隊列的方法進行改造，保證始終在數(shù)組界限內(nèi)操作
- 準(zhǔn)備參數(shù)
- int front = 0;(隊頭)
- int rear = 0;(隊尾)
- int maxSize(最大數(shù)量)
- int [] array(數(shù)組)
現(xiàn)將隊頭和隊尾默認(rèn)值修改為0
- 方法改造
/**
* 判斷隊列是否為空
*
* @return
*/
public boolean isEmpty() {
return front == rear;
}
不用改動
/**
* 判斷隊列是否滿
*
* @return
*/
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
保證從隊頭開始到隊尾等于最大數(shù)量則為滿
rear+1：原因是如果當(dāng)front和rear都為0時即滿足isFull條件也滿足isEmpty條件
所以+1是為了防止條件沖突，預(yù)留一個空位
%maxSize 是為了保證始終在數(shù)組下標(biāo)界限內(nèi)操作
/**
* 加入隊列
*
* @param value
*/
public void addQueue(int value) {
if (isFull()) {
System.out.println("隊列已滿！");
return;
}
array[rear] = value;
rear = (rear + 1) % maxSize;
System.out.println("添加成功");
}
從隊尾開始添加 rear往后移動
%maxSize 是為了保證始終在數(shù)組下標(biāo)界限內(nèi)操作
/** 取出隊列 */
public int getQueue() throws Exception {
if (isEmpty()) {
throw new RuntimeException("隊列為空！");
}
int value = array[front];
front = (front + 1) % maxSize;
return value;
}
從隊頭開始取 front往后移動
%maxSize 是為了保證始終在數(shù)組下標(biāo)界限內(nèi)操作
/**
* 計算隊列中的有效數(shù)據(jù)個數(shù)
*
* @return
*/
public int getSize() {
return (rear - front + maxSize) % maxSize;
}
新增方法，用于循環(huán)輸出隊列結(jié)果使用，靜態(tài)隊列使用的是數(shù)組長度，而環(huán)形隊列則需要算出實際有效個數(shù)（其實就是從隊頭到隊尾的數(shù)據(jù)）
拆分理解：
① (rear - front + maxSize) % maxSize = rear % maxSize + front % maxSize + maxSize % maxSize
②rear%maxSize：取實際在數(shù)組內(nèi)有效下標(biāo) front同理
③(rear-front)%maxSize +1則為列尾和列首的距離
④+1是因為(rear-front)%maxSize是它們間的距離,實際+1才是有效個數(shù)
其實：(rear - front) % maxSize + 1更容易讓人理解
/** 輸出隊列 */
public void showQueue() {
if (isEmpty()) {
System.out.println("隊列為空！");
return;
}
for (int i = front; i < front + getSize(); i++) {
// 取值時需要下標(biāo)%maxSize,是因為如果發(fā)生先全添加后取出再添加不取出時，front會大于數(shù)組最大下標(biāo)，導(dǎo)致異常
System.out.printf("array[%d]：%d\n", i % maxSize, array[i % maxSize]);
}
}
front + getSize() 為最后一個數(shù)據(jù)的位置
i%maxSize 是為了保證始終在數(shù)組下標(biāo)界限內(nèi)操作
3.至此環(huán)形隊列改造完成，對于第一次接觸數(shù)據(jù)結(jié)構(gòu)和算法的朋友，使用數(shù)組實現(xiàn)環(huán)形隊列，需要仔細理解%和具體算法的的含義。這里附上github的代碼地址供參考：https://github.com/hlning/CircularQueue.git。
結(jié)束語
本人不常寫文章，如有問題，請大家多多指教，謝謝！
