佇列介紹
佇列是一個有序串列，可以用陣列或是鏈表來實作， 遵循先入先出的原則，
即：先存入佇列的資料，要先取出，后存入的要后取出 示意圖：(使用陣列模擬佇列示意圖)
陣列模擬佇列
佇列本身是有序串列，若使用陣列的結構來存盤佇列的資料，則佇列陣列的宣告如下圖, 其中 maxSize 是該佇列的最大容量，
因為佇列的輸出、輸入是分別從前后端來處理，因此需要兩個變數 front及 rear分別記錄佇列前后端的下標，front 會隨著資料輸出而改變，而 rear則是隨著資料輸入而改變，
如圖所示:
當我們將資料存入佇列時稱為”addQueue”，
addQueue 的處理需要有兩個步驟：
思路分析 將尾指標往后移：
rear+1 , 當front == rear 【空】 若尾指標 rear 小于佇列的最大下標 maxSize-1，則將資料存入 rear所指的陣列元素中，否則無法存入資料，
rear == maxSize - 1[佇列滿] 代碼實作 問題分析并優化
代碼實作
package com.lin.queue_0131; import java.util.Scanner; public class Array_Queue { public static void main(String[] args) { ArrayQueue arrayQueue = new ArrayQueue(4); Scanner scanner = new Scanner(System.in); char c; while(true) { System.out.println("------------------------------"); System.out.println("|"); System.out.println("|"); System.out.println("------------------------------"); System.out.println("-1 s(show):顯示佇列, -2 e(exit)：退出程式, -3 a(add)：添加資料到佇列, -4 g(get)：獲取佇列的資料, -5 h(head):查看佇列頭資料 "); System.out.println("請輸入以上提示字符："); c = scanner.next().charAt(0); switch (c) { case 's': arrayQueue.showQueue(); break; case 'e': System.exit(0); break; case 'a': System.out.println("請輸入添加資料："); int n = scanner.nextInt(); arrayQueue.addQueue(n); break; case 'g': try { System.out.println("出隊：" + arrayQueue.getQueue()); } catch (NullQueueException e) { System.err.println(e.getMessage()); } break; case 'h': try { System.out.println("頭資料：" + arrayQueue.headQueue()); } catch (NullQueueException e) { System.err.println(e.getMessage()); } break; default: break; } } } } class ArrayQueue{ private int fornt; private int rear; private int maxSize; private int[] arr; // 創建佇列構造器 public ArrayQueue(int maxSize){ this.arr = new int[maxSize]; this.maxSize = maxSize; this.rear = -1; // 指向隊尾的資料 this.fornt = -1; // 指向佇列頭的前一位置 } // 判斷佇列是否已滿 public boolean isFull() { return rear == (maxSize - 1); } // 判斷佇列是否為空 public boolean isEmpty() { return rear == fornt; } // 入隊 public void addQueue(int n) { if(!isFull()) { arr[++rear] = n; System.out.println("添加成功！"); } else { System.out.println("佇列已滿！"); } } // 出隊 public int getQueue() throws NullQueueException { if(isEmpty()) { throw new NullQueueException("佇列為空！"); // 自定義例外 } int arrNum = arr[++fornt]; arr[fornt] = 0; return arrNum; } // 遍歷佇列 public void showQueue() { if(isEmpty()) { System.out.println("佇列為空，無法輸出資料！"); return; } for (int i = 0; i < arr.length; i++) { System.out.print("arr[" + i + "] = " + arr[i] + "\t"); } System.out.println(); } // 顯示佇列的頭資料 public int headQueue() throws NullQueueException { if(isEmpty()) { throw new NullQueueException("佇列為空！"); // 自定義例外 } return arr[fornt +1]; } }
注意：沒有優化的代碼陣列只能用一次，即使佇列為空，也無法添加資料，
優化后的代碼
環形佇列調整思路（其中的一種辦法）：
front變數的含義：front指向佇列的第一個元素，也就是說arr[front]就是佇列的第一個元素，之前的front是指向佇列頭元素的前一個位置，初始值為0，
rear變數的含義：rear指向佇列的最后一個元素的后一個位置，希望空出一個空間作為約定，初始值為0，
當佇列滿時，條件是(rear + 1)%maxSize == front，
當佇列為空時，條件是rear == front，
有效個數：(rear + maxSize - front)%maxSize，
package com.lin.queue_0131; import java.util.Scanner; public class ArrayQueuePuls { public static void main(String[] args) { ArrayQueue2 arrayQueue2 = new ArrayQueue2(4); Scanner scanner = new Scanner(System.in); char c; while(true) { System.out.println("------------------------------"); System.out.println("|"); System.out.println("|"); System.out.println("------------------------------"); System.out.println("-1 s(show):顯示佇列, -2 e(exit)：退出程式, -3 a(add)：添加資料到佇列, -4 g(get)：獲取佇列的資料, -5 h(head):查看佇列頭資料,-1 printFornt,-2 printRear "); System.out.println("請輸入以上提示字符："); c = scanner.next().charAt(0); switch (c) { case 's': arrayQueue2.showQueue(); break; case 'e': System.exit(0); break; case 'a': System.out.println("請輸入添加資料："); int n = scanner.nextInt(); arrayQueue2.addQueue(n); break; case 'g': try { System.out.println("出隊：" + arrayQueue2.getQueue()); } catch (NullQueueException e) { System.err.println(e.getMessage()); } break; case 'h': try { System.out.println("頭資料：" + arrayQueue2.headQueue()); } catch (NullQueueException e) { System.err.println(e.getMessage()); } break; case '1': arrayQueue2.printFront(); break; case '2': arrayQueue2.printRear(); break; default: break; } } } } class ArrayQueue2{ private int fornt; private int rear; private int maxSize; private int[] arr; // 創建佇列構造器 public ArrayQueue2(int maxSize){ this.arr = new int[maxSize]; this.maxSize = maxSize; this.rear = 0; // 指向隊尾的資料 this.fornt = 0; // 指向佇列頭的前一位置 } // 判斷佇列是否已滿 public boolean isFull() { return (rear + 1)%maxSize == fornt; } // 判斷佇列是否為空 public boolean isEmpty() { return rear == fornt; } // 入隊 public void addQueue(int n) { if(!isFull()) { arr[rear] = n; rear = (rear + 1)%maxSize; System.out.println("添加成功！"); } else { System.out.println("佇列已滿！"); } } // 出隊 public int getQueue() throws NullQueueException { if(isEmpty()) { throw new NullQueueException("佇列為空！"); // 自定義例外 } int arrNum = arr[fornt]; fornt = (fornt + 1)%maxSize; return arrNum; } // 遍歷佇列 public void showQueue() { if(isEmpty()) { System.out.println("佇列為空，無法輸出資料！"); return; } for (int i = fornt; i < fornt + numSize(); i++) { System.out.print("arr[" + i%maxSize + "] = " + arr[i%maxSize] + "\t"); } System.out.println(); } public int numSize() { return (rear + maxSize - fornt)%maxSize; // (rear + maxSize - fornt)%maxSize環形佇列元素的實際個數 } // 顯示佇列的頭資料 public int headQueue() throws NullQueueException { if(isEmpty()) { throw new NullQueueException("佇列為空！"); // 自定義例外 } return arr[fornt]; } public void printFront() { System.out.println(this.fornt); } public void printRear() { System.out.println(this.rear); } }
雖然陣列size為4，但容量只有3
最后，fornt單詞寫錯了，應該是front，
僅供參考，有錯誤還請指出！
有什么想法，評論區留言，互相指教指教，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/255051.html
標籤：Java
上一篇：繼承