Java循環(huán)隊列原理與用法詳解
本文實例講述了Java循環(huán)隊列原理與用法。分享給大家供大家參考，具體如下：
在正式進行循環(huán)隊列學習之前，我們先來看看在順序隊列中刪除隊首元素出現(xiàn)的問題
（1）設一個容量為capacity=8，size=5(a,b,c,d,e)的數(shù)組，左側為隊首、右側為隊尾。
（2）出隊一個元素后，需整體往前移動一位
#出隊
#2整體前移一位
關于該種操作方式我們很容易得出時間復雜度為O(n)。
這時我們就想可不可以在出隊元素后，整體元素不往前移，而是在數(shù)組中記下隊首front是誰，同時隊尾tail指向在下一次元素入隊時的位置，這樣當再有出隊時只需要維護一下front的指向即可，而不需移動元素。就這樣我們就有了循環(huán)隊列的情況。
2.循環(huán)隊列原理
(1)初始，數(shù)組整體為空時，隊首front、隊尾tail指向同一個位置（數(shù)組索引為0的地方）也即front==tail 時隊列為空
(2)當往數(shù)組中添加元素后，
(3)出隊一個元素，front指向新的位置
(4)入隊元素，tail疊加
(5)當tail不能再增加時，數(shù)組前面還有空余，此時循環(huán)隊列就該出場了。
此時數(shù)組應該變?yōu)檫@樣：
在往數(shù)組中添加一個元素：
這樣數(shù)組就已經滿了（tail+1==front 隊列滿），開始出發(fā)擴容操作?！綾apacity中，浪費一個空間】。
為了tail能返回到數(shù)組的前面位置，將隊列滿的表達式變?yōu)?【（tail+1）%c==front】這樣數(shù)組就可以循環(huán)移動了。
3.循環(huán)隊列代碼實現(xiàn)
新建一個類LoopQueue并實現(xiàn)接口Queue。
#1：接口Queue代碼如下：
package Queue;
public interface Queue<E> {
//獲取隊列中元素個數(shù)
int getSize();
//隊列中元素是否為空
boolean isEmpty();
//入隊列
void enqueue(E e);
//出隊列
E dequeue();
//獲取隊首元素
E getFront();
}
#2：LoopQueue相關代碼：
package Queue;
//循環(huán)隊列
public class LoopQueue<E> implements Queue<E> {
private E[] data;
private int front, tail;
private int size;//隊列中元素個數(shù)
//構造函數(shù)，傳入隊列的容量capacity構造函數(shù)
public LoopQueue(int capacity) {
data = (E[]) new Object[capacity + 1];//浪費與一個空間
front = 0;
tail = 0;
size = 0;
}
//無參構造函數(shù)，默認隊列的容量capacity=10
public LoopQueue() {
this(10);
}
//真正容量
public int getCapacity() {
return data.length - 1;
}
//隊列是否為空
@Override
public boolean isEmpty() {
return front == tail;
}
//隊列中元素個數(shù)
@Override
public int getSize() {
return size;
}
//入隊列操作
@Override
public void enqueue(E e) {
if ((tail + 1) % data.length == front) {//隊列已滿，需要擴容
resize(getCapacity() * 2);
}
data[tail] = e;
tail = (tail + 1) % data.length;
size++;
}
//出隊操作
@Override
public E dequeue() {
if (isEmpty()) {
throw new IllegalArgumentException("隊列為空");
}
E ret = data[front];
data[front] = null;//手動釋放
front = (front + 1) % data.length;
size--;
if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
resize(getCapacity() / 2);
}
return ret;
}
//獲取隊首元素
@Override
public E getFront() {
if (isEmpty()) {
throw new IllegalArgumentException("隊列為空");
}
return data[front];
}
//改變容量
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity + 1];
for (int i = 0; i < size; i++) {
newData[i] = data[(front + i) % data.length];//循環(huán)數(shù)組防止越界
}
data = newData;
front = 0;
tail = size;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Queue:size=%d, capacity=%d\n", size, getCapacity()));
res.append("front [");
for (int i = front; i != tail; i = (i + 1) % data.length) {
res.append(data[i]);
if ((i + 1) % data.length != tail) {
res.append(",");
}
}
res.append("] tail");
return res.toString();
}
}
在關于LoopQueue類中需要注意的：
（1）第11行中的+1是capacity需要浪費一個空間，故在實例化是多加1
data = (E[]) new Object[capacity + 1];//浪費與一個空間
（2）地24行真正的容量是data.length-1，這是由于有一個空間是浪費的。
data.length - 1;
（3）關于入隊中第46行tail值的說明
為了保證入隊是循環(huán)操作，tail值的變化規(guī)律為
tail = (tail + 1) % data.length;
（4）關于82行的數(shù)據(jù)遷移操作，取余操作是為了防止循環(huán)數(shù)組時越界。
newData[i] = data[(front + i) % data.length];//循環(huán)數(shù)組防止越界
#3直接在LoopQueue中添加一個main函數(shù)進行測試，相關代碼如下：
//測試用例
public static void main(String[] args) {
LoopQueue<Integer> queue = new LoopQueue<Integer>();
for (int i = 0; i < 10; i++) {
queue.enqueue(i);
System.out.println(queue);
if(i%3==2){//每添加3個元素出隊列一個
queue.dequeue();
System.out.println(queue);
}
}
}
結果為：
4.循環(huán)隊列時間復雜度
到此我們就實現(xiàn)了一個循環(huán)隊列操作，解決了在順序隊列中出隊時的時間復雜度為O(n)的情況，在循環(huán)隊列中出隊的時間復雜度為O(1)。
源碼地址 https://github.com/FelixBin/dataStructure/blob/master/src/Queue/LoopQueue.java
更多關于java算法相關內容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結構與算法教程》、《Java操作DOM節(jié)點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。
相關文章
IntelliJ IDEA搜索整個項目進行全局替換(有危險慎用)
今天小編就為大家分享一篇關于IntelliJ IDEA搜索整個項目進行全局替換(有危險慎用)，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-10-10
這篇文章主要介紹了Spring boot集成Kafka+Storm的示例代碼，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-12-12
文章總結：本文主要介紹了單鏈表的基本操作,包括頭插法、尾插法、鏈表翻轉、鏈表成環(huán)判斷、成環(huán)位置判斷、成環(huán)長度判斷,以及有序鏈表的合并,通過實例和代碼示例,詳細講解了每種操作的原理和實現(xiàn)方法2025-01-01
作為程序員,多多少少都會遇到一些內存溢出的場景,如果你還沒遇到,說明你工作的年限可能比較短,或者你根本就是個假程序員！哈哈,開個玩笑.今天分享給大家Java內存溢出的相關案例,希望大家在日常工作中,盡量避免寫這些low水平的代碼,需要的朋友可以參考下2021-06-06
如何開啟控制臺輸出mybatis執(zhí)行的sql日志問題
這篇文章主要介紹了如何開啟控制臺輸出mybatis執(zhí)行的sql日志問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-09-09
這篇文章給大家講解的是MyBatis 這門技術的 CURD （增刪改查） ,非常的詳細與實用,有需要的小伙伴可以參考下2020-02-02
這篇文章主要為大家介紹了java開發(fā)Activiti進階篇流程實例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08
Java Jackson之ObjectMapper常用用法總結
這篇文章主要給大家介紹了關于Java Jackson之ObjectMapper常用用法的相關資料,ObjectMapper是一個Java庫,用于將JSON字符串轉換為Java對象或將Java對象轉換為JSON字符串,需要的朋友可以參考下2024-01-01
java開發(fā)工具IntelliJ?IDEA深受用戶喜愛，很多朋友對這個idea開發(fā)工具比較忠心，一旦有新版本發(fā)出，很多小伙伴就迫不及待的想更新，今天小編給大家?guī)砹薸dea2022.1最新永久激活碼，親測有效，喜歡的朋友快來下載體驗吧2022-08-08
今天給大家?guī)淼氖顷P于Java的相關知識,文章圍繞著Java如何實現(xiàn)小頂堆和大頂堆展開,文中有非常詳細的解釋及代碼示例,需要的朋友可以參考下2021-06-06