【演算】佇列 - Queue

　　與堆疊(stack)類似，佇列(queue)也是一種是一種同質元素集合的資料結構。與之不同的是，佇列只允許資料在後端(rear)進行插入(add)操作、在前端(front)進行刪除(delete)操作。

　　同樣的，讓我們舉個實例：相對於堆疊的疊盤子，你可以把佇列想像成一個正在排隊買甜甜圈的隊伍。每執行一次 "delete" 的動作就像是隊伍最前端，成功的買到甜甜圈而離開隊伍。而執行一次 "add" 就像是多了一個想買甜甜圈的客人，而在隊伍的最後端開始排隊(請忽略掉插隊問題)。

　　也因此，不同於堆疊的 LIFO，佇列的操作方式被稱為 FIFO (First In First Out，先入先出)。換句話說，就是越早加入佇列的人(資料)會越早離開佇列。

　　所以，佇列的應用範圍也相當廣泛。從剛剛舉例說明的排隊、圖形的廣度追蹤、使用印表機時的列印佇列等等，都可以見到佇列應用的蹤影。


　　而模擬一個佇列的運作，最簡單的方式還是使用陣列。同樣定義一個大小為 MAX_SIZE 的陣列，並使用兩個變數 front 與 rear 分別代表佇列的前後端。以下是一個簡易佇列實現的虛擬碼實例：

void add(Queue &queue, Type data)
{
    Index front, rear;

    if (rear = MAX_SIZE)
    {
        print("The queue is full!");
    }
    else
    {
        stack[rear] = data;
        rear = rear + 1;
    }
}

void delete(Queue &queue)
{
    Index front, rear;

    if (front = rear)
    {
        print "The queue is empty!";
    }
    else
    {
        front = front + 1;
    }
}

　　同樣的，陣列之外模擬方式與 C++ STL 實現的佇列相關函式這裡我們不討論，請有興趣者自行查詢相關資料。

　　以下是 C 使用陣列實現的原始碼，可以參考看看：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10

void addQ(int);
void deleteQ(void);

int queue[MAX_SIZE], front = 0, rear = 0;

int main(void)
{
    addQ(0);
    addQ(1);
    deleteQ();
    addQ(2);
    addQ(3);
    addQ(4);
    deleteQ();
    deleteQ();
    addQ(5);
    addQ(6);
    addQ(7);
    deleteQ();
    deleteQ();
    deleteQ();
    deleteQ();
    deleteQ();

    system("pause");
}

void addQ(int data)
{
    if (rear == MAX_SIZE)
    {
        printf("The queue is full!\n");
    }
    else
    {
        queue[rear++] = data;
    }
}

void deleteQ(void)
{
    if (front == rear)
    {
        printf("The stack is empty!\n");
    }
    else
    {
        printf("%d\n", queue[front++]);
    }
}