From Gossip@caterpillar

Algorithm Gossip: 佇列 - 使用陣列實作

說明

佇列是一種先進先出的資料結構，想像您在管子中放入球，最先放入的球在另一端會最先跑出來，在這邊介紹如何使用陣列來實作佇列。

解法

使用陣列來實作佇列，我們必須保留兩個旗標，假設front指向佇列的前端，rear向佇列的後端，我們每次從佇列後端加入一個資料，rear就加1指向最後一個資料，每次從佇列前端取出一個資料，front就加1指向佇列的最前端，如下圖所示：
Quene

這是最簡單的佇列實作，但是由於陣列的大小必須先決定，所以這種線性的結構有個問題，front與rear會到達陣列的後端，而這個陣列就不能再使用了， 為了解決這個問題，將陣列當作環狀來使用，當front或rear到達陣列後端時，就重新從陣列前端再循環，也就是形成環狀佇列，如下圖所示：
Quene


不過陣列的容量還是受限制，所以這個陣列還是會滿的，當front = rear時，佇列就滿了；佇列的基本操作有五項：新增佇列、加入資料、顯示前端資料、取出前端資料、顯示所有的佇列元素。

實作

  • C 
#include <stdio.h> 
#include <stdlib.h> 
#define N 10 

void createq(int[], int*, int*); 
void showfront(int[], int, int); 
void add(int[], int*, int*, int); 
void del(int[], int*, int*); 
void showqueue(int[], int, int); 

int main(void) { 
    int queue[N]; 
    int front, rear; 
    int input, select; 

    createq(queue, &front, &rear); 

    while(1) { 
        printf("\n\n請輸入選項(-1結束)："); 
        printf("\n(1)插入值至佇列"); 
        printf("\n(2)顯示佇列前端"); 
        printf("\n(3)刪除前端值"); 
        printf("\n(4)顯示所有內容"); 
        printf("\n$c>"); 
        scanf("%d", &select); 
        
        if(select == -1) 
            break; 

        switch(select) { 
            case 1: 
                printf("\n輸入值："); 
                scanf("%d", &input); 
                add(queue, &front, &rear, input); 
                break; 
            case 2: 
                showfront(queue, front, rear); 
                break; 
            case 3: 
                del(queue, &front, &rear); 
                break; 
            case 4: 
                showqueue(queue, front, rear); 
                break; 
            default: 
                printf("\n選項錯誤！"); 
        } 
    } 

    printf("\n"); 

    return 0; 
} 

void createq(int queue[], int* front, int* rear) { 
    int i; 

    for(i = 0; i < N; i++) 
        queue[i] = 0; 

    *front = *rear = 0; 
} 

void showfront(int queue[], int front, int rear) { 
    if(front == rear) 
        printf("\n佇列為空！"); 
    else 
        printf("%d", queue[(front+1) % N]); 
} 

void add(int queue[], int* front, int* rear, int data) { 
    int f, r; 
    f = *front; 
    r = *rear; 
    r = (r+1) % N; 

    if(f == r) { 
        printf("\n佇列已滿！"); 
        return; 
    } 

    queue[r] = data; 
    *rear = r; 
} 

void del(int queue[], int* front, int* rear) { 
    int f, r; 
    f = *front; 
    r = *rear; 

    if(f == r) { 
        printf("\n佇列為空！"); 
        return; 
    } 

    f = (f+1) % N; 
    *front = f; 
} 

void showqueue(int queue[], int front, int rear) { 
    int i; 

    printf("\n佇列內容："); 
    for(i = (front+1) % N; i <= rear; i++) 
        printf("%d ", queue[i]); 
}

補充

您如果仔細演算過上面的環狀佇列，您會發現有一個空間會被浪費掉，這是因為判斷佇列已滿或已空的條件都是front = rear，浪費一個空間對現在的電腦記憶體如此足夠來說，並不是個大問題，如果您一定要解決這個問題，可以多使用一個flag來判斷，如果flag設定為 1且front = rear，則表示佇列已滿，如果flag設定為0則front = rear，則表示佇列已空，這樣就不會浪費一個佇列空間了，提供改良後的虛擬碼如下： 
Procedure add(queue, n, front, rear, flag, data) 
    if(front = rear and flag = 1) 
        then call QUEUE_FULL 
    queue(rear) <- data 
    if(front = rear) 
       then flag <- 1 
end add 

Procedure del(queue, n, front, rear, flag, data) 
    if(front = rear and flag = 0) 
        then call QUEUE_EMPTY 
    front <- (front+1) mod n 
    if(front = rear) 
        then flag <- 1 
end del