??隊列(Queue)的概念

隊列：只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有==先進先出FIFO(FirstIn First Out) ==入隊列：

進行插入操作的一端稱為隊尾（Tail/Rear） 出隊列：

進行刪除操作的一端稱為隊頭（Head/Front）

??隊列的使用

在Java中，Queue是個接口，底層是通過鏈表實現(xiàn)的。

隊列在使用時有以下方法：

注意：Queue是個接口，在實例化時必須實例化LinkedList的對象，因為LinkedList實現(xiàn)了Queue接口。

使用如下：

import java.util.LinkedList;
import java.util.Queue;

public class TestMain {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        q.offer(5); // 從隊尾入隊列
        System.out.println(q.size());
        System.out.println(q.peek()); // 獲取隊頭元素
        q.poll();
        System.out.println(q.poll()); // 從隊頭出隊列，并將刪除的元素返回
        if(q.isEmpty()){
            System.out.println("隊列空");
        }else{
            System.out.println(q.size());
        }
    }
}

運行結果如下：

??隊列的模擬實現(xiàn)

隊列中既然可以存儲元素，那底層肯定要有能夠保存元素的空間，通過前面線性表的學習了解到常見的空間類型有兩種：順序結構 和 鏈式結構。

這里博主為大家演示一個雙鏈表模擬實現(xiàn)隊列

??創(chuàng)建隊列

其實就是創(chuàng)建一個雙鏈表，這里就不做過多贅述了，實現(xiàn)如下：

    public static class ListNode {
        ListNode next;
        ListNode prev;
        int value;

        ListNode(int value) {
            this.value = value;
        }
    }

    ListNode first; // 隊頭
    ListNode last; // 隊尾
    int size = 0;

??入隊列

向雙向鏈表位置插入新節(jié)點，做法如下：

• 創(chuàng)建一個節(jié)點newNode接收傳進來的元素
• 判斷該隊列是否為null
• 若為null，則該元素就是隊頭
• 若不為null，則將該元素的前驅節(jié)點設置為last；
• last的后繼節(jié)點變?yōu)閚ewNode
• newNode變?yōu)樾碌奈补?jié)點
• size++

實現(xiàn)如下：

    // 入隊列
    public void offer(int e) {
        ListNode newNode = new ListNode(e);
        if (first == null) {
            first = newNode;
// last = newNode;
        } else {
            last.next = newNode;
            newNode.prev = last;
// last = newNode;
        }
        last = newNode;
        size++;
    }

??出隊列

將雙向鏈表第一個節(jié)點刪除掉，做法如下：

• 分為幾種情況
• 當隊列為空時
• 則直接返回隊列為空的異常，自定義異常如下

public class EmptyException extends RuntimeException{
    public EmptyException() {
    }

    public EmptyException(String message) {
        super(message);
    }
}

• 當隊列中只有一個元素----鏈表中只有一個節(jié)點時—直接刪除
• 當隊列中有多個元素—鏈表中有多個節(jié)點----將第一個節(jié)點刪除

實現(xiàn)如下：

    // 出隊列---將雙向鏈表第一個節(jié)點刪除掉
    public int poll() {
// 1. 隊列為空
// 2. 隊列中只有一個元素----鏈表中只有一個節(jié)點---直接刪除
// 3. 隊列中有多個元素---鏈表中有多個節(jié)點----將第一個節(jié)點刪除
        int value = 0;
        if (first == null) {
            throw new EmptyException("隊列為空");
        } else if (first == last) {
            last = null;
            first = null;
        } else {
            value = first.value;
            first = first.next;
            first.prev.next = null;
            first.prev = null;
        }
        --size;
        return value;
    }

??獲取隊頭元素

獲取鏈表中第一個節(jié)點的值域

• 若隊列為null，拋出異常
• 若不為null，返回隊頭的元素

實現(xiàn)如下：

    // 獲取隊頭元素---獲取鏈表中第一個節(jié)點的值域
    public int peek() {
        if (first == null) {
            throw new EmptyException("隊列為空");
        }
        return first.value;
    }

??獲取隊列長度

直接返回size就好

實現(xiàn)如下：

   public int size() {
        return size;
    }

??判斷是否為空

直接判斷對頭是否為null，然后返回就好

實現(xiàn)如下：

    public boolean isEmpty(){
        return first == null;
    }

??完整代碼

MyQueue實現(xiàn)如下：

public class MyQueue {
    // 雙向鏈表節(jié)點
    public static class ListNode {
        ListNode next;
        ListNode prev;
        int value;

        ListNode(int value) {
            this.value = value;
        }
    }

    ListNode first; // 隊頭
    ListNode last; // 隊尾
    int size = 0;

    // 入隊列---向雙向鏈表位置插入新節(jié)點
    public void offer(int e) {
        ListNode newNode = new ListNode(e);
        if (first == null) {
            first = newNode;
// last = newNode;
        } else {
            last.next = newNode;
            newNode.prev = last;
// last = newNode;
        }
        last = newNode;
        size++;
    }

    // 出隊列---將雙向鏈表第一個節(jié)點刪除掉
    public int poll() {
// 1. 隊列為空
// 2. 隊列中只有一個元素----鏈表中只有一個節(jié)點---直接刪除
// 3. 隊列中有多個元素---鏈表中有多個節(jié)點----將第一個節(jié)點刪除
        int value = 0;
        if (first == null) {
            throw new EmptyException("隊列為空");
        } else if (first == last) {
            last = null;
            first = null;
        } else {
            value = first.value;
            first = first.next;
            first.prev.next = null;
            first.prev = null;
        }
        --size;
        return value;
    }

    // 獲取隊頭元素---獲取鏈表中第一個節(jié)點的值域
    public int peek() {
        if (first == null) {
            throw new EmptyException("隊列為空");
        }
        return first.value;
    }
    public int size() {
        return size;
    }
    public boolean isEmpty(){
        return first == null;
    }
}

??雙端隊列 (Deque)

雙端隊列（deque）是指允許兩端都可以進行入隊和出隊操作的隊列

deque 是 “double ended queue” 的簡稱。

那就說明元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊

Deque是一個接口，使用時必須創(chuàng)建LinkedList的對象。

在實際工程中，使用Deque接口是比較多的，棧和隊列均可以使用該接口

Deque<Integer> stack = new ArrayDeque<>();//雙端隊列的線性實現(xiàn)
Deque<Integer> queue = new LinkedList<>();//雙端隊列的鏈式實現(xiàn)

?總結

關于《 【數(shù)據(jù)結構】 棧（Stack）與棧的模擬實現(xiàn)》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評指正，如果文章對您有幫助或者覺得作者寫的還不錯可以點一下關注，點贊，收藏支持一下！文章來源地址http://www.zghlxwxcb.cn/news/detail-677683.html

到了這里，關于【數(shù)據(jù)結構】 隊列(Queue)與隊列的模擬實現(xiàn)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！