队列-使用链结实作

说明

使用阵列来实作伫列（队列），会有伫列空间的限制，如果使用链结配合动态记忆体宣告，就不会有长度的限制。

解法

在使用链结实作伫列时，为了方便，使用一个空的节点来指向伫列前端第一个元素，这个空节点的data栏位并不储存资料，而next当作front的角色，如下图所示：

为了配合以上的空节点，将伫列是否为空的判断方式，改为front->next是否指向下一个节点来完成，如果front->next指向NULL，表示链结中已无下一个资料，所以伫列为空。

由于必须同时维护front与rear两个资讯，而C语言一次只能传回一个值，为了简化程式逻辑，我们将front与rear宣告为全域变数，有兴趣的话，请自己试着不设为全域变数来撰写，这会让程式变得复杂一些。

参考代码

C

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110


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

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

typedef struct node getnode; 

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

getnode *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 = (getnode*) malloc(sizeof(getnode)); 
    front->next = rear->next = NULL; 
} 

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

void addq(int data) { 
    getnode *newnode; 

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

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

void delq() { 
    getnode* tmpnode; 

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

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

void showqueue() { 
    getnode* tmpnode; 

    tmpnode = front->next; 

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