Java 隊列Queue從原理到實戰(zhàn)指南
更新時間：2025年11月28日 10:35:32 作者：Dylan的碼園
本文介紹了Java中隊列（Queue）的底層實現(xiàn)、常見方法及其區(qū)別,通過LinkedList和ArrayDeque的實現(xiàn),以及循環(huán)隊列的概念,展示了如何高效地進行元素的入隊、出隊和查看操作,感興趣的朋友跟隨小編一起看看吧
一、隊列的認識
隊列的底層與集合框架
在 Java 中，隊列（Queue）是集合框架的一部分，屬于 java.util 包下的接口。
從底層實現(xiàn)來看，不同的隊列實現(xiàn)類底層數(shù)據(jù)結構不同。但是主要是由鏈表和數(shù)組實現(xiàn)的.LinkedList 實現(xiàn)了 Queue 接口，它底層基于雙向鏈表，通過節(jié)點的鏈接來維護隊列的先進先出（FIFO）特性，插入和刪除元素時效率較高.ArrayDeque 則底層基于數(shù)組，利用數(shù)組的索引操作來模擬隊列，在首尾操作元素時也能有較好的性能。
集合框架為隊列提供了統(tǒng)一的接口規(guī)范，讓開發(fā)者能方便地使用隊列的各種操作，如入隊（offer）、出隊（poll）、查看隊首元素（peek）等，同時也能結合集合框架中的其他類和接口，實現(xiàn)更復雜的數(shù)據(jù)結構和算法操作。
java集合框架
常見的隊列方法
- queue(棧)中在java中常見的方法有add,offer .remove,poll .element , peek.他們兩兩一組,又有不同的次重點.
- 這幾個方法都是Java中
Queue接口定義的方法，它們的不同點主要體現(xiàn)在操作失敗時的表現(xiàn)以及方法用途側重方面：
插入元素方法對比（add和offer）
add(E e)：- 操作失敗時的表現(xiàn)：如果試圖將元素添加到一個容量固定且已滿的隊列中，會拋出
IllegalStateException異常。例如，當使用ArrayDeque創(chuàng)建一個固定大小的隊列，并且隊列已經達到最大容量時，調用add方法添加元素就會觸發(fā)異常。 - 用途側重：適用于在程序中能明確保證隊列不會滿的場景，或者希望在隊列滿時以異常形式來中斷程序流程，從而進行錯誤處理的情況。
- 操作失敗時的表現(xiàn)：如果試圖將元素添加到一個容量固定且已滿的隊列中，會拋出
offer(E e)：- 操作失敗時的表現(xiàn)：當嘗試將元素添加到已滿的隊列中，不會拋出異常，而是返回
false。比如在實現(xiàn)一個任務隊列，當隊列滿時，不希望程序因為添加任務失敗而崩潰，此時可以使用offer方法，通過返回值來判斷任務是否成功添加。 - 用途側重：更適合在日常開發(fā)中，不確定隊列是否已滿的場景，通過返回值來靈活處理添加操作的結果。
- 操作失敗時的表現(xiàn)：當嘗試將元素添加到已滿的隊列中，不會拋出異常，而是返回
移除元素方法對比（remove和poll）
remove()：- 操作失敗時的表現(xiàn)：如果從空隊列中移除元素，會拋出
NoSuchElementException異常 。比如在編寫一個處理消息隊列的程序時，沒有提前檢查隊列是否為空就直接調用remove方法，當隊列為空時就會引發(fā)異常。 - 用途側重：適用于能確保隊列非空的場景，或者希望以異常的方式來處理空隊列情況，提醒開發(fā)者進行相應的錯誤處理。
- 操作失敗時的表現(xiàn)：如果從空隊列中移除元素，會拋出
poll()：- 操作失敗時的表現(xiàn)：從空隊列中移除元素時，不會拋出異常，而是返回
null。例如，在循環(huán)處理隊列元素時，可以使用poll方法，通過判斷返回值是否為null來確定是否已經處理完所有元素，進而結束循環(huán)。 - 用途側重：在不確定隊列是否為空的情況下使用更方便，通過返回值就能輕松判斷操作結果，避免了繁瑣的異常處理代碼。
- 操作失敗時的表現(xiàn)：從空隊列中移除元素時，不會拋出異常，而是返回
查看隊首元素方法對比（element和peek）
element()：- 操作失敗時的表現(xiàn)：當試圖從空隊列中獲取隊首元素時，會拋出
NoSuchElementException異常 。例如，在一個多線程操作隊列的場景中，沒有做好同步控制，在隊列為空時調用element方法就會出現(xiàn)異常。 - 用途側重：適用于確定隊列非空的場景，用于獲取隊首元素進行后續(xù)操作，并且希望以異常形式來處理空隊列的情況。
- 操作失敗時的表現(xiàn)：當試圖從空隊列中獲取隊首元素時，會拋出
peek()：- 操作失敗時的表現(xiàn)：從空隊列中獲取隊首元素時，不會拋出異常，而是返回
null。比如在一個定時檢查隊列頭部元素的任務中，使用peek方法可以在不拋出異常的情況下，簡單判斷隊列是否為空以及獲取隊首元素。 - 用途側重：在不確定隊列是否為空，又需要獲取隊首元素信息時，使用
peek方法更為合適，方便根據(jù)返回值進行后續(xù)邏輯處理。
- 操作失敗時的表現(xiàn)：從空隊列中獲取隊首元素時，不會拋出異常，而是返回
簡單說就是
add/remove/element：操作失敗會拋異常。offer/poll/peek：操作失敗返回false（offer）或null（poll/peek），更安全。
二、方法簡單實現(xiàn)
Linkedlist實現(xiàn)
- 框架搭建
public class MyQueue {
// 使用LinkedList實現(xiàn)的隊列，存儲整數(shù)類型元素
// LinkedList實現(xiàn)了Queue接口，提供了隊列的基本操作 向上轉型
Queue<Integer> queue = new LinkedList<>();
//靜態(tài)內部類
static class ListNode{
public int val;
public ListNode prev; //鏈表中的兩個重要指向
public ListNode next;
public ListNode(int val){
//構造方法 用于實例化對象
this.val = val;
}
}
public ListNode first;
public ListNode last;
}- 工具代碼
public boolean isEmpty(){
return first == null && last ==null;
}
public int size(){
int count = 0;
ListNode cur = first;
while (cur != null){
count++;
cur = cur.next;
}
return count;
}- 尾差offer
public void offer(int val){
ListNode node = new ListNode(val);
if (isEmpty()){
first = last = node;
}else {
last.next = node;
node.prev = last;
last = node;
}
}
- 頭刪poll
public int poll(){
int val = first.val;
if (isEmpty()){
return -1;
}
if (first == last){
first = null;
last = null;
}else {
first = first.next;
first.prev = null;
}
return val;
}- 取頂pop
public int pop(){
if (isEmpty()){
return -1;
}
else {
return first.val;
}
}
- 核心思想
這里方法核心思想就是鏈表中指向的修改問題,在定義的first,last cur三個指向的修改思想.比如:
數(shù)組實現(xiàn)遇到的問題
- 數(shù)組的結構不像鏈表那樣靈活,尤其是頭刪,我們的指針會不斷的向后面進行,導致前面的內存浪費.
- 比如說;假設我們有一個固定大小的數(shù)組來模擬隊列，設置隊首指針 front 和隊尾指針 rear，初始時都指向數(shù)組起始位置。當進行入隊操作時，rear 不斷后移；出隊操作時，front 也不斷后移?？蛇@樣一來，隨著操作的進行，隊列前面會逐漸出現(xiàn)空閑的空間，但因為 rear 已經到達數(shù)組末尾，我們卻無法再利用這些前面的空閑空間，就好像隊列 “假滿” 了一樣，明明數(shù)組還有空間，卻無法繼續(xù)入隊新元素。
- 其次，當隊列中的元素都出隊后，front 和 rear 都指向了數(shù)組后面的位置，此時隊列實際為空，但從指針位置看，卻好像還有元素存在，這就給我們判斷隊列是否為空帶來了困難。
- 為了解決這些問題，循環(huán)隊列的概念就被引入了。循環(huán)隊列把數(shù)組的首尾連接起來，形成一個環(huán)形的結構，讓隊首和隊尾指針可以循環(huán)移動，從而充分利用數(shù)組的空間，也能更方便、準確地判斷隊列的空滿狀態(tài)。
三、引入循環(huán)隊列
兩個問題
從上面的圖可以看出有兩個棘手的問題
- 1.當入隊的時候,rear不斷向后,傳統(tǒng)的思想就是每次有新的元素進隊,我們使rear+1即可,但是當rear一個單位相鄰front時候,我們再讓下邊+1就不是front(默認下表0)的下標了,頭刪問題同上.
- 2.我們應當如何判斷隊列是不是滿的,而不是不同的覆蓋添加.
如何正確表示下邊(從尾部到頭部)?
公式法(r + 偏移量) % len(f + 偏移量) % len
如何判斷隊列滿不滿?
標記法
在rear = front (起始時) tip = !isFull標記一下,當下一次出現(xiàn)rear = front時, tip = isFull.不再進行插入
預留空間法
在循環(huán)隊列中讓rear的下一位就是front,即(rear+1)%len = front
預留空間法實現(xiàn)
代碼示例
public class MyCircularQueue {
//預留空間法
//初始變量的定義
public int [] elem;
public int rear ;
public int front;
//構造方法進行初始化
public MyCircularQueue(int k){
this.elem = new int [k];
}
/****
* 入隊
*/
public boolean enQueue(int val) {
//判滿
if (isFull()) {
return false;
}
elem[rear] = val;
rear = (rear + 1) % elem.length;
return true;
}
//出隊
public boolean deQueue (){
if (isEmpty()){
return false;
}
front = (front+1)%elem.length;
return true;
}
/****
* 返回頭
* @return
*/
public int getFront(){
if (isEmpty()){
return -1;
}
return elem[front];
}
/****
* 返回尾
* @return
*/
public int getRear(){
if (isEmpty()){
return -1;
}
if (rear == 0)
return elem[elem.length-1];
//處理邊界問題
}else {
return elem[rear-1];
}
}
public boolean isFull(){
//r的下一個是f
return (rear+1)%elem.length == front;
}
public boolean isEmpty(){
return front == rear;
}
}標記法實現(xiàn)
代碼示例
public class MyCircularQueue {
//標記法
//初始變量的定義
public int [] elem;
public int rear ;
public int front;
//構造方法進行初始化
public MyCircularQueue(int k){
this.elem = new int [k];
}
private boolean isFull0 = false;
public boolean isFull2(){
//r的下一個是f
return isFull0;
}
public boolean isEmpty2(){
return front == rear && !isFull0;
}
//標記法
public boolean enQueue2(int val) {
//判滿
if (isFull2()) { //一開始進不來
return false;
}
elem[rear] = val;
rear = (rear + 1) % elem.length;
//入隊后判斷是不是滿了
if (rear == front) {
isFull0 = true;
}
return true;
}
//出隊
public boolean deQueue2 (){
if (isEmpty()){
return false;
}
front = (front+1)%elem.length;
isFull0 = false;
return true;
}
}四、實戰(zhàn)應用(見<歷練場>)
隊列實現(xiàn)棧
棧實現(xiàn)隊列
總結
好啦,到這里我們隊列的知識就分享到這里了，謝謝大家的閱讀。如有問題請直接指出。
到此這篇關于Java 隊列Queue從原理到實戰(zhàn)指南的文章就介紹到這了,更多相關java 隊列queue內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了Java反射簡易教程，小編覺得挺不錯的，這里分享給大家，需要的朋友可以參考。2017-11-11
本文介紹了三種在Java中實現(xiàn)定時任務的方法,并推薦使用Spring Boot注解方式,介紹了如何使用`@Scheduled`注解結合Cron表達式來設置定時任務,并提供了一個示例配置文件2025-03-03
Shiro 控制并發(fā)登錄人數(shù)限制及登錄踢出的實現(xiàn)代碼
本文通過shiro實現(xiàn)一個賬號只能同時一個人使用，本文重點給大家分享Shiro 控制并發(fā)登錄人數(shù)限制及登錄踢出的實現(xiàn)代碼，需要的朋友參考下吧2017-09-09
Python安裝Jupyter Notebook配置使用教程詳解
這篇文章主要介紹了Python安裝Jupyter Notebook配置使用教程詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-09-09
解決Java字符串JSON轉換異常:cn.hutool.json.JSONException:?Mismatched?
這篇文章主要給大家介紹了關于如何解決Java字符串JSON轉換異常:cn.hutool.json.JSONException:?Mismatched?hr?and?body的相關資料,文中將解決的辦法通過代碼介紹的非常詳細,需要的朋友可以參考下2024-01-01
可以清楚的看到在互斥鎖和共享鎖的拿鎖過程中都是有調用此方法的,而cancelAcquire()方法是寫在finally代碼塊中,并且使用failed標志位來控制cancelAcquire()方法的執(zhí)行2023-04-04
這篇文章主要為大家詳細介紹了Java中的運算符，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
這篇文章主要為大家詳細介紹了java實現(xiàn)九宮格游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-11-11
SpringMvc web.xml配置實現(xiàn)原理過程解析
這篇文章主要介紹了SpringMvc web.xml配置實現(xiàn)原理過程解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-08-08
這篇文章主要介紹了Java 散列存儲詳解及簡單示例的相關資料,需要的朋友可以參考下2017-02-02