溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
Java編程內功之怎么實現隊列，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。
基本介紹
隊列是一個有序列表,可以用數組或者鏈表來實現
遵循先入先出的原則,即先存入隊列的數據,要先取出.后存入的要后取出
數組模擬隊列
隊列本身是有序列表,若使用數組的結構來存儲隊列的數據,則隊列數組的聲明如下圖,其中maxSize是該隊列的最大容量.
因為隊列的輸入\輸出是分別從前后端來處理,因此需要兩個變量front及rear分別記錄隊列前后端的下標,front會隨著數據輸出而改變,而rear則是隨著數據輸入而改變.
代碼案例
package com.structures.queue; import java.util.Scanner; public class ArrayQueueDemo { public static void main(String[] args) { ArrayQueue arrayQueue = 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):添加數據到隊列"); System.out.println("g(get):從隊列取出數據"); System.out.println("h(head):查看隊列頭的數據"); key = scanner.next().charAt(0); switch (key) { case 's': arrayQueue.showQueue(); break; case 'a': System.out.println("輸入一個整數"); int value = scanner.nextInt(); arrayQueue.addQueue(value); break; case 'g': try { int queue = arrayQueue.getQueue(); System.out.printf("取出的數據是%d", queue); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 'e': scanner.close(); loop = false; break; case 'h': try { int head = arrayQueue.headQueue(); System.out.printf("取出隊列頭的數據是%d", head); }catch (Exception e){ System.out.println(e.getMessage()); } default: break; } } System.out.println("程序退出"); } } //使用數組模擬隊列-編寫一個ArrayQueue類 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 boolean isFull() { return rear == maxSize - 1; } //判斷隊列是否為空 public boolean isEmpty() { return rear == front; } //添加數據到隊列 public void addQueue(int n) { if (isFull()) { System.out.println("隊列不能加入數據"); return; } rear++;//讓rear 后移 arr[rear] = n; } //獲取隊列數據,出隊列 public int getQueue() { if (isEmpty()) { throw new RuntimeException("隊列為空,不能取數據"); } front++; return arr[front]; } //顯示隊列所有數據 public void showQueue() { if (isEmpty()) { System.out.println("隊列為空,沒有數據"); } for (int i = 0; i < this.arr.length; i++) { System.out.printf("arr[%d]=%d\n", i, arr[i]); } } //顯示隊列的頭數據,注意不是取數據 public int headQueue() { if (isEmpty()) { throw new RuntimeException("隊列為空,沒有數據"); } return arr[front + 1]; } }問題分析
鴻蒙官方戰略合作共建——HarmonyOS技術社區
目前這個數組使用一次就不能用,沒有達到復用的效果.
將這個數組使用算法,改進成一個環形的隊列:取模%
改進成環形隊列的思路分析
鴻蒙官方戰略合作共建——HarmonyOS技術社區
front變量的含義做一個調整:front 就指向隊列的第一個元素,也就是arr[front]就是隊列的第一個元素,front的初始值=0
rear變量的含義做一個調整:rear 指向隊列的最后一個元素的后一個位置,因為希望空出一個空間作為約定.rear初始值=0
當隊列滿時,條件是(rear+1)%maxSize = front.
當隊列為空時條件,rear == front 空.
當我們這樣分析,隊列中有效的數據的個數=(rear+maxSize-front)%maxSize.
環形隊列代碼案例
package com.structures.queue; import java.util.Scanner; public class CircleArrayQueue { public static void main(String[] args) { CircleArray arrayQueue = new CircleArray(4);//這里設置4,其隊列的有效數據最大是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):添加數據到隊列"); System.out.println("g(get):從隊列取出數據"); System.out.println("h(head):查看隊列頭的數據"); key = scanner.next().charAt(0); switch (key) { case 's': arrayQueue.showQueue(); break; case 'a': System.out.println("輸入一個整數"); int value = scanner.nextInt(); arrayQueue.addQueue(value); break; case 'g': try { int queue = arrayQueue.getQueue(); System.out.printf("取出的數據是%d", queue); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 'e': scanner.close(); loop = false; break; case 'h': try { int head = arrayQueue.headQueue(); System.out.printf("取出隊列頭的數據是%d", head); }catch (Exception e){ System.out.println(e.getMessage()); } default: break; } } System.out.println("程序退出"); } } class CircleArray { //表示數組最大容量 private int maxSize; //front變量的含義做一個調整:front 就指向隊列的第一個元素,也就是arr[front]就是隊列的第一個元素,front的初始值=0 private int front; //rear變量的含義做一個調整:rear 指向隊列的最后一個元素的后一個位置,因為希望空出一個空間作為約定.rear初始值=0 private int rear; //用于存放數據,模擬隊列 private int[] arr; public CircleArray(int arrMaxSize) { maxSize = arrMaxSize; arr = new int[maxSize]; } //判斷隊列是否滿 public boolean isFull() { return (rear + 1) % maxSize == front; } //判斷隊列是否為空 public boolean isEmpty() { return rear == front; } //添加數據到隊列 public void addQueue(int n) { if (isFull()) { System.out.println("隊列滿,隊列不能加入數據"); return; } //直接將數據加入 arr[rear] = n; //將rear后移,這里必須考慮取模 rear = (rear + 1) % maxSize; } //獲取隊列數據,出隊列 public int getQueue() { if (isEmpty()) { throw new RuntimeException("隊列為空,不能取數據"); } //這里需要分析front是指向隊列的第一個元素, //1.先把front對應的值保存到一個臨時變量, //2.將front后移,考慮取模 //3.將臨時保存的變量返回 int value = arr[front]; front = (front + 1) % maxSize; return value; } //顯示隊列所有數據 public void showQueue() { if (isEmpty()) { System.out.println("隊列為空,沒有數據"); } //從front開始遍歷 for (int i = front; i < front + size(); i++) { System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]); } } //求出當前隊列有效數據的個數 public int size() { return (rear + maxSize - front) % maxSize; } //顯示隊列的頭數據,注意不是取數據 public int headQueue() { if (isEmpty()) { throw new RuntimeException("隊列為空,沒有數據"); } return arr[front]; } }看完上述內容，你們掌握Java編程內功之怎么實現隊列的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
