本篇文章主要講述了使用數組實現環形隊列的思路以及具體代碼

我們先來看下百科的解釋：隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。總結起來兩點：1.一種線性表2.添加操作只能在表尾，刪除操作在表頭（先進先出）

初始化一個大小固定的數組，并將頭指針，尾指針都指向下表為0的位置，但其實這種初始化頭指針指向的是隊首，尾指針指向的是隊尾的后一個元素。

往隊列里添加元素，尾指針后移一位。

一直添加直到隊列滿

這個時候尾指針已經出現在數組下標外了

每消費一個隊列元素，頭指針指向的元素出隊，并且后移一位

再消費兩個

這個時候我們想往隊列里繼續添加元素，尾指針后移，然后發現出現了假溢出的情況，因為尾指針無法再向后移動，而隊列實際上并沒有滿，我們又無法繼續往隊列里添加數據。這個時候其實有兩種解決方案。方案一：我們每消費一個元素，其后面的元素都整體往前移動一位，就像我們生活中排隊打飯一樣，后面的人都往前挪一挪。但這種方案帶來的后果是，帶來的時間開銷太大，因為基本上要操作所有的元素，所以這種方案不可行。方案二：尾指針在指向下表為最后一個元素時，再添加元素，如果還有空位，就將尾指針重新指向0，頭指針在取到下表數組末尾時，如果前面還有元素，頭指針也指向0，這就是我們說的環形隊列。

尾指針重新指向零

再添加一個元素

連續消費三個元素，如果前面還有元素，頭指針也指向0

這個時候我們發現那個原來熟悉的隊列又回來了。

/** * description:數組實現環形隊列 * author: xiaowang * */public class MyQueue<E> { // 隊列最大個數 private int size; // 元素真實個數 private int number; // 頭指針，指向隊列的第一個元素即隊頭 private int front; // 尾指針，指向隊尾的后一個元素(非隊尾) private int rear; // 隊列具體值 private Object[] values; // 隊列滿標記，當隊列是滿的時候為true private boolean isFullFlag; /**構造器*/ public MyQueue(int size){if (size<0){ throw new RuntimeException('初始化隊列時，隊列最大元素個數不能為負');}this.front = 0;this.rear = 0;this.number = 0;this.isFullFlag = false;this.size = size;this.values = new Object[size]; } /**往隊列里添加元素 添加成功返回true 失敗返回false*/ public boolean addToQueue(E e){// 判斷隊列是否已經滿了if (isFullFlag){ System.out.println('隊列已滿,無法繼續添加元素'); return false;}// 添加元素values[rear] = e;// 元素個數加一number++;// 尾指針后移一位，若已經指向數組最后的下表，則重新指向0if (rear == size-1){ rear = 0;}else{ rear++;}// 添加完這個元素，判斷隊列是否已經滿了，若滿則標記為trueif (rear==front){ isFullFlag = true;}return true; } /**從隊列里取出數據，隊頭數據*/ public E getFromQueue(){// 判斷隊列是否為空if (number==0||size==0){ System.out.println('隊列為空，無法從隊列中獲取數據'); return null;}// 臨時變量E e = (E) values[front];// 隊頭置空values[front] = null;// 個數減一number--;// 頭指針后移，若已經指向數組最后的下表，則重新指向0if (front==size-1){ front = 0;}else { front++;}// 取隊列之前若是滿的狀態，則更新狀態if (isFullFlag){ isFullFlag = false;}return e; } /**獲取目前有幾個元素正在進行排隊*/ public int getNumber(){return number; } /**獲取隊列的最大個數*/ public int getSize(){return size; } /**查看隊列在數組里保存的詳細情況*/ public String toString(){StringBuffer valueStr = new StringBuffer();valueStr.append('[');for (int i = 0; i < size; i++) { if (i!=size-1){valueStr.append(values[i]+','); }else{valueStr.append(values[i]+']'); }}return valueStr.toString(); }}

測試代碼

public class TestQueue { public static void main(String[] args) {MyQueue<String> queue = new MyQueue<String>(5);Scanner scanner = new Scanner(System.in);Scanner scanner2 = new Scanner(System.in);boolean isCan = true;while (isCan){ System.out.println('歡迎來到小王排隊系統，您可以使用以下功能。n添加：1；取出：2；展示：3；獲取排隊個數：4；退出：0。'); int flag = scanner.nextInt(); switch (flag){case 1 : System.out.println('請輸入一個數據：'); String data = scanner2.nextLine(); boolean isSuccess = queue.addToQueue(data); if (isSuccess){System.out.println('添加成功~~~'); } break;case 2 : String dataFromQueue = queue.getFromQueue(); if (dataFromQueue!=null){System.out.println('本次取出的數據為：'+dataFromQueue); } break;case 3 : System.out.println('隊列詳情為：n'+queue.toString()); break;case 4 : System.out.println('目前有'+queue.getNumber()+'個元素正在進行排隊'); break;default: isCan = false; System.out.println('已退出...'); break; }} }}總結

到此這篇關于java中用數組實現環形隊列的示例代碼的文章就介紹到這了,更多相關java 數組環形隊列內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！