Java數(shù)據(jù)結(jié)構(gòu)之隊列示例詳解
更新時間：2025年12月21日 11:37:08 作者：鴿鴿程序猿
隊列是一種線性數(shù)據(jù)結(jié)構(gòu),它遵循先進(jìn)先出或后近后出的原則,隊列允許在一端插入元素,另一端刪除元素,這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)之隊列的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下
一、隊列
隊列是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表，一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。
隊尾：允許插入的一端。
隊頭：允許刪除的一端。
二、隊列的模擬實現(xiàn)
隊列的底層可以是順序表，可以是鏈表實現(xiàn)。
2.1 隊列的鏈?zhǔn)綄崿F(xiàn)
在實現(xiàn)隊列前我們先思考使用什么樣的鏈表來實現(xiàn)？
由于棧的特性是先入先出，如果使用單鏈表和雙向鏈表都可以，
只要在單鏈表標(biāo)記一下尾節(jié)點就行，
但是因為Java提供的是雙向鏈表實現(xiàn)的，所以我們使用雙向鏈表。
2.1.1 接口實現(xiàn)
實現(xiàn)的接口如下：
public class MyQueue {
//入隊列
public void offer(int val) {}
//出隊列
public int poll() {}
//獲取隊頭元素 但是不刪除
public int peek() { }
//判空
public boolean isEmpty() { }
//獲取隊列元素個數(shù)
public int size(){}
}
2.1.2 內(nèi)部類
跟雙向鏈表的內(nèi)部類實現(xiàn)差不多。
static class ListNode{
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode last;
2.1.3 入隊列
實現(xiàn)思路：
- 先看隊列是否為空，為空，頭尾指向入隊節(jié)點。
- 不為空尾節(jié)點的后繼next指向入隊節(jié)點，入隊節(jié)點前驅(qū)prev指向尾節(jié)點，尾節(jié)點變?yōu)槿腙牴?jié)點。
public void offer(int val){
ListNode cur = new ListNode(val);
if(isEmpty()){
head = last = cur;
return;
}
last.next = newNode;
newNode.prev = last;
last = newNode;
}
2.1.4 出隊列
實現(xiàn)思路：
- 先判斷隊列是否為空，隊列為空拋異常。
- 隊列不為空，將頭節(jié)點記錄下來，頭節(jié)點后一個節(jié)點前驅(qū)prev置為空，頭節(jié)點變?yōu)楹笠粋€節(jié)點。
public int poll() throws NullPointerException{
try{
if(isEmpty()){
throw new NullPointerException;
}
}catch(NullPointerException e){
e.printStackTrace();
}
ListNode cur = head;
head.next.prev = null;
head = head.next;
return cur.val;
}
2.1.5 獲取隊頭元素 但是不刪除
實現(xiàn)思路：
- 先判斷隊列是否為空，隊列為空拋異常。
- 隊列不為空，返回頭節(jié)點。
public int peek() throws NullPointerException{
try{
if(isEmpty()){
throw new NullPointerException;
}
}catch(NullPointerException e){
e.printStackTrace();
}
return head.val;
}
2.1.6 判空
直接返回頭是否為空就行。
public boolean isEmpty(){
return head == null;
}
2.1.7 獲取隊列元素個數(shù)
直接循環(huán)遍歷即可。
public int size(){
ListNode cur = head;
int size = 0;
while(cur != null){
cur = cur.next;
size++;
}
return size;
}
2.2 隊列的順序?qū)崿F(xiàn)（循環(huán)隊列）
2.2.1 直接使用順序表的缺陷
當(dāng)我們直接使用順序表來放數(shù)據(jù)時，我們將元素入隊列放在數(shù)組尾，出隊列時將數(shù)組前面元素出去后，會使前面浪費的空間越來越大。
基于此我們就用循環(huán)隊列來實現(xiàn)，還是數(shù)組作為底層，但我們將其想象成一個圓。
2.2.2 接口實現(xiàn)
class MyCircularQueue {
//構(gòu)造器，設(shè)置隊列長度為 k
public MyCircularQueue(int k) {}
// 向循環(huán)隊列插入一個元素。如果成功插入則返回真。
public boolean enQueue(int value) {}
//從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真。
public boolean deQueue() {}
//從隊首獲取元素。如果隊列為空，返回 -1
public int Front() {}
//獲取隊尾元素。如果隊列為空，返回 -1 。
public int Rear() {}
//檢查循環(huán)隊列是否為空。
public boolean isEmpty() {}
//檢查循環(huán)隊列是否已滿。
public boolean isFull() {}
};
2.2.3 成員變量
數(shù)組arr ，頭下標(biāo)front，尾節(jié)點下一個下標(biāo)rear，數(shù)組長度size。
private int []arr; private int front; private int rear; private int size;
2.2.4 構(gòu)造器，設(shè)置隊列長度為 k
因為我們使用的判空方法（下文講）會造成一個空間的浪費，所以多申請一個空間。
public MyCircularQueue(int k) {
size = k+1;
arr = new int[size];
front = rear = 0;
}
2.2.5 向循環(huán)隊列插入一個元素 成功插入則返回真
實現(xiàn)思路：
- 判斷隊列是否已滿，滿了就返回false。
- 不滿就在rear放。
- 因為是循環(huán)隊列，所以rear的賦值要使用取余。
public boolean enQueue(int value) {
if(isFull()){
return false;
}else{
arr[rear] = value;
rear = (rear + 1) % size;
return true;
}
}
2.2.6 從循環(huán)隊列中刪除一個元素 成功刪除則返回真
實現(xiàn)思路：
- 判斷隊列是否為空，空就返回false。
- 不空就直接將front指向下一個位置。
- 因為是循環(huán)隊列，所以front的賦值要使用取余。
public boolean deQueue() {
if(isEmpty()){
return false;
}else{
front = (front + 1) % size;
return true;
}
}
2.2.7 從隊首獲取元素。如果隊列為空，返回 -1
實現(xiàn)思路：
- 先判斷隊列是否為空，為空返回-1。
- 不為空，返回front下標(biāo)對應(yīng)值。
public int Front() {
if(isEmpty()){
return -1;
}else{
return arr[front];
}
}
2.2.8 獲取隊尾元素。如果隊列為空，返回 -1
實現(xiàn)思路：
- 先判斷隊列是否為空，為空返回-1。
- 不為空，再判斷rear是否為0，是0就返回數(shù)組最后一個元素。
- 不為0，就直接返回rear-1下標(biāo)對應(yīng)的元素。
public int Rear() {
if(isEmpty()){
return -1;
}else{
if(rear == 0){
return arr[size - 1];
}else{
return arr[rear - 1];
}
}
}
2.2.9 檢查循環(huán)隊列是否為空
檢查空根據(jù)循環(huán)隊列的實現(xiàn)有兩種方法：
- 使用usedSize記錄隊列元素個數(shù)，個數(shù)為0就是空。
- 空一個空間，如果front和rear相等那就是空。
public boolean isEmpty() {
return rear == front;
}
2.2.10 檢查循環(huán)隊列是否已滿
檢查滿根據(jù)循環(huán)隊列的實現(xiàn)有兩種方法：
- 使用usedSize記錄隊列元素個數(shù)，個數(shù)和size相等就是滿。
- 空一個空間，如果rear的下一個位置就是front那就是滿。
public boolean isFull() {
return front == (rear+1) % size;
}
三、Java中的Queue
Java中Queue的底層是LinkedList實現(xiàn)的。
并且Queue只是一個接口，必須new對象LinkedList才能使用。
3.1 實現(xiàn)的接口
實現(xiàn)的接口如下：
3.2 常用方法
常用方法如下：
四、隊列練習(xí)
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之隊列示例詳解的文章就介紹到這了,更多相關(guān)Java數(shù)據(jù)結(jié)構(gòu)隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
今天通過實例代碼給大家介紹了Springboot 注入裝配到IOC容器方式，代碼簡單易懂，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，感興趣的朋友跟隨小編一起看看吧2021-10-10
這篇文章主要為大家詳細(xì)介紹了Java中常見的一些占位符的使用方法，例如%d，%s等，文中的示例代碼簡潔易懂，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)學(xué)習(xí)2023-05-05
關(guān)于遠(yuǎn)程調(diào)用RestTemplate的使用避坑指南
這篇文章主要介紹了關(guān)于遠(yuǎn)程調(diào)用RestTemplate的使用避坑指南，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-10-10
如何使用Resttemplate和Ribbon調(diào)用Eureka實現(xiàn)負(fù)載均衡
這篇文章主要介紹了如何使用Resttemplate和Ribbon調(diào)用Eureka實現(xiàn)負(fù)載均衡，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-03-03
在很多場景中我們需要驗證時間日期的是否屬于正確的格式，驗證時間是否符合常規(guī)的，本文就來介紹一下幾種方式，感興趣的可以了解一下2022-04-04
SpringFactoriesLoader可以加載jar包下META-INF下的spring.factories，把相關(guān)接口的實現(xiàn)按照key,value的形式加載到內(nèi)存，一個接口的多個實現(xiàn)可以按照","進(jìn)行分割2022-10-10
這篇文章主要介紹了springboot啟動類如何剔除掃描某個包，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-11-11
MyBatis-Plus updateById方法更新不了空字符串/null的問題及解決
MyBatis-Plus的updateById()方法在更新字段為null時會失敗,因為默認(rèn)策略不更新null值,文章提供三種解決方案：全局配置忽略判斷、使用PO對象的el屬性指定jdbcType、通過注解設(shè)置字段驗證策略為IGNORED2026-03-03
下面小編就為大家?guī)硪黄狫VM 心得分享(加載 鏈接 初始化)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-10-10
JDK8接口的默認(rèn)與靜態(tài)方法-接口與抽象類的區(qū)別詳解
這篇文章主要介紹了JDK8接口的默認(rèn)與靜態(tài)方法-接口與抽象類的區(qū)別詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，,需要的朋友可以參考下2019-06-06