數據結構與算法——隊列（環形隊列）
一個使用場景
銀行辦理業務的排隊叫號
辦理業務的人先拿號，然後窗口叫號處理，沒有叫到的，則排隊等待。
基本介紹
隊列：是一個 有序列表，可以用 數組 或 鏈表 實現。
特點：遵循 先入先出 原則。即：先存入的數據，先取出。
示意圖：
- front：隊首，隊列頭部
- rear：隊尾，隊列尾部
- 左 1 圖：隊列初始化的兩個變量值
- 中圖：存入數據後，的首位變化
- 右圖：取數據時，從隊首取，隊首的變量指向也在發生變化
數組模擬隊列
隊列本身是 有序列表，使用數組結構來存儲隊列的數據，則如前面基本介紹中的示意圖一樣。
聲明 4 個變量：
arr：用來存儲數據的數組maxSize：該隊列的最大容量front：隊首下標，隨着數據輸出而改變rear：隊尾下標，隨着數據輸入而改變
隊列中常用操作分析，以 add，把數據存入隊列為例，思路分析：
- 將尾指針往後移：
rear + 1，前提是當front == rear時，隊列是空的 - 若尾指針
rear < maxSize -1：- 則將數據存入 rear 所指的數組元素中，
- 否則無法存入數據。
rear = maxSize -1表示隊列滿了
以上思路是一個最基本的實現（不是完美的，看完代碼就明白了）。代碼實現如下
/**
* 數組模擬隊列
*/
public class ArrayQueueDemo {
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(3);
queue.add(1);
queue.add(2);
queue.add(3);
System.out.println("查看隊列中的數據");
queue.show();
System.out.println("查看隊列頭數據：" + queue.head());
System.out.println("查看隊列尾數據：" + queue.tail());
// queue.add(4);
System.out.println("獲取隊列數據：" + queue.get());
System.out.println("查看隊列中的數據");
queue.show();
}
}
class ArrayQueue {
private int maxSize; // 隊列最大容量
private int front; // 隊列頭,指向隊列頭的前一個位置
private int rear; // 隊列尾，指向隊列尾的數據（及最後一個數據）
private int arr[]; // 用於存儲數據，模擬隊列
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
front = -1;
rear = -1;
}
/**
* 取出隊列數據
*/
public int get() {
if (isEmpty()) {
throw new RuntimeException("隊列空");
}
return arr[++front];
}
/**
* 往隊列存儲數據
*/
public void add(int n) {
if (isFull()) {
System.out.println("隊列已滿");
return;
}
arr[++rear] = n;
}
/**
* 顯示隊列中的數據
*/
public void show() {
if (isEmpty()) {
System.out.println("隊列為空");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d] = %d \n", i, arr[i]);
}
}
/**
* 查看隊列的頭部數據，注意：不是取出數據，只是查看
*
* @return
*/
public int head() {
if (isEmpty()) {
throw new RuntimeException("隊列空");
}
return arr[front + 1]; // front 指向隊列頭前一個元素，取頭要 +1
}
/**
* 查看隊尾數據
*
* @return
*/
public int tail() {
if (isEmpty()) {
throw new RuntimeException("隊列空");
}
return arr[rear];
}
// 隊列是否已滿
private boolean isFull() {
return rear == maxSize - 1;
}
// 隊列是否為空
private boolean isEmpty() {
return rear == front;
}
}
運行測試
查看隊列中的數據
arr[0] = 1
arr[1] = 2
arr[2] = 3
查看隊列頭數據：1
查看隊列尾數據：3
獲取隊列數據：1
查看隊列中的數據
arr[0] = 1
arr[1] = 2
arr[2] = 3
分析
目前實現了一個 一次性的隊列（不能復用），因為可以往隊列中添加數據，基本功能也是可以的，當隊列滿之後，再添加就加不進去了，獲取數據也不能清空原隊列中的數據。
優化方向：使用算法將這個數組改進成一個環形隊列。
數組模擬環形隊列
思路分析
-
front：含義調整
表示：隊列的第一個元素，也就是說
arr[front]就是隊列的第一個元素初始值：0
-
rear：含義調整
表示：隊列的最後一個元素的下一個位置
初始值(只是初始值)：0
這個很重要，是一個小算法，能更方便的實現我們的環形隊列。
-
隊列 滿 計算公式：
(rear + 1) % maxSize == front -
隊列 空 計算公式：
rear == front -
隊列中 有效元素個數 計算公式：
(rear + maxSize - front) % maxSize
為了能更清晰這個算法，下面畫圖來演示隊列中元素個數，關鍵變量的值
該算法取巧的地方在於 rear 的位置，注意看上圖，rear 所在的位置 永遠是空的，實現環形隊列的算法也有多種，這裡空出來一個位置，是這裡算法的核心。所以，循環隊列會浪費一個數組的存儲空間。
代碼實現
/**
* 數組擬環形隊列
*/
public class CircleQueueDemo {
public static void main(String[] args) {
CircleQueue queue = new CircleQueue(3);
// 為了測試方便，寫一個控制台輸入的小程序
Scanner scanner = new Scanner(System.in);
boolean loop = true;
char key = ' '; // 接受用戶輸入指令
System.out.println("s(show): 顯示隊列");
System.out.println("e(exit): 退出程序");
System.out.println("a(add): 添加數據到隊列");
System.out.println("g(get): 從隊列取出數據");
System.out.println("h(head): 查看隊列頭的數據");
System.out.println("t(tail): 查看隊列尾的數據");
System.out.println("p(isEmpty): 隊列是否為空");
while (loop) {
key = scanner.next().charAt(0);
switch (key) {
case 's':
queue.show();
break;
case 'e':
loop = false;
break;
case 'a':
System.out.println("請輸入要添加到隊列的整數：");
int value = scanner.nextInt();
queue.add(value);
break;
case 'g':
try {
int res = queue.get();
System.out.printf("取出的數據是：%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int res = queue.head();
System.out.printf("隊首數據：%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 't':
try {
int res = queue.tail();
System.out.printf("隊尾數據：%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'p':
System.out.printf("隊列是否為空：%s", queue.isEmpty());
break;
}
}
}
}
class CircleQueue {
private int maxSize; // 隊列最大容量
private int front; // 隊列頭,指向 隊頭 的元素
private int rear; // 隊列尾，指向 隊尾 的下一個元素
private int arr[]; // 用於存儲數據，模擬隊列
public CircleQueue(int arrMaxSize) {
maxSize = arrMaxSize + 1;
arr = new int[maxSize];
front = 0;
rear = 0;
}
/**
* 取出隊列數據
*/
public int get() {
if (isEmpty()) {
throw new RuntimeException("隊列空");
}
// front 指向的是隊首的位置
int value = arr[front];
// 需要向後移動，但是由於是環形，同樣需要使用取模的方式來計算
front = (front + 1) % maxSize;
return value;
}
/**
* 往隊列存儲數據
*/
public void add(int n) {
if (isFull()) {
System.out.println("隊列已滿");
return;
}
arr[rear] = n;
// rear 指向的是下一個位置
// 由於是環形隊列,需要使用取模的形式來喚醒他的下一個位置
rear = (rear + 1) % maxSize;
}
/**
* 顯示隊列中的數據
*/
public void show() {
if (isEmpty()) {
System.out.println("隊列為空");
return;
}
// 打印的時候，需要從隊首開始打印
// 打印的次數則是：有效的元素個數
// 獲取數據的下標：由於是環形的，需要使用取模的方式來獲取
for (int i = front; i < front + size(); i++) {
int index = i % maxSize;
System.out.printf("arr[%d] = %d \n", index, arr[index]);
}
}
/**
* 查看隊列的頭部數據，注意：不是取出數據，只是查看
*
* @return
*/
public int head() {
if (isEmpty()) {
throw new RuntimeException("隊列空");
}
return arr[front];
}
/**
* 查看隊尾數據
*
* @return
*/
public int tail() {
if (isEmpty()) {
throw new RuntimeException("隊列空");
}
// rear - 1 是隊尾數據，但是如果是環形收尾相接的時候
// 那麼 0 -1 就是 -1 了，負數時，則是數組的最後一個元素
return rear - 1 < 0 ? arr[maxSize - 1] : arr[rear - 1];
}
// 隊列是否已滿
private boolean isFull() {
return (rear + 1) % maxSize == front;
}
// 隊列是否為空
public boolean isEmpty() {
return rear == front;
}
// 有效個數
public int size() {
return (rear + maxSize - front) % maxSize;
}
}
運行測試功能輸出
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數據到隊列
g(get): 從隊列取出數據
h(head): 查看隊列頭的數據
t(tail): 查看隊列尾的數據
p(isEmpty): 隊列是否為空
a
請輸入要添加到隊列的整數：
10
a
請輸入要添加到隊列的整數：
20
a
請輸入要添加到隊列的整數：
30
s
arr[0] = 10
arr[1] = 20
arr[2] = 30
a
請輸入要添加到隊列的整數：
40
隊列已滿
h
隊首數據：10
t
隊尾數據：30
g
取出的數據是：10
s
arr[1] = 20
arr[2] = 30
a
請輸入要添加到隊列的整數：
40
s
arr[1] = 20
arr[2] = 30
arr[3] = 40
h
隊首數據：20
t
隊尾數據：40
g
取出的數據是：20
s
arr[2] = 30
arr[3] = 40
a
請輸入要添加到隊列的整數：
50
s
arr[2] = 30
arr[3] = 40
arr[0] = 50
h
隊首數據：30
t
隊尾數據：50
可以看到上面的表現，和那個圖解分析是一致的， rear 所在的位置沒有元素，是動態的。
