---

目錄

隊列的概念

隊列的數(shù)據(jù)結(jié)構(gòu)

隊列的實現(xiàn)

入隊

出隊

獲取隊頭元素

獲取隊列長度

循環(huán)隊列的概念

循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)

循環(huán)隊列的實現(xiàn)

判斷隊列是否為空

判斷隊列是否已滿

入隊

出隊

得到隊頭元素

得到隊尾元素

---

隊列的概念

隊列（Queue）是一種數(shù)據(jù)結(jié)構(gòu)，是一種先進先出（First-In-First-Out，FIFO）的線性數(shù)據(jù)結(jié)構(gòu)。它只允許在列表的一端進行插入操作（入隊），在另一端進行刪除操作（出隊），即隊頭進行刪除操作，隊尾進行插入操作。隊列常用的操作有入隊（Enqueue）、出隊（Dequeue）、獲取隊頭元素（Front/Peek）、獲取隊列長度（Size/Length）等。

圖示如下：

隊列的特點是按照元素加入的先后順序進行操作，先加入隊列的元素會先被取出，后加入的元素會后被取出。這種特性常常被用于模擬實際生活中的排隊場景，例如銀行柜臺排隊、CPU任務(wù)調(diào)度等。

---

隊列的數(shù)據(jù)結(jié)構(gòu)

隊列可以用數(shù)組或鏈表來實現(xiàn)。數(shù)組實現(xiàn)的隊列需要預(yù)先分配一定的空間，但是在操作中效率較高；鏈表實現(xiàn)的隊列沒有固定的空間限制，但是在操作中可能需要更多的時間和空間。

這里筆者以鏈表進行演示：

public class MyQueue {static class ListNode {int val;//存放數(shù)據(jù)ListNode pre;//前驅(qū)指針ListNode next;//后驅(qū)指針public ListNode(int val) {this.val = val;}}private ListNode head;//記錄頭節(jié)點private ListNode last;//記錄尾部節(jié)點
}

---

隊列的實現(xiàn)

入隊

因為我們使用的是鏈表來模擬實現(xiàn)，所以對于入隊的操作就相當(dāng)于使用尾插法(頭插法)，入隊圖示：

當(dāng)隊列為空的時候需要進行特殊處理，不然會造成空指針異常，隊列為空的時候讓我們的頭指針和尾指針都指向這個節(jié)點就可以，如果隊列不為空就正常的使用尾插法，尾插法圖示：

    //入隊public void enqueue(int val) {ListNode newNode = new ListNode(val);if (head == null) {head = newNode;last = newNode;}else {newNode.pre = last;last.next = newNode;last = newNode;}}

出隊

隊列是個單向的數(shù)據(jù)結(jié)構(gòu)，對于入隊我們使用了尾插法，那么出隊就需要使用刪除頭節(jié)點的方法，出隊的圖示如下：

出隊實際上是對于隊頭節(jié)點的刪除，所以當(dāng)隊內(nèi)沒有節(jié)點的時候我們就不能進行這樣的操作，我們直接拋出一個異常，在可以拋出的情況下，我們定義一個 val變量 來存放我們要刪除的值，以便返回。當(dāng)隊列只有一個元素的時候要進行特殊處理，不然后面的程序會報空指針異常，這種情況下，我們需要先拿到頭節(jié)點的值，然后將頭節(jié)點置空，最后返回這個值；其余情況我們就正常進行刪除操作，先拿到頭節(jié)點的值然后讓頭節(jié)點后移，再讓改變現(xiàn)在頭節(jié)點的前驅(qū)指針，讓我們要刪除的數(shù)據(jù)無法被訪問，最后返回這個值

    //出隊public int dequeue() {if (head == null) {throw new ExceptionOfEmpty("隊列為空，無法操作");}int val = -1;//當(dāng)隊列只有一個元素的時候要進行特殊處理，不然后面的程序會報空指針異常if (head.next == null) {val = head.val;head = null;last = null;return val;}//對于其他正常位置元素的處理val = head.val;head = head.next;head.pre = null;return val;}

獲取隊頭元素

獲取隊頭元素則十分的簡單，使用個臨時變量拿到頭節(jié)點的值然后返回就可以了

    //拿出隊列的首個元素進行查看public int peek() {if (head == null) {throw new ExceptionOfEmpty("隊列為空，無法操作");}int val = head.val;return val;}

獲取隊列長度

獲取隊列的長度也非常的簡單，使用一個新的節(jié)點挨個變量，然后累加計數(shù)器最后返回就可以

    //獲取隊列長度public int size() {int count = 0;ListNode cur = head;while (cur != null) {cur = cur.next;count++;}return count;}

---

循環(huán)隊列的概念

循環(huán)隊列是一種特殊的隊列數(shù)據(jù)結(jié)構(gòu)，它允許隊列的頭尾相接，形成一個環(huán)。循環(huán)隊列解決了普通隊列的一些缺點，如空間浪費和在元素出隊后無法再次入隊的問題。

循環(huán)隊列通常使用數(shù)組來實現(xiàn)，其內(nèi)部有兩個指針front和rear，分別指向隊列的第一個元素和最后一個元素的下一個位置。初始化時，front和rear都指向數(shù)組的第一個位置。

當(dāng)往循環(huán)隊列中插入元素時，將元素放入rear指向的位置，并將rear指針向后移動一位。如果rear指針到達數(shù)組的尾部，則將其指向數(shù)組的起始位置。當(dāng)從循環(huán)隊列中刪除元素時，將front指針向后移動一位，表示該元素已出隊列。如果front指針到達數(shù)組的尾部，則將其指向數(shù)組的起始位置。

圖示如下：

使用循環(huán)隊列可以實現(xiàn)高效的元素入隊和出隊操作，因為循環(huán)隊列的空間利用率較高。當(dāng)隊列滿時，rear指針和front指針會指向同一個位置，此時隊列被認(rèn)為是滿的。而在普通隊列中，即使隊列中還有空閑位置，當(dāng)rear指針到達數(shù)組的尾部時，無法再向隊列中插入元素。

循環(huán)隊列通過循環(huán)利用數(shù)組空間，解決了普通隊列的空間浪費和無法再次入隊的問題，提高了隊列的空間利用率和性能。

---

循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)

對于循環(huán)隊列，我們可以使用數(shù)組來模擬實現(xiàn)，分別有倆個指針指向整個數(shù)組的首部和尾部

public class MyCircularQueue {public int[] elem;//存放數(shù)據(jù)public int front;//指向隊頭public int rear;//指向隊尾MyCircularQueue(int k) {elem = new int[k];}
}

---

循環(huán)隊列的實現(xiàn)

對于循環(huán)隊列的實現(xiàn)，其實難點就在于判斷隊列的狀態(tài)，分得清隊列已滿和隊列為空的情況就可以，其余的操作實際上都是非常簡單的數(shù)組的添加和刪除元素

另外很重要的一點就是，循環(huán)隊列需要體現(xiàn)出循環(huán)的概念，所以不管是隊頭指針還是隊尾指針，我們在操作的時候都需要除以這個數(shù)組的模

判斷隊列是否為空

隊列為空是怎么樣的狀態(tài)？為空，也就是說隊列內(nèi)什么都沒有，隊列的開始就是隊列的結(jié)束，也就是隊頭指針和隊尾指針指向同一個地方，如圖所示：

    //判空 front和rear相遇public boolean isEmpty() {return front == rear;}

判斷隊列是否已滿

隊列已滿是怎么樣的狀態(tài)？隊列已滿就是說隊列每一個位置都有元素存放，這個情況下，如果隊尾指針再往后走一步，就相當(dāng)于回到了第二輪的起點，如圖所示：

那么也就是說，當(dāng)隊尾指針再往后走一步的值除以整個隊列的大小，就等于頭指針的大小?

    //判空 front和rear相遇public boolean isFull() {return (rear + 1) % elem.length == front;}

入隊

入隊的時候，我們先要判斷隊列是否已滿，滿了就返回false表示入隊失敗；沒有滿的話就進行入隊，也就是從數(shù)組的最后位置放個元素，然后再更改隊尾指針指向，圖示如下：

出隊

出隊的實現(xiàn)實際上就是對數(shù)組的第一個元素進行刪除操作，如圖所示：

    //出隊public boolean deQueue() {if (isEmpty()) {return false;}front = (front + 1) % elem.length;return true;}

得到隊頭元素

這樣的操作其實就是出隊操作的簡化，拿到值返回即可，這里就不再贅述

    //得到隊頭元素public int Front() {if (isEmpty()) {return -1;}return elem[front];}

得到隊尾元素

這里有一點需要注意，當(dāng)我們的隊列只有一個元素的時候，是需要進行特殊處理的，不然就會出現(xiàn)數(shù)組越界的異常，畢竟數(shù)組不存在下標(biāo)為-1的元素

    //得到隊尾元素public int Rear() {if (isEmpty()) {return -1;}int index = (rear == 0) ? elem.length - 1 : rear - 1;return index;}

---

---

---

??本次的分享就到此為止了，希望我的分享能給您帶來幫助，也歡迎大家三連支持，你們的點贊就是博主更新最大的動力！如有不同意見，歡迎評論區(qū)積極討論交流，讓我們一起學(xué)習(xí)進步！有相關(guān)問題也可以私信博主，評論區(qū)和私信都會認(rèn)真查看的，我們下次再見