就幾幅圖，能干趴隊列？
今天繼續(xù)來給大家上一盤硬菜，保證喂個半飽——嗝。和棧一樣，隊列(queue)也是一個非常有用的數(shù)據(jù)結(jié)構(gòu)。同時又非常特殊，它只允許在隊尾(rear)插入元素，在隊首(front)刪除元素，也就是一端進(jìn)，一端出。
在網(wǎng)上購票普及之前，我們大多數(shù)人需要到車站的購票大廳買票，經(jīng)常是排隊排到水泄不通，queue 就和現(xiàn)實中的排隊是一模一樣的，排在隊首的先買到票，然后離開，緊跟著的人移動到隊首，直到隊列消失。
隊列遵循的是 First In First Out，縮寫為 FIFO，也就是先進(jìn)先出，第一個進(jìn)入隊列的第一個先出來。
在上面這幅圖中，1 比 2 先進(jìn)入隊列，也比 2 先出隊列，規(guī)規(guī)矩矩的。
對于隊列這樣一個數(shù)據(jù)結(jié)構(gòu)來說，它有兩個常見的動作：
- enqueue，我個人喜歡把它譯作入隊，指的是把元素放入隊列這個動作。
- dequeue，出隊，指的是把元素從隊列中移除這個動作。
明白了隊列的基本操作后，我們來深入地思考一下，隊列是如何工作的。
1) 建立順序的隊列結(jié)構(gòu)需要為其靜態(tài)分配或者動態(tài)申請一串連續(xù)的存儲空間。
2)然后設(shè)置兩個指針進(jìn)行管理：一個隊首指針 FRONT，指向隊首的元素，一個隊尾指針 REAR，指向隊尾的元素。初始化的時候，F(xiàn)RONT 和 REAR 都設(shè)置為 -1。
3)入隊時
檢查隊列是否已經(jīng)滿了，需要一個 isFull() 的方法來判斷;
對于第一個元素，設(shè)置 FRONT 的值為 0;
每次在隊尾插入一個元素時，REAR 加 1，然后把隊尾的元素指向 REAR。
4)出隊時
檢查隊列是否為空，需要一個 isEmpty() 的方法來判斷;
用一個臨時變量來保存隊首的元素，以便出隊后返回;
每次在隊首刪除一個元素時，F(xiàn)RONT 加 1;
如果是最后一個元素，重置 FRONT 和 REAR 為 -1。
隊列為空的時候，F(xiàn)RONT 和 REAR 等于 -1;把元素 1 入隊的時候，F(xiàn)RONT 變?yōu)?1，REAR 加 1 變?yōu)? 0，queue[FRONT]=queue[REAR] 為 1;把元素 2 入隊的時候，REAR 加 1 變?yōu)?1，queue[REAR] 為 2，queue[FRONT] 仍然為 1;接著，元素 3 入隊;元素 4 入隊;元素 5 入隊，REAR 變?yōu)?4，queue[REAR] 為 5，queue[FRONT] 仍然為 1。
元素 1 出隊的時候，F(xiàn)RONT 為 0，queue[FRONT] 為 1，然后 FRONT 加 1 變?yōu)?1;元素 2 出隊的時候，queue[FRONT] 為 2，然后 FRONT 加 1 變?yōu)?2;接著，元素 3 出隊;元素 4 出隊;元素 5 出隊的時候，queue[FRONT] 為 5，F(xiàn)RONT 為 4，REAR 為 4，出隊后，F(xiàn)RONT 和 REAR 重設(shè)為 -1。
假設(shè)隊列中的元素為 int 類型，隊列的大小為 5，我們可以用 Java 語言來自定義一個最簡單的 queue。它需要 3 個字段：
- int queue[]，一個 int 類型的數(shù)組，來存放數(shù)據(jù)
- int front，一個 int 類型的隊首標(biāo)記
- int rear，一個 int 類型的隊尾標(biāo)記
- class Queue {
- int SIZE = 5;
- int items[] = new int[SIZE];
- int front, rear;
- }
初始化隊列：
- Queue() {
- front = -1;
- rear = -1;
- }
入隊：
- void enQueue(int element) {
- if (isFull()) {
- System.out.println("隊列已經(jīng)滿了");
- } else {
- if (front == -1)
- front = 0;
- rear++;
- items[rear] = element;
- System.out.println("插入 " + element);
- }
- }
出隊：
- int deQueue() {
- int element;
- if (isEmpty()) {
- System.out.println("隊列空了");
- return (-1);
- } else {
- element = items[front];
- if (front >= rear) {
- front = -1;
- rear = -1;
- }
- else {
- front++;
- }
- System.out.println("刪除 -> " + element);
- return (element);
- }
- }
檢查隊列是否已經(jīng)滿了：
- boolean isFull() {
- if (front == 0 && rear == SIZE - 1) {
- return true;
- }
- return false;
- }
檢查隊列是否為空：
- boolean isEmpty() {
- if (front == -1)
- return true;
- else
- return false;
- }
來個 main() 方法測試下：
- void display() {
- int i;
- if (isEmpty()) {
- System.out.println("隊列為空");
- } else {
- System.out.println("\n隊首的下標(biāo)-> " + front);
- System.out.println("元素 -> ");
- for (i = front; i <= rear; i++)
- System.out.print(items[i] + " ");
- System.out.println("\n隊尾的下標(biāo)-> " + rear);
- }
- }
- public static void main(String[] args) {
- Queue q = new Queue();
- // 隊列為空的時候不允許出隊
- q.deQueue();
- // enQueue 5 elements
- q.enQueue(1);
- q.enQueue(2);
- q.enQueue(3);
- q.enQueue(4);
- q.enQueue(5);
- // 隊列滿了的時候不允許入隊
- q.enQueue(6);
- q.display();
- // 出隊
- q.deQueue();
- // 打印
- q.display();
- }
打印結(jié)果如下所示：
- 隊列空了
- 插入 1
- 插入 2
- 插入 3
- 插入 4
- 插入 5
- 隊列已經(jīng)滿了
- 隊首的下標(biāo)-> 0
- 元素 ->
- 1 2 3 4 5
- 隊尾的下標(biāo)-> 4
- 刪除 -> 1
- 隊首的下標(biāo)-> 1
- 元素 ->
- 2 3 4 5
- 隊尾的下標(biāo)-> 4
隊列空了插入 1插入 2插入 3插入 4插入 5隊列已經(jīng)滿了隊首的下標(biāo)-> 0元素 -> 1 2 3 4 5 隊尾的下標(biāo)-> 4刪除 -> 1隊首的下標(biāo)-> 1元素 -> 2 3 4 5 隊尾的下標(biāo)-> 4
好了，這種基本的隊列已經(jīng)可以正常工作了，但它有一個問題：當(dāng)已經(jīng)出隊了 N 個元素后，按理說，應(yīng)該可以再入隊 N 個元素，對吧?因為省出來了 N 個空間嘛。
- Queue q = new Queue();
- // enQueue 5 elements
- q.enQueue(1);
- q.enQueue(2);
- q.enQueue(3);
- q.enQueue(4);
- q.enQueue(5);
- // 出隊
- q.deQueue();
- q.deQueue();
- q.enQueue(6);
- q.enQueue(7);
但事實上，這段代碼在運(yùn)行的時候報錯了：
- 插入 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)
看見 ArrayIndexOutOfBoundsException 我們就知道，數(shù)組越界了。這是因為我們是用數(shù)組實現(xiàn)的隊列，在出隊的時候 REAR 并沒有減小，導(dǎo)致入隊的時候 items[rear++]超出了數(shù)組的邊界。
可以把問題歸咎于我們實現(xiàn)隊列的方式上，也可以淺顯地認(rèn)為基本類型的隊列存在有局限性。隨著入隊和出隊的連續(xù)操作，隊列中的元素在不停地變化，隊列所占的存儲空間也在分配的連續(xù)空間中不停的移動。
當(dāng) REAR 增加到超出數(shù)組大小的范圍之后，隊列就無法添加新的元素了，事實上還有很多空間可以利用，但它們?nèi)匀槐灰殉鲫牭脑卣加弥?mdash;—正所謂“附身”啊。除非所有的元素均被移除后， FRONT 和 REAR 被重置，隊列才能重新使用。
由于基本類型的隊列存在這種局限性，我們就迫切的需要一種新型隊列的出現(xiàn)——環(huán)形隊列(Circular queue) 就閃亮登場了。
那環(huán)形隊列是如何工作的呢?它是怎么解決這個問題的呢?
1)同樣需要一串連續(xù)的存儲空間。
2)初始化的時候和基本類型的隊列 完全一樣;
3)入隊時
- 檢查隊列是否已經(jīng)滿了，此時的條件除了 FRONT = 0 && REAR = SIZE + 1， 也就是隊首有元素，隊尾也有元素時，也就是第一次把隊列填滿時。還需要再增加一個：FRONT = REAR + 1，也就是隊尾緊跟在隊首后面的時候，循環(huán)把隊列填滿時。代碼如下所示。
- boolean isFull() {
- if (front == 0 && rear == SIZE - 1) {
- return true;
- }
- if (front == rear + 1) {
- return true;
- }
- return false;
- }
- 一旦 REAR 加 1 后超出了所分配的連續(xù)空間，就讓它指向連續(xù)空間的起始位置。也就是說，REAR 需要重新輪循了，從 0 開始，可以用 (REAR + 1) % SIZE 取余的形式來表示。代碼如下所示。
- void enQueue(int element) {
- if (isFull()) {
- System.out.println("隊列已經(jīng)滿了");
- } else {
- if (front == -1)
- front = 0;
- rear = (rear + 1) % SIZE;
- items[rear] = element;
- System.out.println("插入 " + element);
- }
- }
4)出隊時
- 同樣的，當(dāng) FRONT 加 1 超出了所分配的連續(xù)空間，就讓它指向連續(xù)空間的起始位置。也就是說，F(xiàn)RONT 需要重新輪循了，從 0 開始，可以用 (FRONT + 1) % SIZE 來表示。代碼如下所示。
- int deQueue() {
- int element;
- if (isEmpty()) {
- System.out.println("隊列空了");
- 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() 方法的測試代碼就不再貼了，和基本類型的隊列時差別不大。一圖勝千言，我們來畫一幅圖表示下環(huán)形隊列的工作方式。
當(dāng)隊列第一次被填滿了以后，出隊了兩個元素，此時下標(biāo)為 0 和 1 的兩個位置空了出來，然后入隊元素 6，意味著 6 變成了隊尾，也就是 REAR 等于 0 了;再入隊元素 7，7 變成了隊尾，也就是 REAR 等于 1 了。
現(xiàn)在，來思考一個問題，假如此時執(zhí)行 deQueue() 方法出隊一個元素時，哪一個元素會被移除呢?答案是元素 3，因為此時它在隊首，之后是元素 4，元素 5，元素 6，元素 7，雖然直觀上看起來不是那么回事，但如果把它想象成一個環(huán)形的而不是直線型的就很好理解了。
對比來說，環(huán)形隊列比普通類型的隊列在容量的利用上更充分一點。
除了基本類型和環(huán)形隊列之外，隊列還有優(yōu)先級隊列和雙端隊列，雖然它們都?xì)w到了隊列這一類，但其實并不遵循 FIFO 的規(guī)則，所以我就打算把它們拎出來單獨(dú)來講。
本文轉(zhuǎn)載自微信公眾號「 沉默王二」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系 沉默王二公眾號。
