順序隊(duì)列

順序隊(duì)列定義

隊(duì)列的底層是數(shù)組，我們常說的隊(duì)列其實(shí)就是順序隊(duì)列，其數(shù)據(jù)結(jié)構(gòu)定義一般是：

1. 隊(duì)頭指針指向數(shù)組第一個元素
2. 隊(duì)尾指針指向數(shù)組最后一個元素的下一個位置

為了避免當(dāng)只有一個元素時，隊(duì)頭和隊(duì)尾重合使處理變得麻煩，所以這里引入了隊(duì)頭和隊(duì)尾兩個指針，假設(shè) front 指針指向隊(duì)頭元素，rear 指針指向隊(duì)尾元素的下一個位置，這樣：

• 當(dāng) front == rear 時，表示這個隊(duì)列是空隊(duì)列
• 當(dāng) front == rear + 1 時，表示這個隊(duì)列中只有一個元素

示意圖如下：

圖片

眾所周知，隊(duì)列是先進(jìn)先出的，那么進(jìn)隊(duì)操作對應(yīng)的步驟就是：先送值到隊(duì)尾，再將隊(duì)尾指針 +1

// 送值到隊(duì)尾
queue[rear] = x;
// 隊(duì)尾指針 +1
rear ++;

出隊(duì)操作：先取出隊(duì)頭元素，再將隊(duì)頭指針 +1

// 取出隊(duì)頭元素
x = queue[Q.front]
// 隊(duì)頭指針 +1
front ++;

假溢出問題

順序隊(duì)列存在假溢出問題 ，就是明明在隊(duì)列中仍然有可以存放元素的空間卻無法執(zhí)行入隊(duì)操作了，舉個例子：

隊(duì)列的大小是 5（數(shù)組容量為 5），一開始是空隊(duì)列，然后依次入隊(duì)了 A、B、C、D：

圖片

然后 A 出隊(duì)，B 出隊(duì)，相應(yīng)的 front 指針會往后移動兩位：

圖片

再入隊(duì)一個新元素 E，此時 front 指針不變，rear 指針需要 +1，已經(jīng)超出了數(shù)組的下標(biāo)范圍，就會導(dǎo)致新元素插入失敗：

圖片

明明隊(duì)列中還有空間，插入元素竟然會失敗？這就是一種假性上溢出現(xiàn)象。

如何解決這個問題呢，有三種：

1. 建立一個足夠大的存儲空間以避免溢出。這樣做空間使用率低，浪費(fèi)存儲空間
2. 移動元素：每當(dāng)出隊(duì)一個元素，就將移動隊(duì)列中所有的已有元素向隊(duì)頭移動一個位置。這樣做很明顯時間復(fù)雜度比較高，效率慢
3. 循環(huán)隊(duì)列：將隊(duì)頭和隊(duì)尾看作是一個首尾相接的循環(huán)隊(duì)列

因此，循環(huán)隊(duì)列是解決順序隊(duì)列假溢出問題的最佳選擇！

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

循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)定義一般是：

1. 隊(duì)列長度固定，即隊(duì)列（數(shù)組）容量有限
2. 隊(duì)列的頭尾相接形成一個環(huán)，當(dāng)隊(duì)尾到達(dá)數(shù)組的最后一個位置時，下一個位置是數(shù)組的第一個位置

具體實(shí)現(xiàn)步驟如下：

1. 定義一個數(shù)組和兩個指針：front 和 rear，分別表示隊(duì)頭和隊(duì)尾的位置。初始時（空隊(duì)列），隊(duì)頭和隊(duì)尾都指向數(shù)組的第一個位置，即 front = rear = 0。
2. 入隊(duì)時，首先檢查隊(duì)列是否已滿，如何判斷隊(duì)列滿？犧牲一個單元來區(qū)分隊(duì)空和隊(duì)滿：即 (rear + 1) % maxsize = front。如果滿了則返回錯誤，否則將元素添加到隊(duì)尾，即 queue[rear] = element，然后將 rear 指針向后移動一位，即 rear = (rear + 1) % capacity。
3. 出隊(duì)時，首先檢查隊(duì)列是否為空，**front == rear 就表示隊(duì)列空**。如果為空則返回錯誤，否則將隊(duì)頭元素取出并返回，即 element = queue[front]，然后將 front 指針向后移動一位，即 front = (front + 1) % capacity。
4. 在隊(duì)列的任何時刻，隊(duì)列中的元素?cái)?shù)量為 (rear - front + capacity) % capacity

示意圖如下：

圖片

以下是一個基于數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列的 Java 代碼示例：

public class CircularQueue {
   // 存儲元素的數(shù)組
    private int[] data;
    private int front, rear;
   // 數(shù)組大小
    private int capacity;

    public CircularQueue(int k) {
        capacity = k;
        data = new int[capacity];
        front = 0;
        rear = 0;
    }

   // 入隊(duì)
    public boolean enqueue(int element) {
        if (isFull()) {
            return false;
        } else {
            data[rear] = element;
            rear = (rear + 1) % capacity;
            return true;
        }
    }
 
   // 出隊(duì)
    public boolean dequeue() {
        if (isEmpty()) {
            return false;
        } else {
            front = (front + 1) % capacity;
            return true;
        }
    }

    // 獲取隊(duì)頭元素
    public int front() {
        if (isEmpty()) {
            return -1;
        } else {
            return data[front];
        }
    }
  
   // 獲取隊(duì)尾元素
    public int rear() {
        if (isEmpty()) {
            return -1;
        } else {
            return data[(rear - 1 + capacity) % capacity];
        }
    }

   // 判斷隊(duì)列是否為空
    public boolean isEmpty() {
        return front == rear;
    }
 
   // 判斷隊(duì)列是否滿
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }
}

簡單總結(jié)就是：

• 初始/隊(duì)空：front = rear
• 出隊(duì)：front = (front + 1) % capacity (最大元素個數(shù))
• 進(jìn)隊(duì)：rear = (rear + 1) % capacity
• 隊(duì)列長度：(rear - front + capacity) % capacity
• 隊(duì)滿（犧牲一個單元來區(qū)分隊(duì)空和隊(duì)滿 ）：(rear + 1) % capacity = front