總目錄：地址如下看總綱
1歉闰、隊列基本說明
1、隊列是一個有序列表琢唾，可以用數(shù)組或者鏈表實現(xiàn)
2载荔、遵循先進先出原則，先存入數(shù)據(jù)先取出采桃，后存入后取出
2懒熙、數(shù)組模擬隊列
image.png
1、隊列本身是有序列表普办，若使用數(shù)組的結(jié)構(gòu)來存儲隊列的數(shù)據(jù)工扎，則隊列數(shù)組的聲明如上圖, 其中 maxSize 是該隊列的最大容量。
2衔蹲、因為隊列的輸出肢娘、輸入是分別從前后端來處理，因此需要兩個變量 front及 rear分別記錄隊列前后端的下標舆驶，front 會隨著數(shù)據(jù)輸出而改變橱健，而 rear則是隨著數(shù)據(jù)輸入而改變
3、數(shù)組模擬隊列設(shè)計思路：
當我們將數(shù)據(jù)存入隊列時稱為”addQueue”沙廉，addQueue 的處理需要有兩個步驟：
(1)將尾指針往后移：rear+1 , 前提是 判斷 是否為空 取決于 front == rear 【空】
(2)若尾指針 rear 小于隊列的最大下標 maxSize-1拘荡，則將數(shù)據(jù)存入 rear所指的數(shù)組元素中，否則無法存入數(shù)據(jù)撬陵。
前提判斷是否 隊列 容量滿了 rear == maxSize - 1[隊列滿]
4珊皿、核心代碼和測試代碼：
package com.kk.datastructure.queue;
import java.util.Scanner;
import javax.management.RuntimeErrorException;
/**
* title: 數(shù)組模擬隊列
* @author 阿K
* 2020年11月22日 下午2:12:32
*/
public class ArrayQueueDemo {
public static void main(String[] args) {
//創(chuàng)建一個隊列
ArrayQueue queue = new ArrayQueue(3);
char key = ' '; //接收用戶輸入
Scanner scanner = new Scanner(System.in);//
boolean loop = true;
//輸出一個菜單
while (loop) {
System.out.println("s(show): 顯示隊列");
System.out.println("e(exit): 退出程序");
System.out.println("a(add): 添加數(shù)據(jù)到隊列");
System.out.println("g(get): 從隊列取出數(shù)據(jù)");
System.out.println("h(head): 查看隊列頭的數(shù)據(jù)");
key = scanner.next().charAt(0);//接收一個字符
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("輸出一個數(shù)");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': //取出數(shù)據(jù)
try {
int res = queue.getQueue();
System.out.printf("取出的數(shù)據(jù)是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': //查看隊列頭的數(shù)據(jù)
try {
int res = queue.headQueue();
System.out.printf("隊列頭的數(shù)據(jù)是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': //退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
// 使用數(shù)組模擬一個隊列：ArrayQueue類
class ArrayQueue{
private int maxSize;// 數(shù)組最大的容量
private int front; // 隊列頭
private int rear; // 對列尾
private int[] arr; // 該數(shù)組用于模擬隊列存放的數(shù)據(jù)
// 創(chuàng)建隊列構(gòu)造器
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize ];
front = -1;// 指向隊列頭部，分析出目前初始化的 front 是指向隊列頭的前一個位置
rear = -1; // 指向隊列尾部巨税，意思就是隊列最后一個數(shù)據(jù)的位置
}
// 判斷隊列是否滿
public boolean isFull() {
return rear == maxSize-1;// 隊列尾 == 數(shù)組的最后一個數(shù)據(jù)
}
// 判斷你隊列是否為空
public boolean isEmpty() {
return front == rear;// 頭尾相等蟋定，說明沒數(shù)據(jù)
}
// 添加數(shù)據(jù)到隊列
public void addQueue(int n) {
// 判斷隊列是否滿
if(isFull()) {
System.out.println("隊列已滿,無法添加數(shù)據(jù)~~~~");
return;
}
rear++; // 讓 rear 后移
arr[rear] = n;
}
// 獲取隊列數(shù)據(jù)(出隊列)
public int getQueue() {
// 判斷隊列是否為空
if(isEmpty()) {
// 通過異常拋出 null
throw new RuntimeException("隊列為空，無法取數(shù)據(jù)~~~");
}
front++;// front后移
int result = arr[front];
arr[front] = 0;// 此時取出的值 位置存放的為0
return result;
}
// 顯示隊列的所有數(shù)據(jù)
public void showQueue() {
// 判空
if(isEmpty()) {
System.out.println("隊列為空,無法顯示數(shù)據(jù)~~~~");
return;
}
// 遍歷
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n",i,arr[i]);
}
}
// 顯示頭隊列垢夹，而非取出
public int headQueue() {
// 判空
if (isEmpty()) {
// 通過異常拋出 null
throw new RuntimeException("隊列為空溢吻，無法取數(shù)據(jù)~~~");
}
// 顯示
return arr[front+1];// 這邊加一的原因是一開始，初始化指向的是隊列頭的前一個
}
}
5、此隊列出現(xiàn)的問題和優(yōu)化：
1促王、目前設(shè)計的隊列只能使用一次(因為數(shù)組只能有一次)犀盟，沒有達到復(fù)用效果
2、將此數(shù)組用算法改進蝇狼，成一個環(huán)形隊列阅畴，取模 %
6、環(huán)形隊列設(shè)計思路：參考之一(實現(xiàn)方式有很多)
- front 變量調(diào)整： front 就指向隊列的第一個元素, 也就是說 arr[front] 就是隊列的第一個元素
front 的初始值 = 0 (之前的是 front +1 才是第一個元素迅耘，初始值 -1)- rear 變量的調(diào)整：rear 指向隊列的最后一個元素的后一個位置. 因為希望空出一個空間做為約定.
rear 的初始值 = 0 (之前的是 rear 就是最后一個元素贱枣，現(xiàn)在是 rear -1 才是最后一個元素，初始值 -1 )- 當隊列滿時颤专，公式是 (rear + 1) % maxSize == front (腿上面是頭時纽哥，你就沒法再被拉長了)
- 對隊列為空的條件， rear == front 空 (你的 頭距離地面 20cm 栖秕，你的腿也是 春塌，那么你的肉體就不存在了)
- 當我們這樣分析， 隊列中有效的數(shù)據(jù)的個數(shù) (rear + maxSize - front) % maxSize
- 關(guān)于第五點的公式推導(dǎo)簇捍，如果非環(huán)形隊列有效個數(shù)是 rear-front只壳。那么是不是就很好理解了
7、環(huán)形隊列測試和代碼實現(xiàn)
package com.kk.datastructure.queue;
import java.util.Scanner;
/**
* title: 環(huán)形隊列實現(xiàn)
* @author 阿K
* 2020年11月22日 下午3:50:46
*/
public class CircleArrayQueueDemo {
public static void main(String[] args) {
//創(chuàng)建一個隊列
CircleArrayQueue queue = new CircleArrayQueue(4);// 此處有效數(shù)據(jù)為3
char key = ' '; //接收用戶輸入
Scanner scanner = new Scanner(System.in);//
boolean loop = true;
//輸出一個菜單
while (loop) {
System.out.println("s(show): 顯示隊列");
System.out.println("e(exit): 退出程序");
System.out.println("a(add): 添加數(shù)據(jù)到隊列");
System.out.println("g(get): 從隊列取出數(shù)據(jù)");
System.out.println("h(head): 查看隊列頭的數(shù)據(jù)");
key = scanner.next().charAt(0);//接收一個字符
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("輸出一個數(shù)");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': //取出數(shù)據(jù)
try {
int res = queue.getQueue();
System.out.printf("取出的數(shù)據(jù)是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': //查看隊列頭的數(shù)據(jù)
try {
int res = queue.headQueue();
System.out.printf("隊列頭的數(shù)據(jù)是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': //退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
//使用數(shù)組模擬一個環(huán)形隊列：CArrayQueue類
class CircleArrayQueue{
private int maxSize;// 數(shù)組最大的容量
// front 就指向隊列的第一個元素, 也就是說 arr[front] 就是隊列的第一個元素
private int front;
// rear 指向隊列的最后一個元素的后一個位置
private int rear;
private int[] arr;
// 創(chuàng)建隊列構(gòu)造器
public CircleArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[arrMaxSize];
// front rear 默認值為0暑塑，聲明的默認值也為0吼句，既不需要重復(fù)賦值
}
// 判斷隊列是否滿
public boolean isFull() {
return (rear + 1)% maxSize == front;
}
// 判斷你隊列是否為空
public boolean isEmpty() {
return front == rear;// 頭尾相等，說明沒數(shù)據(jù)
}
// 添加數(shù)據(jù)到隊列
public void addQueue(int n) {
// 判斷隊列是否滿
if (isFull()) {
System.out.println("隊列已滿,無法添加數(shù)據(jù)~~~~");
return;
}
// 直接插入進來
arr[rear] = n;
// rear 后移, 得考慮取模(環(huán)形)
rear = (rear + 1) % maxSize;
}
// 獲取隊列數(shù)據(jù)(出隊列)
public int getQueue() {
// 判斷隊列是否為空
if (isEmpty()) {
// 通過異常拋出 null
throw new RuntimeException("隊列為空事格，無法取數(shù)據(jù)~~~");
}
// 分析得 front 是指向隊列的第一個元素
// 先 將 front 值保存到臨時變量惕艳，用于返回
// 然后再進行后移
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
// 顯示隊列的所有數(shù)據(jù)
public void showQueue() {
// 判空
if (isEmpty()) {
System.out.println("隊列為空,無法顯示數(shù)據(jù)~~~~");
return;
}
// 遍歷(從頭隊列 到 都隊列 + 有效數(shù)據(jù)個數(shù))
for (int i = front; i < front+size(); i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
}
// 計算出有效數(shù)據(jù)個數(shù)
public int size() {
return (rear - front + maxSize) % maxSize;
}
// 顯示頭隊列，而非取出
public int headQueue() {
// 判空
if (isEmpty()) {
// 通過異常拋出 null
throw new RuntimeException("隊列為空驹愚，無法取數(shù)據(jù)~~~");
}
// 顯示
return arr[front];
}
}
