看完這篇你還不知道這些隊(duì)列，我這些圖白作了

隊(duì)列（queue）是一種采用先進(jìn)先出(FIFO)策略的抽象數(shù)據(jù)結(jié)構(gòu)，即最先進(jìn)隊(duì)列的數(shù)據(jù)元素，同樣要最先出隊(duì)列。隊(duì)列跟我們排隊(duì)買(mǎi)票一樣，先來(lái)排隊(duì)的肯定先買(mǎi)票，后來(lái)排隊(duì)的的后買(mǎi)到票。隊(duì)列如下圖所示：


隊(duì)列有兩個(gè)重要的概念，一個(gè)叫隊(duì)頭，一個(gè)叫隊(duì)尾，隊(duì)頭指向的是第一個(gè)元素，而隊(duì)尾指向的是最后一個(gè)元素。隊(duì)列跟棧一樣也是訪問(wèn)受限制的，所以隊(duì)列也只有兩個(gè)主要的操作：
入隊(duì)(enqueue)操作 和 出隊(duì)(dequeue)操作 。入隊(duì)操作就是將一個(gè)元素添加到隊(duì)尾，出隊(duì)操作就是從隊(duì)頭取出一個(gè)元素。

隊(duì)列的底層實(shí)現(xiàn)可以用數(shù)組和鏈表，基于數(shù)組實(shí)現(xiàn)的隊(duì)列叫作順序隊(duì)列，基于鏈表實(shí)現(xiàn)的隊(duì)列叫作鏈?zhǔn)疥?duì)列，下面我們分別用數(shù)組和鏈表來(lái)簡(jiǎn)單的實(shí)現(xiàn)這兩種隊(duì)列。

基于數(shù)組的隊(duì)列

不管使用那種方式來(lái)實(shí)現(xiàn)隊(duì)列，都需要定義兩個(gè)指針?lè)謩e指向隊(duì)頭和隊(duì)尾，本文中我們用head指向隊(duì)頭，tail
指向隊(duì)尾，后面的示例中這將默認(rèn)使用這個(gè)，有特殊的地方我會(huì)進(jìn)行說(shuō)明，先來(lái)看看順序隊(duì)列的入隊(duì)、出隊(duì)操作。



圖中可以看出，入隊(duì)時(shí)，隊(duì)尾往后移動(dòng)，隊(duì)頭保持不變，出隊(duì)是隊(duì)頭往后移動(dòng)，隊(duì)尾保持不變。入隊(duì)、出隊(duì)操作的邏輯都比較簡(jiǎn)單，可能你有疑問(wèn)的地方是：
出隊(duì)時(shí)為什么隊(duì)頭要往后移動(dòng)而不是一直指向數(shù)組下標(biāo)為0的位置？ 為什么呢？如果我們保持隊(duì)頭一直指向數(shù)組下標(biāo)為0
的位置，那每次出隊(duì)操作后，后面的數(shù)據(jù)都需要往前挪一位，換句話說(shuō)每次出隊(duì)操作都需要進(jìn)行數(shù)據(jù)遷移，而數(shù)據(jù)遷移的代價(jià)比較大，每次數(shù)據(jù)遷移的時(shí)間復(fù)雜度為O(n)，這樣會(huì)極大的影響隊(duì)列的使用性能。如果我們出隊(duì)時(shí)，隊(duì)頭往后移動(dòng)一位，這樣我們就避免每次出隊(duì)都進(jìn)行數(shù)據(jù)遷移，我們只需要在只有在
tail等于數(shù)組大小且head不等于0時(shí)，進(jìn)行一次數(shù)據(jù)遷移，將已經(jīng)出隊(duì)留下的空間繼續(xù)供入隊(duì)時(shí)使用。下圖是數(shù)據(jù)遷移的過(guò)程：



數(shù)據(jù)遷移時(shí)，從head位置開(kāi)始的數(shù)據(jù)都需要往前移動(dòng)head位，這樣就把出隊(duì)后的空間騰出來(lái)，供后續(xù)入隊(duì)操作使用。

基于數(shù)組的隊(duì)列實(shí)現(xiàn)代碼：
/** * 基于數(shù)組的隊(duì)列 */ public class ArrayQueue { // 存放數(shù)據(jù)的數(shù)組 private String[] items;
// 容器的大小 private int size = 0; // 第一個(gè)節(jié)點(diǎn) private int head = 0; // 最后一個(gè)節(jié)點(diǎn) private
int tail = 0; // 構(gòu)造函數(shù) public ArrayQueue(int size){ this.size = size; items =
new String[size]; } /** * 入隊(duì)操作 * @param data * @return */ public int
enqueue(String data){ // 如果最后一個(gè)節(jié)點(diǎn)等于容器大小，說(shuō)明隊(duì)列滿了 /** * 判斷隊(duì)列滿了的條件，tail = size,head
= 0, */ if (tail == size && head == 0) return -1; /** * 如果tail = size，但是head !=
0,說(shuō)明前有數(shù)據(jù)刪除，隊(duì)列未滿，需要數(shù)據(jù)遷移 */ if (tail == size){ // head 后面的數(shù)據(jù)都需要往前遷移 head 位 for
(int i= head;i< size;i++){ items[i-head] = items[i]; } // 將最后一個(gè)元素遷移 head 位 tail
-=head; // 第一個(gè)元素指向 0 head = 0; } // 向隊(duì)列中添加元素 items[tail] = data; tail++; return
1; } /** * 出隊(duì)操作 * @return */ public String dequeue(){ // 第一個(gè)元素和最后一個(gè)元素相等時(shí)，隊(duì)列為空
if (head == tail) return null; String result = items[head]; //
第一個(gè)元素后移一次，這樣做的好處是在出隊(duì)時(shí)不需要數(shù)據(jù)遷移 head ++ ; return result; } }
鏈?zhǔn)疥?duì)列

鏈?zhǔn)疥?duì)列實(shí)現(xiàn)起來(lái)相對(duì)順序隊(duì)列來(lái)說(shuō)要簡(jiǎn)單很多，我們先來(lái)看看鏈?zhǔn)疥?duì)列的入隊(duì)、出隊(duì)操作：


從圖中可以看出鏈?zhǔn)疥?duì)列入隊(duì)操作是將tail的next指向新增的節(jié)點(diǎn)，然后將tail指向新增的節(jié)點(diǎn)，出隊(duì)操作時(shí)，將head節(jié)點(diǎn)指向head.next
節(jié)點(diǎn)。鏈?zhǔn)疥?duì)列與順序隊(duì)列比起來(lái)不需要進(jìn)行數(shù)據(jù)的遷移，但是鏈?zhǔn)疥?duì)列增加了存儲(chǔ)成本。

基于鏈表的隊(duì)列實(shí)現(xiàn)代碼
/** * 基于鏈表的隊(duì)列 */ public class LinkQueue { // 指向隊(duì)首 private Node head; // 指向隊(duì)尾
private Node tail; /** * 入隊(duì)操作 * @param data * @return */ public int
enqueue(String data){ Node node = new Node(data,null); // 判斷隊(duì)列中是否有元素 if (tail
== null) { tail = node; head = node; }else { tail.next = node; tail = node; }
return 1; } /** * 出隊(duì)操作 * @return */ public String dequeue(){ if (head==null)
return null; String data = head.data; head = head.next; //
取出元素后，頭指針為空，說(shuō)明隊(duì)列中沒(méi)有元素，tail也需要制為空 if (head == null){ tail = null; } return data;
} class Node{ private String data; private Node next; public Node(String
data,Node node){ this.data = data; next = node; } } }
循環(huán)隊(duì)列

循環(huán)隊(duì)列是對(duì)順序隊(duì)列的改進(jìn)，因?yàn)轫樞蜿?duì)列不可避免的數(shù)據(jù)遷移操作，數(shù)據(jù)遷移操作會(huì)導(dǎo)致隊(duì)列的性能下降，為了避免這個(gè)問(wèn)題，將隊(duì)列改造成循環(huán)的，當(dāng)tail
到達(dá)數(shù)組的最大下標(biāo)時(shí)，重新指回?cái)?shù)組下標(biāo)為0的位置，這樣就避免了數(shù)據(jù)遷移。先來(lái)看看循環(huán)隊(duì)列的出隊(duì)、入隊(duì)操作：


因?yàn)殛?duì)列是循環(huán)隊(duì)列，所以在進(jìn)行入隊(duì)、出隊(duì)操作時(shí)，就不能像順序隊(duì)列那樣對(duì)tail、head進(jìn)行簡(jiǎn)單的加1操作，我們需要對(duì)tail、head加1
后與數(shù)組的大小進(jìn)行求余操作，來(lái)得出tail、head的值，這樣才能進(jìn)行循環(huán)操作。循環(huán)隊(duì)列需要犧牲一個(gè)存儲(chǔ)空間，對(duì)于一個(gè)存儲(chǔ)空間為n的循環(huán)隊(duì)列來(lái)說(shuō)只能存放n-1
為數(shù)據(jù)，因?yàn)槿绻粻奚粋€(gè)存儲(chǔ)空間的話，當(dāng)tail==head時(shí)，就有可能存在隊(duì)空或者隊(duì)滿的情況。

循環(huán)隊(duì)列的實(shí)現(xiàn)代碼
/** * 環(huán)形隊(duì)列,不需要數(shù)據(jù)遷移，提高性能 */ public class CircularQueue { // 存放數(shù)據(jù)的數(shù)組 private
String[] items; // 容器的大小 private int size = 0; // 第一個(gè)節(jié)點(diǎn) private int head = 0;
// 最后一個(gè)節(jié)點(diǎn) private int tail = 0; // 構(gòu)造函數(shù) public CircularQueue(int size){
this.size = size; items = new String[size]; } /** * 入隊(duì)操作 * @param data *
@return */ public int enqueue(String data){ /** * 判斷環(huán)形隊(duì)列滿了的條件，(tail+1)求余等于head
*/ if ((tail+1)%size == head) return -1; // 向隊(duì)列中添加元素 items[tail] = data; //
因?yàn)槭黔h(huán)形隊(duì)列，所以下邊是數(shù)組長(zhǎng)度的余數(shù) tail= (tail+1)%size; return 1; } /** * 出隊(duì)操作 * @return */
public String dequeue(){ // 第一個(gè)元素和最后一個(gè)元素相等時(shí)，隊(duì)列為空 if (head == tail) return null;
String result = items[head]; // 因?yàn)槭黔h(huán)形隊(duì)列，所以下邊是數(shù)組長(zhǎng)度的余數(shù) head = (head+1)% size ;
return result; } }
雙端隊(duì)列

雙端隊(duì)列是一種隊(duì)頭、隊(duì)尾都可以進(jìn)行入隊(duì)、出隊(duì)操作的隊(duì)列，雙端隊(duì)列采用雙向鏈表來(lái)實(shí)現(xiàn)，先來(lái)看一下雙端隊(duì)列的入隊(duì)、出隊(duì)操作：




可以從動(dòng)態(tài)圖中看出，雙端隊(duì)列的每一端都是一個(gè)棧，都符合棧先進(jìn)后出的特性，如果我們對(duì)雙端隊(duì)列進(jìn)行禁止隊(duì)頭入隊(duì)和隊(duì)尾出隊(duì)操作的限制，雙端隊(duì)列又變成了一個(gè)鏈?zhǔn)疥?duì)列，雙端隊(duì)列是一種多功能的數(shù)據(jù)結(jié)構(gòu)，我們可以使用它來(lái)提供隊(duì)列和棧兩種功能。

雙端隊(duì)列的實(shí)現(xiàn)代碼
/** * 雙端隊(duì)列，使用雙向鏈表實(shí)現(xiàn) */ public class DoubleEndsQueue { private static class
Node { String item; Node next; Node prev; Node(Node prev, String element, Node
next) { this.item = element; this.next = next; this.prev = prev; } } // 第一個(gè)節(jié)點(diǎn)
private Node first; // 最后一個(gè)節(jié)點(diǎn) private Node last; /* * 在第一個(gè)節(jié)點(diǎn)前面入隊(duì) */ public void
enqueueFirst(String e) { final Node f = first; final Node newNode = new
Node(null, e, f); // 第一個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn) first = newNode; if (f == null) // 最后一個(gè)節(jié)點(diǎn)也指向該節(jié)點(diǎn)
last = newNode; else // 當(dāng)前節(jié)點(diǎn)的前節(jié)點(diǎn)指向新節(jié)點(diǎn) f.prev = newNode; } /** * 在最后一個(gè)元素后面入隊(duì) *
@param e */ public void enqueueLast(String e) { final Node l = last; final Node
newNode = new Node(l, e, null); // 最后一個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn) last = newNode; if (l == null)
// 第一個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn) first = newNode; else // 當(dāng)前節(jié)點(diǎn)的下節(jié)點(diǎn)指向新節(jié)點(diǎn) l.next = newNode; } /** *
從第一個(gè)節(jié)點(diǎn)出隊(duì) * @return */ public String dequeueFirst() { if (first == null) return
null; final Node f = first; String element = f.item; Node next = f.next; f.item
= null; f.next = null; // 第一個(gè)節(jié)點(diǎn)指向當(dāng)先節(jié)點(diǎn)的next節(jié)點(diǎn) first = next; if (next == null) //
說(shuō)明隊(duì)列為空 last = null; else next.prev = null; return element; } /** * 從最后節(jié)點(diǎn)出隊(duì) *
@return */ public String dequeueLast() { final Node l = last; if (last == null)
return null; String element = l.item; Node prev = l.prev; l.item = null; l.prev
= null; last = prev; if (prev == null) first = null; else prev.next = null;
return element; } // 輸出隊(duì)列全部?jī)?nèi)容 public void displayAll() { while (first !=null){
System.out.print(first.item+" "); first = first.next; }
System.out.println("==============="); } }
優(yōu)先隊(duì)列


優(yōu)先隊(duì)列為一種不必遵循隊(duì)列先進(jìn)先出(FIFO)特性的特殊隊(duì)列，優(yōu)先隊(duì)列跟普通隊(duì)列一樣都只有一個(gè)隊(duì)頭和一個(gè)隊(duì)尾并且也是從隊(duì)頭出隊(duì)，隊(duì)尾入隊(duì)，不過(guò)在優(yōu)先隊(duì)列中，每次入隊(duì)時(shí)，都會(huì)按照入隊(duì)數(shù)據(jù)項(xiàng)的關(guān)鍵值進(jìn)行排序(從大到小、從小到大)，這樣保證了關(guān)鍵字最小的或者最大的項(xiàng)始終在隊(duì)頭，出隊(duì)的時(shí)候優(yōu)先級(jí)最高的就最先出隊(duì)，這個(gè)就像我們醫(yī)院就醫(yī)一樣，急救的病人要比普通的病人先就診。一起來(lái)看看優(yōu)先隊(duì)列的出隊(duì)、入隊(duì)操作：


在示例中，我們規(guī)定數(shù)值越小優(yōu)先級(jí)越高。我們每執(zhí)行一次入隊(duì)操作時(shí)，小的元素都會(huì)靠近頭隊(duì)，在出隊(duì)的時(shí)候，元素小的也就先出隊(duì)。

優(yōu)先隊(duì)列的代碼實(shí)現(xiàn)

這里使用的數(shù)組實(shí)現(xiàn)優(yōu)先隊(duì)列，用數(shù)組實(shí)現(xiàn)主要原因是更好理解優(yōu)先隊(duì)列的思想。一般都是使用堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列，因?yàn)閿?shù)組實(shí)現(xiàn)在插入的時(shí)候?qū)?shù)據(jù)的排序代價(jià)比較大。
/** * 優(yōu)先隊(duì)列 */ public class PriorityQueue { // 存放數(shù)據(jù)的數(shù)組 private Integer[] items;
// 容器的大小 private int size = 0; // 第一個(gè)節(jié)點(diǎn) private int head = 0; // 構(gòu)造函數(shù) public
PriorityQueue(int size){ this.size = size; items = new Integer[size]; } /** *
入隊(duì)操作 * @param data * @return */ public int enqueue(Integer data){ int j; if
(head == 0){ items[head++] = data; } else { for (j=head-1;j>=0;j--){ // 將小的數(shù)往后排
if (data > items[j]){ items[j+1] = items[j]; }else { break; } } items[j+1] =
data; head++; } return 1; } public Integer dequeue(){ return items[--head]; } }
總結(jié)

* 隊(duì)列是一種遵循先進(jìn)先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)
* 隊(duì)列可以使用數(shù)組和鏈表實(shí)現(xiàn)，數(shù)組實(shí)現(xiàn)叫作順序隊(duì)列，鏈表實(shí)現(xiàn)叫作鏈?zhǔn)疥?duì)列
* 循環(huán)隊(duì)列解決了順序隊(duì)列的數(shù)據(jù)遷移帶來(lái)的性能損耗的問(wèn)題
* 雙端隊(duì)列是隊(duì)頭和隊(duì)尾都可以進(jìn)行入隊(duì)、出隊(duì)操作的隊(duì)列
* 優(yōu)先隊(duì)列是一種不必遵循先進(jìn)先出規(guī)則的隊(duì)列，任意元素加入時(shí)，都會(huì)講優(yōu)先級(jí)最高的放入到隊(duì)頭
最后

打個(gè)小廣告，歡迎掃碼關(guān)注微信公眾號(hào)：「平頭哥的技術(shù)博文」，一起進(jìn)步吧。

• ? 上一篇： 【備戰(zhàn)春招/秋招系列】程序員的簡(jiǎn)歷就該這樣寫(xiě)
• ? 下一篇：手把手教你使用Java實(shí)現(xiàn)一個(gè)神經(jīng)網(wǎng)絡(luò)