国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Java數據結構與算法[原創]——隊列

韓冰 / 2097人閱讀

摘要:前言數據結構與算法專題會不定時更新,歡迎各位讀者監督。隊列和棧類似,也是一個遵循特殊規則約束的數據結構。將沒有元素的隊列稱之為空隊,往隊列中插入元素的過程稱之為入隊,從隊列中移除元素的過程稱之為出隊。

聲明:碼字不易,轉載請注明出處,歡迎文章下方討論交流。

前言: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

相關文章

  • CAS 算法 —— Compare and Swap

    摘要:算法算法會先對一個內存變量位置和一個給定的值進行比較,如果相等,則用一個新值去修改這個內存變量位置。因為是非公平鎖,所以一上來就嘗試搶占鎖給定舊值并希望用新值去更新內存變量。 本文翻譯和原創各占一半,所以還是厚顏無恥歸類到原創好了...https://howtodoinjava.com/jav...java 5 其中一個令人振奮的改進是新增了支持原子操作的類型,例如 AtomicInt...

    mmy123456 評論0 收藏0
  • 長知識 - 收藏集 - 掘金

    摘要:問題是這些服務都是第三方提供的,不能保證它們的響應時間,快的話美團點評分布式生成系統后端掘金背景在復雜分布式系統中,往往需要對大量的數據和消息進行唯一標識。 SpringBatch 讀取 txt 文件并寫入數據庫 - 后端 - 掘金SpringBatch 讀取 txt 文件并寫入數據庫... Java 進階-多線程開發關鍵技術 - 后端 - 掘金原創文章,轉載請務必將下面這段話置于文章...

    SimpleTriangle 評論0 收藏0
  • 長知識系列 - 收藏集 - 掘金

    摘要:問題是這些服務都是第三方提供的,不能保證它們的響應時間,快的話美團點評分布式生成系統后端掘金背景在復雜分布式系統中,往往需要對大量的數據和消息進行唯一標識。 SpringBatch 讀取 txt 文件并寫入數據庫 - 后端 - 掘金SpringBatch 讀取 txt 文件并寫入數據庫... Java 進階-多線程開發關鍵技術 - 后端 - 掘金原創文章,轉載請務必將下面這段話置于文章...

    longmon 評論0 收藏0
  • JavaSE數據結構基礎知識系列——專欄導航

    ??前面的話?? 大家好!這是Java基礎知識與數據結構博文的導航帖,收藏我!學習Java不迷路! ?博客主頁:未見花聞的博客主頁 ?歡迎關注?點贊?收藏??留言? ?本文由未見花聞原創,CSDN首發! ?首發時間:?2021年11月11日? ??堅持和努力一定能換來詩與遠方! ?參考書籍:?《Java核心技術卷1》,?《Java核心技術卷2》,?《Java編程思想》 ?參考在線編程網站:?牛...

    Cc_2011 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<