順序循環(huán)隊列
隊列是一個先進先出的有序列表诺祸，可以用數(shù)組或鏈表來實現(xiàn)
使用數(shù)組實現(xiàn)循環(huán)隊列：
- front指向隊頭元素往枣，初始值為0
- rear指向隊尾的后一個位置望侈，初始值為0
- 隊滿：front == (rear + 1) % maxSize
- 隊空：rear == front
- 有效數(shù)據(jù)量：(rear + maxSize - front) % maxSize
由于在rear后空出了一個空間來便于判斷隊滿辩昆，因此最多存儲maxSize個元素
循環(huán)隊列代碼實現(xiàn)：
public class CircularQueue {
// 數(shù)組最大容量
private int maxSize;
// front指向隊頭元素盲再，初始值為0
private int front;
// rear指向隊尾的后一個位置，初始值為0
private int rear;
private int[] arrayQueue;
public CircularQueue(int maxSize) {
this.maxSize = maxSize;
arrayQueue = new int[maxSize];
this.front = 0;
this.rear = 0;
}
// 判斷隊列是否滿
public boolean isFull() {
return front == (rear + 1) % maxSize;
}
// 判斷隊列是否空
public boolean isEmpty() {
return rear == front;
}
// 獲取有效數(shù)據(jù)量
public int getValidSize() {
return (rear + maxSize - front) % maxSize;
}
// 添加數(shù)據(jù)到隊尾棍鳖，返回值為是否添加成功
public boolean enqueue(int data) {
if (isFull())
return false;
arrayQueue[rear] = data;
// 將rear后移
rear = (rear + 1) % maxSize;
return true;
}
// 移除隊頭數(shù)據(jù)炮叶，返回值為是否移除成功
public boolean dequeue() {
if (isEmpty())
return false;
// 將front后移
front = (front + 1) % maxSize;
return true;
}
// 獲取隊頭數(shù)據(jù)
public int getFront() {
if (isEmpty()) {
// 通過拋異常來處理隊空的情況
throw new RuntimeException("隊列為空");
}
return arrayQueue[front];
}
// 遍歷隊列所有數(shù)據(jù)
public void showQueue() {
if (isEmpty()) {
System.out.println("隊空");
return;
}
// 從front開始遍歷
for (int i = front; i < front + getValidSize(); i++) {
System.out.printf("ArrayQueue[%d] = %d\n", i % maxSize, arrayQueue[i % maxSize]);
}
}
}
