Java數(shù)組模擬隊(duì)列
簡介
本文主要內(nèi)容在Java代碼中用數(shù)組模擬一個(gè)隊(duì)列出來，這里只簡要一提，不過多的介紹隊(duì)列基本概念
隊(duì)列是一種特殊的線性表，特點(diǎn)是先進(jìn)先出。
和棧相似，它們的操作都是受限的。
這里要說的隊(duì)列，只有兩種操作，插入一個(gè)數(shù)據(jù)稱為入隊(duì)，刪除一個(gè)數(shù)據(jù)稱為出隊(duì)，并且只能從隊(duì)尾插入數(shù)據(jù)，只能在隊(duì)頭刪除數(shù)據(jù)。
隊(duì)列的數(shù)組實(shí)現(xiàn)
從百度百科中可以看到對隊(duì)列的描述
簡要來說，實(shí)現(xiàn)一個(gè)隊(duì)列，本質(zhì)上需要一片連續(xù)的存儲(chǔ)空間，可以是靜態(tài)分配，也可以動(dòng)態(tài)申請
數(shù)組呢，正好就可以貼合這個(gè)要求，靜態(tài)分配一段定長的連續(xù)內(nèi)存空間
除此之外，還需要兩個(gè)指針，一個(gè)指向隊(duì)頭，一個(gè)指向隊(duì)尾
入隊(duì)操作是在隊(duì)尾添加數(shù)據(jù)，所以要在指向隊(duì)尾的指針后一個(gè)位置添加數(shù)據(jù)，并且將指針指向新的隊(duì)尾，也就是尾指針后移
出隊(duì)操作是取出并刪除隊(duì)頭的數(shù)據(jù)，其實(shí)刪除數(shù)據(jù)的操作，就是在指向隊(duì)頭的指針處取得數(shù)據(jù)返回，然后將隊(duì)頭指針后移即可
我們發(fā)現(xiàn)，在操作數(shù)據(jù)的同時(shí)，需要伴隨著指針的移動(dòng)
分析一把，如果將頭指針正好指向當(dāng)前隊(duì)頭，尾指針正好指向當(dāng)前隊(duì)尾
注意：完整實(shí)現(xiàn)一個(gè)隊(duì)列，需要有入隊(duì)、出隊(duì)、初始化三個(gè)操作。但用數(shù)組實(shí)現(xiàn)隊(duì)列，因?yàn)榇鎯?chǔ)空間是靜態(tài)分配的定長空間，意味著隊(duì)列容量有最大值，所以還需要判斷隊(duì)列滿和隊(duì)列空兩種情況
1.入隊(duì)：將尾指針后移一下，然后，將數(shù)據(jù)放到尾指針位置；（需要先判斷隊(duì)列是否還沒滿）
2.出隊(duì)：將頭指針位置的數(shù)據(jù)取出，然后，后移頭指針；（需要先判斷是否有數(shù)據(jù)可以出隊(duì)）
3.判斷隊(duì)列的空滿問題：
這種方式下，在操作出入隊(duì)之前，尾指針正好指向隊(duì)尾，頭指針正好指向隊(duì)頭
所以，尾指針數(shù)值 - 頭指針數(shù)值 +1 = 當(dāng)前隊(duì)列數(shù)據(jù)量，我們判斷這個(gè)計(jì)算出的當(dāng)前隊(duì)列數(shù)據(jù)量，如果等于最大容量就說明隊(duì)列滿了，如果等于0就說明隊(duì)列是空的
4.初始化隊(duì)列：
初始化隊(duì)列時(shí)，首先分析初始化的隊(duì)列是空的，根據(jù)判斷隊(duì)列為空的方式，發(fā)現(xiàn)，當(dāng)隊(duì)列空時(shí)，頭指針在尾指針的后一個(gè)位置；再分析第一個(gè)入隊(duì)的數(shù)據(jù)要放在數(shù)組的第一個(gè)位置，也就是索引0的位置，而入隊(duì)時(shí)先將尾指針后移，再將數(shù)據(jù)放在尾指針位置，所以初始化尾指針要指向-1；而頭指針要在尾指針后一位，也就是初始化頭指針指向0。
5.改進(jìn)：
這樣的方式實(shí)現(xiàn)隊(duì)列后，會(huì)發(fā)現(xiàn)指針一直在后移，添加到最大容量后，指針就會(huì)超出邊界，即便數(shù)據(jù)都已經(jīng)出列了，也無法再入隊(duì)，所以其實(shí)當(dāng)指針移動(dòng)到最大容量位置時(shí)，再向后移應(yīng)該是移動(dòng)到第一個(gè)，讓隊(duì)列首尾相連變成一個(gè)環(huán)狀
實(shí)現(xiàn)這個(gè)的方式是，每次在移動(dòng)指針后進(jìn)行一次（指針%最大容量）的取余運(yùn)算
但這樣會(huì)出現(xiàn)問題，原先的計(jì)算當(dāng)前數(shù)據(jù)量公式就不再正確，還需要將（結(jié)果%最大容量）進(jìn)行取余運(yùn)算
也可以放任指針持續(xù)后移，在取數(shù)據(jù)和插入數(shù)據(jù)的時(shí)候?qū)χ羔樔∮?，這樣不影響計(jì)算數(shù)據(jù)量公式
實(shí)現(xiàn)方式其實(shí)并不唯一，取決于你對頭尾指針的設(shè)定
下面的代碼演示中，設(shè)定為：頭指針指向隊(duì)列頭的前一個(gè)數(shù)據(jù)，尾指針指向隊(duì)列尾
區(qū)別就是：
1.判斷隊(duì)列容量：尾指針-頭指針正好等于隊(duì)列容量，不需要加一
2.入隊(duì)出隊(duì)操作都是先移動(dòng)指針，再操作數(shù)據(jù)
眼觀千遍，不如手動(dòng)一遍
讀者朋友可以看完我的實(shí)現(xiàn)代碼后，自行根據(jù)上面分析與代碼不同的思路實(shí)現(xiàn)一遍，當(dāng)做一個(gè)小練習(xí)
class ArrayQueueEntity{
/**
* 數(shù)組最大容量
*/
private final int maxSize;
/**
* 約定指向隊(duì)列頭的前一個(gè)位置
*/
private int front;
/**
* 指向隊(duì)列尾
*/
private int rear;
/**
* 模擬隊(duì)列用于存放數(shù)據(jù)的數(shù)組
*/
private final int[] arr;
/**
* 構(gòu)造器，創(chuàng)建隊(duì)列(初始化隊(duì)列)
* @param arrMaxSize 隊(duì)列最大容量
*/
public ArrayQueueEntity(int arrMaxSize){
maxSize = arrMaxSize;
arr = new int[maxSize];
//初始化時(shí)頭指針指向第一個(gè)數(shù)據(jù)的前一個(gè)（其實(shí)表示這個(gè)位置是上一次出列的數(shù)據(jù)位置）
front = -1;
//初始化時(shí)尾指針需要指向當(dāng)前最后一個(gè)數(shù)據(jù)的索引，但初始化隊(duì)列為空找不到隊(duì)尾，所以根據(jù)空隊(duì)列判斷尾指針-頭指針=0，設(shè)置為-1
rear = -1;
}
/**
* 判斷隊(duì)列是否是滿的
* @return true表示隊(duì)列滿了，false表示隊(duì)列沒滿
*/
public boolean isFull(){
return rear - front >= maxSize;
}
/**
* 判斷隊(duì)列是否為空
* @return true表示為空，false表示不為空
*/
public boolean isEmpty(){
return rear - front == 0;
}
/**
* 添加數(shù)據(jù)到隊(duì)列
* @param data 要添加的數(shù)據(jù)
*/
public void addQueue(int data){
//判斷隊(duì)列是否已滿
if (!isFull()){
//隊(duì)列沒滿，添加數(shù)據(jù)
//隊(duì)列尾指針后移
rear++;
//在尾指針處添加數(shù)據(jù)(指針位置都一直在后移，所以要對數(shù)組容量取余，模擬成環(huán)形隊(duì)列)
arr[rear%maxSize] = data;
}else {
//隊(duì)列滿了輸出提示
System.out.println("隊(duì)列滿，不能加入數(shù)據(jù)");
}
}
/**
* 獲取隊(duì)列數(shù)據(jù)/出隊(duì)列
* @return 出隊(duì)列的數(shù)據(jù)
*/
public int getQueue(){
//先判斷隊(duì)列是否為空
if (isEmpty()){
throw new RuntimeException("隊(duì)列為空");
}
//不為空，取數(shù)據(jù)
//頭指針后移一下，指向需要出列的數(shù)據(jù)
front++;
//讓指針位置數(shù)據(jù)出列即可
return arr[front%maxSize];
}
/**
* 打印當(dāng)前隊(duì)列的所有數(shù)據(jù)
*/
public void printQueue(){
System.out.println("正在打印當(dāng)前隊(duì)列......");
//先判斷隊(duì)列是否為空
if (!isEmpty()){
//不為空就遍歷打印，從頭指針的下一個(gè)遍歷到尾指針
for (int i = front+1; i <= rear; i++) {
System.out.println(i+":"+arr[i%maxSize]);
}
}else {
System.out.println("隊(duì)列中沒有數(shù)據(jù)");
}
}
}
模擬上面代碼，完成小練習(xí)后，可以用下面這個(gè)主方法來測試一下隊(duì)列
public static void main(String[] args) {
//初始化隊(duì)列——最大容量為3
ArrayQueueEntity queue = new ArrayQueueEntity(3);
//接收用戶輸入
String key;
Scanner scanner = new Scanner(System.in);
//讓系統(tǒng)在用戶主動(dòng)退出之前一直運(yùn)行，并能夠輸出一個(gè)指引菜單
boolean loop = true;
while (loop){
System.out.println("s(show):顯示當(dāng)前隊(duì)列狀況");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加數(shù)據(jù)到隊(duì)列");
System.out.println("g(get):從隊(duì)列取出數(shù)據(jù)");
key = scanner.next();
switch (key){
case "s":
queue.printQueue();
break;
case "e":
loop=false;
break;
case "a":
if (queue.isFull()){
System.out.println("隊(duì)列已滿，清先出列一些數(shù)據(jù)再試");
break;
}
System.out.println("請輸入要入隊(duì)的數(shù)字：");
int data = scanner.nextInt();
queue.addQueue(data);
break;
case "g":
if (queue.isEmpty()){
System.out.println("隊(duì)列為空，沒有數(shù)據(jù)可以出列，請先嘗試添加數(shù)據(jù)入列");
break;
}
System.out.println("出列成功，出列數(shù)據(jù)為："+queue.getQueue());
break;
default:
System.out.println("請根據(jù)菜單提示輸入正確指令");
}
}
}
