概念

隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出FIFO(FirstIn First Out) 入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾（Tail/Rear） 出隊(duì)列：進(jìn)行刪除操作的一端稱為隊(duì)頭（Head/Front）

隊(duì)列的使用

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


注意：Queue是個(gè)接口，在實(shí)例化時(shí)必須實(shí)例化LinkedList的對(duì)象，因?yàn)長inkedList實(shí)現(xiàn)了Queue接口。

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); // 從隊(duì)尾入隊(duì)列
	System.out.println(q.size());
	System.out.println(q.peek()); // 獲取隊(duì)頭元素
	q.poll();
	System.out.println(q.poll()); // 從隊(duì)頭出隊(duì)列，并將刪除的元素返回
	if(q.isEmpty()){
		System.out.println("隊(duì)列空");
	}else{
		System.out.println(q.size());
	}
}

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

隊(duì)列中既然可以存儲(chǔ)元素，那底層肯定要有能夠保存元素的空間，通過前面線性表的學(xué)習(xí)了解到常見的空間類型有兩種：順序結(jié)構(gòu) 和 鏈?zhǔn)浇Y(jié)構(gòu)。

public class Queue {
    // 雙向鏈表節(jié)點(diǎn)
    public static class ListNode{
        ListNode next;
        ListNode prev;
        int value;
        ListNode(int value){
            this.value = value;
        }
    }
    ListNode first; // 隊(duì)頭
    ListNode last; // 隊(duì)尾
    int size = 0;
    // 入隊(duì)列---向雙向鏈表位置插入新節(jié)點(diǎ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++;
    }
    // 出隊(duì)列---將雙向鏈表第一個(gè)節(jié)點(diǎn)刪除掉
    public int poll(){
// 1. 隊(duì)列為空
// 2. 隊(duì)列中只有一個(gè)元素----鏈表中只有一個(gè)節(jié)點(diǎn)---直接刪除
// 3. 隊(duì)列中有多個(gè)元素---鏈表中有多個(gè)節(jié)點(diǎn)----將第一個(gè)節(jié)點(diǎn)刪除
        int value = 0;
        if(first == null){
            throw new RuntimeException("隊(duì)列沒有元素 poll失敗");
        }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;
    }
    // 獲取隊(duì)頭元素---獲取鏈表中第一個(gè)節(jié)點(diǎn)的值域
    public int peek(){
        if(first == null){
            throw new RuntimeException("隊(duì)列沒有元素 peek失敗");
        }
        return first.value;
    }
    public int size() {
        return size;
    }
    public boolean isEmpty(){
        return first == null;
    }
}

循環(huán)隊(duì)列

實(shí)際中我們有時(shí)還會(huì)使用一種隊(duì)列叫循環(huán)隊(duì)列。如操作系統(tǒng)課程講解生產(chǎn)者消費(fèi)者模型時(shí)可以就會(huì)使用循環(huán)隊(duì)列。環(huán)形隊(duì)列通常使用數(shù)組實(shí)現(xiàn)。

如何區(qū)分空與滿

1. 通過添加 size 屬性記錄
2. 保留一個(gè)位置
3. 使用標(biāo)記
   

雙端隊(duì)列 (Deque)

雙端隊(duì)列（deque）是指允許兩端都可以進(jìn)行入隊(duì)和出隊(duì)操作的隊(duì)列，deque 是 “double ended queue” 的簡稱。那就說明元素可以從隊(duì)頭出隊(duì)和入隊(duì)，也可以從隊(duì)尾出隊(duì)和入隊(duì)。

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

文章來源地址http://www.zghlxwxcb.cn/news/detail-414499.html

到了這里，關(guān)于【Java數(shù)據(jù)結(jié)構(gòu)】線性表-隊(duì)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！