摘要:前言數據結構與算法專題會不定時更新,歡迎各位讀者監督。隊列和棧類似,也是一個遵循特殊規則約束的數據結構。將沒有元素的隊列稱之為空隊,往隊列中插入元素的過程稱之為入隊,從隊列中移除元素的過程稱之為出隊。
聲明:碼字不易,轉載請注明出處,歡迎文章下方討論交流。
前言:Java數據結構與算法專題會不定時更新,歡迎各位讀者監督。本文介紹數據結構中的隊列(queue)的概念、存儲結構、隊列的特點,文末給出java實現循環隊列的代碼實現供讀者參考學習。
1.隊列的概念隊列正如其名,隊列就像一支隊伍,有隊首(head)和隊尾(tail)以及隊列長度。隊列和棧類似,也是一個遵循特殊規則約束的數據結構。在上一篇文章java數據結構與算法——棧中介紹棧是一個后進先出(LIFO)的數據結構,隊列正好與之相反,是一個先進先出(FIFO,First In First Out),例如我們去肯德基排隊,先排上隊的肯定先拿到餐出隊,這和我們對列認知是一致的。
上面說到隊列是一個遵循特殊規則的數據結構,除了先進先出,隊列的插入只能從隊列的一端操作,我們稱這端為隊尾;對應的,移除只能從另一端出來,我們稱之為隊首。
將沒有元素的隊列稱之為空隊,往隊列中插入元素的過程稱之為入隊,從隊列中移除元素的過程稱之為出隊。
一般而言,隊列的實現有兩種方式:數組實現和鏈表實現,本篇中采取數組實現,鏈表實現在后續補充。用數組實現的隊列有兩種:一種是順序隊列,另一種是循環隊列,這兩種隊列的存儲結構和特點下文會逐一介紹。
說明:用數組實現隊列,若隊列中出現隊滿的情況(因為在聲明隊列時,一般會指定一個初始容量),此時如果有新元素入隊,但沒有位置怎么辦?要么丟棄,要么等待。
2.隊列的存儲結構以下采用數組實現,初始化一個隊列長度為6,隊列有兩個標記,一個隊頭的位置head,一個隊尾的位置tail,初始都指向數組下標為0的位置,如圖所示:
在插入元素時,tail標記+1,比如入隊三個元素,依次為A,B,C(注意是有順序的),則當前隊列存儲情況如圖:
當前head為0,tail為3,接下來進行出隊操作,此處將A元素出隊,則head+1,此時隊列的存儲情況如圖:
根據上面的圖例,我們可以通過tail-head獲得隊列中元素的個數。當tail==head時,此時隊列為空,而當tail等于數組長度時,此時將無法出入元素,那么隊列是否已經滿呢?未必!因為head和tail在入隊和出隊操作中只增不減,因此head和tail都會最終指向隊列之外的存儲位置,此時雖然數組為空,但也無法將元素入隊。
上溢: 當隊列中無法插入元素時,稱之為上溢;
假上溢: 在順序隊列中,數組還有空間(不一定全空)但無法入隊稱之為假上溢;
真上溢: 如果head為0,tail指向數組之外,即數組真滿了,稱之為真上溢;
下溢: 如果空隊中執行出隊操作,此時隊列中無元素,稱之為下溢
如何解決“假上溢”的問題呢?此時引入循環隊列。出現假上溢時,此時數組還有空閑的位置,將tail從新指向數組的0索引處即可,如圖所示:
如果繼續入隊E和F,則隊列的存儲結構如圖:
通常而言,在對head和tail加1時,為了方便采用對數組長度取余操作。另外由于順序隊列存在“假上溢”的現象,所以一般用循環隊列實現。
在采用循環隊列實現的過程中,當隊列滿隊時,tail等于head,而當隊列空時,tail也等于head,為了區分兩種狀態,一般規定循環隊列的長度為數組長度-1,即有一個位置不放元素,此時head==tail時為空隊,而當head==(tail+1)%數組長度,說明對滿。
3.隊列的java代碼實現下面是循環隊列的java代碼,采用數組方式實現:
public class ArrayQueue { private final Object[] queue; //聲明一個數組 private int head; private int tail; /** * 初始化隊列 * @param capacity 隊列長度 */ public ArrayQueue(int capacity){ this.queue = new Object[capacity]; } /** * 入隊 * @param o 入隊元素 * @return 入隊成功與否 */ public boolean put(Object o){ if(head == (tail+1)%queue.length){ //說明隊滿 return false; } queue[tail] = o; tail = (tail+1)%queue.length; //tail標記后移一位 return true; } /** * 返回隊首元素,但不出隊 * @return */ public Object peak() { if(head==tail){ //隊空 return null; } return queue[head]; } /** * 出隊 * @return 出隊元素 */ public Object pull(){ if(head==tail){ return null; } Object item = queue[head]; queue[head] = null; return item; } /** * 判斷是否為空 * @return */ public boolean isEmpty(){ return head == tail; } /** * 判斷是否為滿 * @return */ public boolean isFull(){ return head == (tail+1)%queue.length; } /** * 獲取隊列中的元素個數 * @return */ public int getsize(){ if(tail>=head){ return tail-head; }else{ return (tail+queue.length)-head; } } }
下面是隊列的測試代碼
public class ArrayQueueTest { public static void main(String[] args) { ArrayQueue q = new ArrayQueue(4); //初始化隊列長度為3,因為循環隊列有一個不放元素 System.out.println(q.put("張三")); //入隊,true System.out.println(q.put("李四")); //入隊,true System.out.println(q.put("趙五")); //入隊,true System.out.println(q.put("老王")); //隊滿,false System.out.println(q.isFull()); //隊滿 true System.out.println(q.getsize()); //3,隊列中有3個元素 System.out.println(q.peak()); //返回“張三” 不出隊 System.out.println(q.pull()); //返回“張三” System.out.println(q.pull()); //返回“李四” System.out.println(q.pull()); //返回“趙五” System.out.println(q.isEmpty()); //true 空隊 } }4.隊列的應用場景
隊列先入先出的特點,使得其應用非常廣泛,比如隊列作為“緩沖區”,可以解決計算機和外設速度不匹配的問題,FIFO的特點保證了數據傳輸的順序;除此之外隊列在后面樹的層序遍歷中也有應用,FIFO的特點保證了處理順序不會出錯。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/76372.html
摘要:算法算法會先對一個內存變量位置和一個給定的值進行比較,如果相等,則用一個新值去修改這個內存變量位置。因為是非公平鎖,所以一上來就嘗試搶占鎖給定舊值并希望用新值去更新內存變量。 本文翻譯和原創各占一半,所以還是厚顏無恥歸類到原創好了...https://howtodoinjava.com/jav...java 5 其中一個令人振奮的改進是新增了支持原子操作的類型,例如 AtomicInt...
摘要:問題是這些服務都是第三方提供的,不能保證它們的響應時間,快的話美團點評分布式生成系統后端掘金背景在復雜分布式系統中,往往需要對大量的數據和消息進行唯一標識。 SpringBatch 讀取 txt 文件并寫入數據庫 - 后端 - 掘金SpringBatch 讀取 txt 文件并寫入數據庫... Java 進階-多線程開發關鍵技術 - 后端 - 掘金原創文章,轉載請務必將下面這段話置于文章...
摘要:問題是這些服務都是第三方提供的,不能保證它們的響應時間,快的話美團點評分布式生成系統后端掘金背景在復雜分布式系統中,往往需要對大量的數據和消息進行唯一標識。 SpringBatch 讀取 txt 文件并寫入數據庫 - 后端 - 掘金SpringBatch 讀取 txt 文件并寫入數據庫... Java 進階-多線程開發關鍵技術 - 后端 - 掘金原創文章,轉載請務必將下面這段話置于文章...
??前面的話?? 大家好!這是Java基礎知識與數據結構博文的導航帖,收藏我!學習Java不迷路! ?博客主頁:未見花聞的博客主頁 ?歡迎關注?點贊?收藏??留言? ?本文由未見花聞原創,CSDN首發! ?首發時間:?2021年11月11日? ??堅持和努力一定能換來詩與遠方! ?參考書籍:?《Java核心技術卷1》,?《Java核心技術卷2》,?《Java編程思想》 ?參考在線編程網站:?牛...
閱讀 3138·2021-11-24 10:24
閱讀 2930·2021-11-11 16:54
閱讀 3066·2021-09-22 15:55
閱讀 2027·2019-08-30 15:44
閱讀 1901·2019-08-29 18:41
閱讀 2761·2019-08-29 13:43
閱讀 3053·2019-08-29 12:51
閱讀 1171·2019-08-26 12:19