[[385574]]

今天繼續(xù)來(lái)給大家上一盤(pán)硬菜，保證喂個(gè)半飽——嗝。和棧一樣，隊(duì)列(queue)也是一個(gè)非常有用的數(shù)據(jù)結(jié)構(gòu)。同時(shí)又非常特殊，它只允許在隊(duì)尾(rear)插入元素，在隊(duì)首(front)刪除元素，也就是一端進(jìn)，一端出。

在網(wǎng)上購(gòu)票普及之前，我們大多數(shù)人需要到車(chē)站的購(gòu)票大廳買(mǎi)票，經(jīng)常是排隊(duì)排到水泄不通，queue 就和現(xiàn)實(shí)中的排隊(duì)是一模一樣的，排在隊(duì)首的先買(mǎi)到票，然后離開(kāi)，緊跟著的人移動(dòng)到隊(duì)首，直到隊(duì)列消失。

隊(duì)列遵循的是 First In First Out，縮寫(xiě)為 FIFO，也就是先進(jìn)先出，第一個(gè)進(jìn)入隊(duì)列的第一個(gè)先出來(lái)。

在上面這幅圖中，1 比 2 先進(jìn)入隊(duì)列，也比 2 先出隊(duì)列，規(guī)規(guī)矩矩的。

對(duì)于隊(duì)列這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)，它有兩個(gè)常見(jiàn)的動(dòng)作：

• enqueue，我個(gè)人喜歡把它譯作入隊(duì)，指的是把元素放入隊(duì)列這個(gè)動(dòng)作。
• dequeue，出隊(duì)，指的是把元素從隊(duì)列中移除這個(gè)動(dòng)作。

明白了隊(duì)列的基本操作后，我們來(lái)深入地思考一下，隊(duì)列是如何工作的。

1) 建立順序的隊(duì)列結(jié)構(gòu)需要為其靜態(tài)分配或者動(dòng)態(tài)申請(qǐng)一串連續(xù)的存儲(chǔ)空間。

2)然后設(shè)置兩個(gè)指針進(jìn)行管理：一個(gè)隊(duì)首指針 FRONT，指向隊(duì)首的元素，一個(gè)隊(duì)尾指針 REAR，指向隊(duì)尾的元素。初始化的時(shí)候，F(xiàn)RONT 和 REAR 都設(shè)置為 -1。

3)入隊(duì)時(shí)

檢查隊(duì)列是否已經(jīng)滿(mǎn)了，需要一個(gè) isFull() 的方法來(lái)判斷;

對(duì)于第一個(gè)元素，設(shè)置 FRONT 的值為 0;

每次在隊(duì)尾插入一個(gè)元素時(shí)，REAR 加 1，然后把隊(duì)尾的元素指向 REAR。

4)出隊(duì)時(shí)

檢查隊(duì)列是否為空，需要一個(gè) isEmpty() 的方法來(lái)判斷;

用一個(gè)臨時(shí)變量來(lái)保存隊(duì)首的元素，以便出隊(duì)后返回;

每次在隊(duì)首刪除一個(gè)元素時(shí)，F(xiàn)RONT 加 1;

如果是最后一個(gè)元素，重置 FRONT 和 REAR 為 -1。

隊(duì)列為空的時(shí)候，F(xiàn)RONT 和 REAR 等于 -1;把元素 1 入隊(duì)的時(shí)候，F(xiàn)RONT 變?yōu)?1，REAR 加 1 變?yōu)? 0，queue[FRONT]=queue[REAR] 為 1;把元素 2 入隊(duì)的時(shí)候，REAR 加 1 變?yōu)?1，queue[REAR] 為 2，queue[FRONT] 仍然為 1;接著，元素 3 入隊(duì);元素 4 入隊(duì);元素 5 入隊(duì)，REAR 變?yōu)?4，queue[REAR] 為 5，queue[FRONT] 仍然為 1。

元素 1 出隊(duì)的時(shí)候，F(xiàn)RONT 為 0，queue[FRONT] 為 1，然后 FRONT 加 1 變?yōu)?1;元素 2 出隊(duì)的時(shí)候，queue[FRONT] 為 2，然后 FRONT 加 1 變?yōu)?2;接著，元素 3 出隊(duì);元素 4 出隊(duì);元素 5 出隊(duì)的時(shí)候，queue[FRONT] 為 5，F(xiàn)RONT 為 4，REAR 為 4，出隊(duì)后，F(xiàn)RONT 和 REAR 重設(shè)為 -1。

假設(shè)隊(duì)列中的元素為 int 類(lèi)型，隊(duì)列的大小為 5，我們可以用 Java 語(yǔ)言來(lái)自定義一個(gè)最簡(jiǎn)單的 queue。它需要 3 個(gè)字段：

• int queue[]，一個(gè) int 類(lèi)型的數(shù)組，來(lái)存放數(shù)據(jù)
• int front，一個(gè) int 類(lèi)型的隊(duì)首標(biāo)記
• int rear，一個(gè) int 類(lèi)型的隊(duì)尾標(biāo)記

class Queue { 
    int SIZE = 5; 
    int items[] = new int[SIZE]; 
    int front, rear; 
} 

初始化隊(duì)列：

Queue() { 
    front = -1; 
    rear = -1; 
} 

入隊(duì)：

void enQueue(int element) { 
    if (isFull()) { 
        System.out.println("隊(duì)列已經(jīng)滿(mǎn)了"); 
    } else { 
        if (front == -1) 
            front = 0; 
        rear++; 
        items[rear] = element; 
        System.out.println("插入 " + element); 
    } 
} 

出隊(duì)：

int deQueue() { 
    int element; 
    if (isEmpty()) { 
        System.out.println("隊(duì)列空了"); 
        return (-1); 
    } else { 
        element = items[front]; 
        if (front >= rear) { 
            front = -1; 
            rear = -1; 
        } 
        else { 
            front++; 
        } 
        System.out.println("刪除 -> " + element); 
        return (element); 
    } 
} 

檢查隊(duì)列是否已經(jīng)滿(mǎn)了：

boolean isFull() { 
    if (front == 0 && rear == SIZE - 1) { 
        return true; 
    } 
    return false; 
} 

檢查隊(duì)列是否為空：

boolean isEmpty() { 
    if (front == -1) 
        return true; 
    else 
        return false; 
} 

來(lái)個(gè) main() 方法測(cè)試下：

void display() { 
    int i; 
    if (isEmpty()) { 
        System.out.println("隊(duì)列為空"); 
    } else { 
        System.out.println("\n隊(duì)首的下標(biāo)-> " + front); 
        System.out.println("元素 -> "); 
        for (i = front; i <= rear; i++) 
            System.out.print(items[i] + "  "); 
 
        System.out.println("\n隊(duì)尾的下標(biāo)-> " + rear); 
    } 
} 
 
public static void main(String[] args) { 
    Queue q = new Queue(); 
 
    // 隊(duì)列為空的時(shí)候不允許出隊(duì) 
    q.deQueue(); 
 
    // enQueue 5 elements 
    q.enQueue(1); 
    q.enQueue(2); 
    q.enQueue(3); 
    q.enQueue(4); 
    q.enQueue(5); 
 
    // 隊(duì)列滿(mǎn)了的時(shí)候不允許入隊(duì) 
    q.enQueue(6); 
 
    q.display(); 
 
    // 出隊(duì) 
    q.deQueue(); 
 
    // 打印 
    q.display(); 
} 

打印結(jié)果如下所示：

隊(duì)列空了 
插入 1 
插入 2 
插入 3 
插入 4 
插入 5 
隊(duì)列已經(jīng)滿(mǎn)了 
 
隊(duì)首的下標(biāo)-> 0 
元素 ->  
1  2  3  4  5   
隊(duì)尾的下標(biāo)-> 4 
刪除 -> 1 
 
隊(duì)首的下標(biāo)-> 1 
元素 ->  
2  3  4  5   
隊(duì)尾的下標(biāo)-> 4 

隊(duì)列空了插入 1插入 2插入 3插入 4插入 5隊(duì)列已經(jīng)滿(mǎn)了隊(duì)首的下標(biāo)-> 0元素 -> 1 2 3 4 5 隊(duì)尾的下標(biāo)-> 4刪除 -> 1隊(duì)首的下標(biāo)-> 1元素 -> 2 3 4 5 隊(duì)尾的下標(biāo)-> 4

好了，這種基本的隊(duì)列已經(jīng)可以正常工作了，但它有一個(gè)問(wèn)題：當(dāng)已經(jīng)出隊(duì)了 N 個(gè)元素后，按理說(shuō)，應(yīng)該可以再入隊(duì) N 個(gè)元素，對(duì)吧?因?yàn)槭〕鰜?lái)了 N 個(gè)空間嘛。

Queue q = new Queue(); 
 
// enQueue 5 elements 
q.enQueue(1); 
q.enQueue(2); 
q.enQueue(3); 
q.enQueue(4); 
q.enQueue(5); 
 
// 出隊(duì) 
q.deQueue(); 
q.deQueue(); 
 
q.enQueue(6); 
q.enQueue(7); 

但事實(shí)上，這段代碼在運(yùn)行的時(shí)候報(bào)錯(cuò)了：

插入 1 
插入 2 
插入 3 
插入 4 
插入 5 
刪除 -> 1 
刪除 -> 2 
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5 
 at com.itwanger.queue.Queue.enQueue(Queue.java:23) 
 at com.itwanger.queue.Queue.main(Queue.java:89) 

看見(jiàn) ArrayIndexOutOfBoundsException 我們就知道，數(shù)組越界了。這是因?yàn)槲覀兪怯脭?shù)組實(shí)現(xiàn)的隊(duì)列，在出隊(duì)的時(shí)候 REAR 并沒(méi)有減小，導(dǎo)致入隊(duì)的時(shí)候 items[rear++]超出了數(shù)組的邊界。

可以把問(wèn)題歸咎于我們實(shí)現(xiàn)隊(duì)列的方式上，也可以淺顯地認(rèn)為基本類(lèi)型的隊(duì)列存在有局限性。隨著入隊(duì)和出隊(duì)的連續(xù)操作，隊(duì)列中的元素在不停地變化，隊(duì)列所占的存儲(chǔ)空間也在分配的連續(xù)空間中不停的移動(dòng)。

當(dāng) REAR 增加到超出數(shù)組大小的范圍之后，隊(duì)列就無(wú)法添加新的元素了，事實(shí)上還有很多空間可以利用，但它們?nèi)匀槐灰殉鲫?duì)的元素占用著——正所謂“附身”啊。除非所有的元素均被移除后， FRONT 和 REAR 被重置，隊(duì)列才能重新使用。

由于基本類(lèi)型的隊(duì)列存在這種局限性，我們就迫切的需要一種新型隊(duì)列的出現(xiàn)——環(huán)形隊(duì)列(Circular queue) 就閃亮登場(chǎng)了。

那環(huán)形隊(duì)列是如何工作的呢?它是怎么解決這個(gè)問(wèn)題的呢?

1)同樣需要一串連續(xù)的存儲(chǔ)空間。

2)初始化的時(shí)候和基本類(lèi)型的隊(duì)列 完全一樣;

3)入隊(duì)時(shí)

• 檢查隊(duì)列是否已經(jīng)滿(mǎn)了，此時(shí)的條件除了 FRONT = 0 && REAR = SIZE + 1， 也就是隊(duì)首有元素，隊(duì)尾也有元素時(shí)，也就是第一次把隊(duì)列填滿(mǎn)時(shí)。還需要再增加一個(gè)：FRONT = REAR + 1，也就是隊(duì)尾緊跟在隊(duì)首后面的時(shí)候，循環(huán)把隊(duì)列填滿(mǎn)時(shí)。代碼如下所示。

boolean isFull() { 
    if (front == 0 && rear == SIZE - 1) { 
        return true; 
    } 
     
    if (front == rear + 1) { 
        return true; 
    } 
    return false; 
} 

• 一旦 REAR 加 1 后超出了所分配的連續(xù)空間，就讓它指向連續(xù)空間的起始位置。也就是說(shuō)，REAR 需要重新輪循了，從 0 開(kāi)始，可以用 (REAR + 1) % SIZE 取余的形式來(lái)表示。代碼如下所示。

void enQueue(int element) { 
    if (isFull()) { 
        System.out.println("隊(duì)列已經(jīng)滿(mǎn)了"); 
    } else { 
        if (front == -1) 
            front = 0; 
        rear = (rear + 1) % SIZE; 
        items[rear] = element; 
        System.out.println("插入 " + element); 
    } 
} 

4)出隊(duì)時(shí)

• 同樣的，當(dāng) FRONT 加 1 超出了所分配的連續(xù)空間，就讓它指向連續(xù)空間的起始位置。也就是說(shuō)，F(xiàn)RONT 需要重新輪循了，從 0 開(kāi)始，可以用 (FRONT + 1) % SIZE 來(lái)表示。代碼如下所示。

int deQueue() { 
    int element; 
    if (isEmpty()) { 
        System.out.println("隊(duì)列空了"); 
        return (-1); 
    } else { 
        element = items[front]; 
        if (front >= rear) { 
            front = -1; 
            rear = -1; 
        } 
        else { 
            front = (front + 1) % SIZE; 
        } 
        System.out.println("刪除 -> " + element); 
        return (element); 
    } 
} 

main() 方法的測(cè)試代碼就不再貼了，和基本類(lèi)型的隊(duì)列時(shí)差別不大。一圖勝千言，我們來(lái)畫(huà)一幅圖表示下環(huán)形隊(duì)列的工作方式。

當(dāng)隊(duì)列第一次被填滿(mǎn)了以后，出隊(duì)了兩個(gè)元素，此時(shí)下標(biāo)為 0 和 1 的兩個(gè)位置空了出來(lái)，然后入隊(duì)元素 6，意味著 6 變成了隊(duì)尾，也就是 REAR 等于 0 了;再入隊(duì)元素 7，7 變成了隊(duì)尾，也就是 REAR 等于 1 了。

現(xiàn)在，來(lái)思考一個(gè)問(wèn)題，假如此時(shí)執(zhí)行 deQueue() 方法出隊(duì)一個(gè)元素時(shí)，哪一個(gè)元素會(huì)被移除呢?答案是元素 3，因?yàn)榇藭r(shí)它在隊(duì)首，之后是元素 4，元素 5，元素 6，元素 7，雖然直觀上看起來(lái)不是那么回事，但如果把它想象成一個(gè)環(huán)形的而不是直線(xiàn)型的就很好理解了。

對(duì)比來(lái)說(shuō)，環(huán)形隊(duì)列比普通類(lèi)型的隊(duì)列在容量的利用上更充分一點(diǎn)。

除了基本類(lèi)型和環(huán)形隊(duì)列之外，隊(duì)列還有優(yōu)先級(jí)隊(duì)列和雙端隊(duì)列，雖然它們都?xì)w到了隊(duì)列這一類(lèi)，但其實(shí)并不遵循 FIFO 的規(guī)則，所以我就打算把它們拎出來(lái)單獨(dú)來(lái)講。

本文轉(zhuǎn)載自微信公眾號(hào)「 沉默王二」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系 沉默王二公眾號(hào)。