一、隊(duì)列的認(rèn)識(shí)

隊(duì)列的底層與集合框架

在 Java 中，隊(duì)列（Queue）是集合框架的一部分，屬于 java.util 包下的接口。

從底層實(shí)現(xiàn)來看，不同的隊(duì)列實(shí)現(xiàn)類底層數(shù)據(jù)結(jié)構(gòu)不同。但是主要是由鏈表和數(shù)組實(shí)現(xiàn)的.
LinkedList 實(shí)現(xiàn)了 Queue 接口，它底層基于雙向鏈表，通過節(jié)點(diǎn)的鏈接來維護(hù)隊(duì)列的先進(jìn)先出（FIFO）特性，插入和刪除元素時(shí)效率較高.
ArrayDeque 則底層基于數(shù)組，利用數(shù)組的索引操作來模擬隊(duì)列，在首尾操作元素時(shí)也能有較好的性能。

集合框架為隊(duì)列提供了統(tǒng)一的接口規(guī)范，讓開發(fā)者能方便地使用隊(duì)列的各種操作，如入隊(duì)（offer）、出隊(duì)（poll）、查看隊(duì)首元素（peek）等，同時(shí)也能結(jié)合集合框架中的其他類和接口，實(shí)現(xiàn)更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法操作。

java集合框架

常見的隊(duì)列方法

• queue(棧)中在java中常見的方法有add,offer .remove,poll .element , peek.他們兩兩一組,又有不同的次重點(diǎn).
• 這幾個(gè)方法都是Java中Queue接口定義的方法，它們的不同點(diǎn)主要體現(xiàn)在操作失敗時(shí)的表現(xiàn)以及方法用途側(cè)重方面：

插入元素方法對(duì)比（add和offer）

• add(E e)：
  • 操作失敗時(shí)的表現(xiàn)：如果試圖將元素添加到一個(gè)容量固定且已滿的隊(duì)列中，會(huì)拋出IllegalStateException異常。例如，當(dāng)使用ArrayDeque創(chuàng)建一個(gè)固定大小的隊(duì)列，并且隊(duì)列已經(jīng)達(dá)到最大容量時(shí)，調(diào)用add方法添加元素就會(huì)觸發(fā)異常。
  • 用途側(cè)重：適用于在程序中能明確保證隊(duì)列不會(huì)滿的場(chǎng)景，或者希望在隊(duì)列滿時(shí)以異常形式來中斷程序流程，從而進(jìn)行錯(cuò)誤處理的情況。
• offer(E e)：
  • 操作失敗時(shí)的表現(xiàn)：當(dāng)嘗試將元素添加到已滿的隊(duì)列中，不會(huì)拋出異常，而是返回false 。比如在實(shí)現(xiàn)一個(gè)任務(wù)隊(duì)列，當(dāng)隊(duì)列滿時(shí)，不希望程序因?yàn)樘砑尤蝿?wù)失敗而崩潰，此時(shí)可以使用offer方法，通過返回值來判斷任務(wù)是否成功添加。
  • 用途側(cè)重：更適合在日常開發(fā)中，不確定隊(duì)列是否已滿的場(chǎng)景，通過返回值來靈活處理添加操作的結(jié)果。

移除元素方法對(duì)比（remove和poll）

• remove()：
  • 操作失敗時(shí)的表現(xiàn)：如果從空隊(duì)列中移除元素，會(huì)拋出NoSuchElementException異常 。比如在編寫一個(gè)處理消息隊(duì)列的程序時(shí)，沒有提前檢查隊(duì)列是否為空就直接調(diào)用remove方法，當(dāng)隊(duì)列為空時(shí)就會(huì)引發(fā)異常。
  • 用途側(cè)重：適用于能確保隊(duì)列非空的場(chǎng)景，或者希望以異常的方式來處理空隊(duì)列情況，提醒開發(fā)者進(jìn)行相應(yīng)的錯(cuò)誤處理。
• poll()：
  • 操作失敗時(shí)的表現(xiàn)：從空隊(duì)列中移除元素時(shí)，不會(huì)拋出異常，而是返回null 。例如，在循環(huán)處理隊(duì)列元素時(shí)，可以使用poll方法，通過判斷返回值是否為null來確定是否已經(jīng)處理完所有元素，進(jìn)而結(jié)束循環(huán)。
  • 用途側(cè)重：在不確定隊(duì)列是否為空的情況下使用更方便，通過返回值就能輕松判斷操作結(jié)果，避免了繁瑣的異常處理代碼。

查看隊(duì)首元素方法對(duì)比（element和peek）

• element()：
  • 操作失敗時(shí)的表現(xiàn)：當(dāng)試圖從空隊(duì)列中獲取隊(duì)首元素時(shí)，會(huì)拋出NoSuchElementException異常 。例如，在一個(gè)多線程操作隊(duì)列的場(chǎng)景中，沒有做好同步控制，在隊(duì)列為空時(shí)調(diào)用element方法就會(huì)出現(xiàn)異常。
  • 用途側(cè)重：適用于確定隊(duì)列非空的場(chǎng)景，用于獲取隊(duì)首元素進(jìn)行后續(xù)操作，并且希望以異常形式來處理空隊(duì)列的情況。
• peek()：
  • 操作失敗時(shí)的表現(xiàn)：從空隊(duì)列中獲取隊(duì)首元素時(shí)，不會(huì)拋出異常，而是返回null 。比如在一個(gè)定時(shí)檢查隊(duì)列頭部元素的任務(wù)中，使用peek方法可以在不拋出異常的情況下，簡(jiǎn)單判斷隊(duì)列是否為空以及獲取隊(duì)首元素。
  • 用途側(cè)重：在不確定隊(duì)列是否為空，又需要獲取隊(duì)首元素信息時(shí)，使用peek方法更為合適，方便根據(jù)返回值進(jìn)行后續(xù)邏輯處理。

簡(jiǎn)單說就是

• add/remove/element：操作失敗會(huì)拋異常。
• offer/poll/peek：操作失敗返回 false（offer）或 null（poll/peek），更安全。

二、方法簡(jiǎn)單實(shí)現(xiàn)

Linkedlist實(shí)現(xiàn)

• 框架搭建

public class MyQueue {
    // 使用LinkedList實(shí)現(xiàn)的隊(duì)列，存儲(chǔ)整數(shù)類型元素
    // LinkedList實(shí)現(xiàn)了Queue接口，提供了隊(duì)列的基本操作 向上轉(zhuǎn)型
    Queue<Integer> queue = new LinkedList<>();
    //靜態(tài)內(nèi)部類
    static class ListNode{
        public int val;
        public ListNode prev; //鏈表中的兩個(gè)重要指向
        public ListNode next;
        public ListNode(int val){
            //構(gòu)造方法 用于實(shí)例化對(duì)象
            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三個(gè)指向的修改思想.比如:

數(shù)組實(shí)現(xiàn)遇到的問題

• 數(shù)組的結(jié)構(gòu)不像鏈表那樣靈活,尤其是頭刪,我們的指針會(huì)不斷的向后面進(jìn)行,導(dǎo)致前面的內(nèi)存浪費(fèi).
• 比如說;假設(shè)我們有一個(gè)固定大小的數(shù)組來模擬隊(duì)列，設(shè)置隊(duì)首指針 front 和隊(duì)尾指針 rear，初始時(shí)都指向數(shù)組起始位置。當(dāng)進(jìn)行入隊(duì)操作時(shí)，rear 不斷后移；出隊(duì)操作時(shí)，front 也不斷后移?？蛇@樣一來，隨著操作的進(jìn)行，隊(duì)列前面會(huì)逐漸出現(xiàn)空閑的空間，但因?yàn)?rear 已經(jīng)到達(dá)數(shù)組末尾，我們卻無法再利用這些前面的空閑空間，就好像隊(duì)列 “假滿” 了一樣，明明數(shù)組還有空間，卻無法繼續(xù)入隊(duì)新元素。
• 其次，當(dāng)隊(duì)列中的元素都出隊(duì)后，front 和 rear 都指向了數(shù)組后面的位置，此時(shí)隊(duì)列實(shí)際為空，但從指針位置看，卻好像還有元素存在，這就給我們判斷隊(duì)列是否為空帶來了困難。
• 為了解決這些問題，循環(huán)隊(duì)列的概念就被引入了。循環(huán)隊(duì)列把數(shù)組的首尾連接起來，形成一個(gè)環(huán)形的結(jié)構(gòu)，讓隊(duì)首和隊(duì)尾指針可以循環(huán)移動(dòng)，從而充分利用數(shù)組的空間，也能更方便、準(zhǔn)確地判斷隊(duì)列的空滿狀態(tài)。

三、引入循環(huán)隊(duì)列

兩個(gè)問題

從上面的圖可以看出有兩個(gè)棘手的問題

• 1.當(dāng)入隊(duì)的時(shí)候,rear不斷向后,傳統(tǒng)的思想就是每次有新的元素進(jìn)隊(duì),我們使rear+1即可,但是當(dāng)rear一個(gè)單位相鄰front時(shí)候,我們?cè)僮屜逻?1就不是front(默認(rèn)下表0)的下標(biāo)了,頭刪問題同上.
• 2.我們應(yīng)當(dāng)如何判斷隊(duì)列是不是滿的,而不是不同的覆蓋添加.

如何正確表示下邊(從尾部到頭部)?

公式法
(r + 偏移量) % len
(f + 偏移量) % len

如何判斷隊(duì)列滿不滿?

標(biāo)記法
在rear = front (起始時(shí)) tip = !isFull標(biāo)記一下,當(dāng)下一次出現(xiàn)rear = front時(shí), tip = isFull.不再進(jìn)行插入

預(yù)留空間法
在循環(huán)隊(duì)列中讓rear的下一位就是front,即(rear+1)%len = front

預(yù)留空間法實(shí)現(xiàn)

代碼示例

public class MyCircularQueue {
    //預(yù)留空間法
    //初始變量的定義
    public int [] elem;
    public int rear ;
    public int front;
    //構(gòu)造方法進(jìn)行初始化
    public MyCircularQueue(int k){
        this.elem = new int [k];
    }
    /****
     * 入隊(duì)
     */
    public boolean enQueue(int val) {
        //判滿
        if (isFull()) {
            return false;
        }
        elem[rear] = val;
        rear = (rear + 1) % elem.length;
        return true;
    }
    //出隊(duì)
    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的下一個(gè)是f
        return (rear+1)%elem.length == front;
    }
    public boolean isEmpty(){
        return front == rear;
    }
}

標(biāo)記法實(shí)現(xiàn)

代碼示例

public class MyCircularQueue {
    //標(biāo)記法
    //初始變量的定義
    public int [] elem;
    public int rear ;
    public int front;
    //構(gòu)造方法進(jìn)行初始化
    public MyCircularQueue(int k){
        this.elem = new int [k];
    }
	private boolean isFull0 = false;
    public boolean isFull2(){
        //r的下一個(gè)是f
        return isFull0;
    }
    public boolean isEmpty2(){
        return front == rear && !isFull0;
        }
    //標(biāo)記法
    public boolean enQueue2(int val) {
        //判滿
        if (isFull2()) { //一開始進(jìn)不來
            return false;
        }
        elem[rear] = val;
        rear = (rear + 1) % elem.length;
        //入隊(duì)后判斷是不是滿了
        if (rear == front) {
            isFull0 = true;
        }
        return true;
    }
    //出隊(duì)
    public boolean deQueue2 (){
        if (isEmpty()){
            return false;
        }
        front = (front+1)%elem.length;
        isFull0 = false;
        return true;
    }
}

四、實(shí)戰(zhàn)應(yīng)用(見<歷練場(chǎng)>)

隊(duì)列實(shí)現(xiàn)棧

棧實(shí)現(xiàn)隊(duì)列

總結(jié)

好啦,到這里我們隊(duì)列的知識(shí)就分享到這里了，謝謝大家的閱讀。如有問題請(qǐng)直接指出。

到此這篇關(guān)于Java 隊(duì)列Queue從原理到實(shí)戰(zhàn)指南的文章就介紹到這了,更多相關(guān)java 隊(duì)列queue內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論