K60 Pro官方停產 第三方瞬間漲價
雖然沒有官方宣布，但Redmi的一些高管也已經透露了，Redmi K60 Pro已經停產且不會補貨，這一切都是為了即將到來的K60 Ultra鋪路，屬于廠家的正常操作。但有意思的是該機在停產之后
隊列是一種重要的數據結構，它按照“先入先出”（FIFO）的原則管理數據。本文將介紹隊列的概念、應用場景，以及如何使用數組實現普通隊列和環形隊列。
隊列（Queue）是一種常見的數據結構，它是一個線性數據結構，按照先入先出（FIFO，First-In-First-Out）的原則來管理數據。
注意，先入先出的原則就意味著最早進入隊列的元素將最先被取出，而最后進入隊列的元素將最后被取出，類似于排隊等候服務的行為。
隊列可以使用數組或鏈表來實現，具體實現方式因應用需求而異。
隊列支持兩種主要的操作，即入隊（Enqueue）和出隊（Dequeue）。
隊列的應用場景有很多，比如：
隊列在計算機科學和實際應用中非常有用，因為它們提供了一種有效的方法來管理和調度數據或任務，以確保按照特定的順序進行處理。
下面，我們用數組來模擬一個簡單的隊列數據結構。
首先給出類的定義：
class ArrayQueue { private int maxSize; private int front; private int rear; private int[] data; ArrayQueue(int queueMaxSize) { maxSize = queueMaxSize; // 隊列的最大容量 data = new int[maxSize]; // 存放隊列的數據 front = -1; // 指向隊列頭的前一個位置 rear = -1; // 直接指向隊列尾部 } // ... 方法定義}在這里，ArrayQueue 是一個隊列類，使用數組作為內部數據存儲。它包括最大容量（maxSize）、隊列頭（front）、隊列尾（rear）和一個整數數組（data）來存放隊列的數據。
構造函數 ArrayQueue 接受一個整數參數 queueMaxSize，表示隊列的最大容量。初始化時，隊列的頭（front）和尾都（rear）被置為-1，表示隊列為空。
需要注意這里的定義，在這里，front 變量指的是指向隊列首元素的前一個位置，而 rear 變量則指向隊列的尾部元素，即最后一個元素。
因此，初始隊列的結構圖如下：
public boolean isEmpty() { return rear == front;}public boolean isFull() { return rear == maxSize - 1;}// 入隊操作，添加數據到隊尾public void enQueue(int num) { if(isFull()) { System.out.println("隊列已滿，無法入隊"); return; } rear++; data[rear] = num;}enQueue 方法用于將數據添加到隊列的尾部。首先，它會檢查隊列是否已滿，如果是，將輸出一條錯誤消息并不執行入隊操作。如果隊列未滿，將 rear 后移，然后將數據存入隊列尾部。
再次強調一下，這里的 rear 變量用于指向隊列的最后一個數據，即隊列的尾部。
// 出隊操作，取出隊頭數據public int deQueue() { if(isEmpty()) { throw new RuntimeException("隊列為空，無法出隊"); } front++; return data[front];}deQueue 方法用于取出隊列頭部的數據。首先，它會檢查隊列是否為空，如果是，將拋出一個運行時異常。如果隊列不為空，將 front 后移，然后返回隊頭的數據。
再次強調一下，這里的 front 變量指向的是隊列頭數據的前一個位置。
// 查看隊頭數據（注意不是取出數據）public int headQueue() { if(isEmpty()) { throw new RuntimeException("隊列為空，沒有數據"); } return data[front+1];}headQueue 方法用于獲取隊列頭部的數據，但不會將其出隊。它會檢查隊列是否為空，如果是，將拋出一個運行時異常。如果隊列不為空，將返回隊頭的數據。
// 打印隊列public void showQueue() { if(isEmpty()) { System.out.println("隊列為空，沒有數據"); return; } // 簡單的遍歷隊列 for(int i = 0; i < data.length; i++) { System.out.printf("data[%d] = %d/n", i, data[i]); }}showQueue 方法用于簡單地打印隊列的所有元素。如果隊列為空，將輸出一條消息表示隊列為空。否則，它會簡單地遍歷隊列，打印每個數據元素的索引和值。
我們再來思考一個問題，雖然上述的隊列類實現了一個簡單的隊列數據結構，但仍然存在弊端。那就是數組使用一次后不能復用。
什么意思？
具體的，我們可以發現，每當隊列入隊一個數據，rear 變量就會往后移一位。每當有元素出隊，front 變量也會往后移一位。但是！一旦 rear 變量到達隊列的尾部，如果隊列頭部仍有空余的空間，就像這樣：
那么此時根據 isFull() 方法的判斷下，該隊列是滿的。因此無法再入隊。
因此我們說，對于之前的隊列簡單實現來說，一旦隊列中的數據元素被取出，對應的數組位置就不能再次使用。數據從頭部添加，從尾部取出。一旦數組被填滿，我們無法再添加新的數據，即使隊列的前面已經有一些位置被釋放出來。這就會導致內存資源浪費。
為了解決這個問題，我們考慮使用環形隊列來優化。
那什么是環形隊列？
事實上，環形隊列是一種更高效的隊列實現方式，它允許隊列在達到最大容量后繼續添加元素，以覆蓋掉隊列頭部已經被取出的數據，實現數據的循環復用。
我們通過取模運算 % 來實現環形隊列。
當我們考慮了隊列內部數據存儲資源的復用后，我們就需要對 front 和 rear 變量的含義進行一個的調整（當然不調整也行，看個人習慣）。
具體如下：
當我們這樣約定好了后，就可以開始著手編寫代碼，得到一個環形隊列。
此時判斷隊列已滿或空時，邏輯需要略微調整。
判斷環形隊列空時，條件為：(rear == front)。因為當 rear 指針等于 front 指針時，表示隊列沒有有效的元素，即隊列為空。
判斷環形隊列滿時，條件為：(rear + 1) % maxSize == front
這該怎么理解？
事實上，在含義調整后，環形隊列中的 rear 變量指向的位置實際上就是預留給下次入隊的數據存放的位置。
當有一個新的數據入隊時，rear 指向的位置就可以存儲本次入隊的數據的值，然后，rear 就會加一并取余 maxSize ，用于尋找下一個可以存儲入隊數據的位置。
因此，當(rear + 1) % maxSize 的值剛好等于 front，那么證明該環形隊列已經滿了，沒有地方可以存儲下一次入隊的值。
舉一個例子，假設 maxSize 為 3，初始時 front 和 rear 都是0：
示意圖如下：
優化后的代碼實現如下：
class CircleArrayQueue { private int maxSize; private int front; // 初始值為 0，指向隊頭數據，即首元素 private int rear; // 初始值為 0，指向隊尾數據的下一個位置 private int[] data; ArrayQueue(int queueMaxSize) { maxSize = queueMaxSize; data = new int[maxSize]; } // 判斷隊列是否為空 public boolean isEmpty() { return rear == front; } // 判斷隊列是否滿 public boolean isFull() { return (rear + 1) % maxSize == front; } // 入隊：添加數據到隊尾 public void enQueue(int num) { if(isFull()) { System.out.println("隊列已滿，無法入隊"); return; } data[rear] = num; rear = (rear + 1) % maxSize; } // 出隊，取出隊頭數據 public int deQueue() { if(isEmpty()) { throw new RuntimeException("隊列為空，無法出隊"); } int value = data[front]; front = (front + 1) % maxSize; return value; } // 顯示隊列的頭數據（不是取出數據） public int headQueue() { if(isEmpty()) { throw new RuntimeException("隊列為空，沒有數據"); } return data[front]; } // 返回環形隊列當前的元素個數 public int size() { return (rear + maxSize - front) % maxSize; } // 打印隊列 public void showQueue() { if(isEmpty()) { System.out.println("隊列為空，沒有數據"); return; } // 遍歷思路，從 data[front] 遍歷到 data[front + size] for(int i = front; i < front + size(); i++) { System.out.printf("data[%d] = %d/n", i%maxSize, data[i%maxSize]); } }}本文詳細介紹了隊列數據結構的概念和應用，包括普通隊列和環形隊列的實現。隊列是一種有序的數據結構，它在計算機科學中被廣泛應用，用于管理數據和任務的順序執行。普通隊列使用數組實現，但存在內存資源浪費的問題。為了解決這個問題，我們引入了環形隊列的概念，它允許隊列數據的循環復用，更加高效地利用內存。
本文鏈接：http://www.www897cc.com/showinfo-26-14006-0.htmlJava代碼手撕【數據結構】| 隊列的實現與優化指南
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： 徹底搞懂hashMap底層原理
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號