From Gossip@caterpillar

Algorithm Gossip: 佇列 - 使用鏈結實作（C語言動態記憶體宣告）

說明

使用陣列來實作佇列，會有佇列空間的限制，如果使用鏈結配合動態記憶體宣告，就不會有長度的限制。

解法

在使用鏈結實作佇列時，為了方便，使用一個空的節點來指向佇列前端第一個元素，這個空節點的data欄位並不儲存資料，而next當作front的角色，如下圖所示：

為了配合以上的空節點，將佇列是否為空的判斷方式，改為front->next是否指向下一個節點來完成，如果front->next指向NULL，表示鏈結中已無下一個資料，所以佇列為空。

由於必須同時維護front與rear兩個資訊，而C語言一次只能傳回一個值，為了簡化程式邏輯，我們將front與rear宣告為全域變數，有興趣的話，請自己試著不設為全域變數來撰寫，這會讓程式變得複雜一些。

實作

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

struct node { 
    int data; 
    struct node *next; 
}; 

typedef struct node Node; 

void createq(); 
void showfront(); 
void addq(int); 
void delq(); 
void showqueue(); 

Node *front, *rear; 

int main(void) { 
    int input, select; 

    createq(); 

    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); 
                addq(input); 
                break; 
            case 2: 
                showfront(); 
                break; 
            case 3: 
                delq(); 
                break; 
            case 4: 
                showqueue(); 
                break; 
            default: 
                printf("\n選項錯誤！"); 
        } 
    } 

    printf("\n"); 

    return 0; 
} 

void createq() { 
    front = rear = (Node*) malloc(sizeof(Node)); 
    front->next = rear->next = NULL; 
} 

void showfront(){ 
    if(front->next == NULL) 
        printf("\n佇列為空！"); 
    else 
        printf("\n頂端值：%d", front->next->data); 
} 

void addq(int data) { 
    Node *newnode; 

    newnode = (Node*) malloc(sizeof(Node)); 

    if(front->next == NULL)  
        front->next = newnode; 
    
    newnode->data = data; 
    newnode->next = NULL; 
    rear->next = newnode; 
    rear = newnode; 
} 

void delq() { 
    Node* tmpnode; 

    if(front->next == NULL) { 
        printf("\n佇列已空！"); 
        return; 
    } 

    tmpnode = front->next; 
    front->next = tmpnode->next; 
    free(tmpnode);    
} 

void showqueue() { 
    Node* tmpnode; 

    tmpnode = front->next; 

    printf("\n佇列內容："); 
    while(tmpnode != NULL) { 
        printf("%d ", tmpnode->data); 
        tmpnode = tmpnode->next; 
    } 
}