【C语言数据结构】队列-链式存储(链队列)

---

---

代码实现

#include
#include
#include

//定义元素数据类型
#define ElemType int

//定义链队列的数据结构体
typedef struct LinkNode {
    //保存数据元素
    ElemType data;

    //指向下一个结点(这个要在front和rear的基础上来用)
    struct LinkNode *next;
} LinkNode;

//定义队首队尾指针结构体(这个才是用于进行各种操作的结构体)
typedef struct {
    //定义队首队尾指针(这下真的是指针了)
    LinkNode *front, *rear;
} *LinkQueue;

//初始化队列
void InitQueue(LinkQueue *queue) {
    //为整个队列指针先分配一个内存空间
    (*queue) = (LinkQueue)malloc(sizeof(LinkNode));
    
    //将队首队尾指针都置空，表明现在整个链队列还为空，没有数据
    (*queue)->front = NULL;
    (*queue)->rear = NULL;
}

//判断队列是否为空
bool QueueEmpty(LinkQueue queue) {
    //这里只需要看front指针是否为空就行了，为什么呢？
    //因为如果添加了一个元素，那么front和rear都需要指向那个元素。如果再加一个元素，那么front指针不动，rear指针指向下一个结构体
    //如果要删除一个元素，那么front指针指向下一个结构体，释放上一个结构体的内存空间。
    //因此可以知道，如果队列为空，那么front指针一定为空
    return queue->front == NULL;
}

//入队操作
bool EnQueue(LinkQueue *queue, ElemType e) {
    //先建立一个新的结构体结点
    LinkNode *newNode = (LinkNode *) malloc(sizeof(LinkNode));

    if (newNode == NULL) {
        // 内存分配失败，返回错误
        return false;
    }

    //将元素值赋给newNode里
    newNode->data = e;
    //不要忘了把新节点的next置空，否则会出现野指针
    newNode->next = NULL;

    //如果队列现在没有元素，那么front和rear都指向这个结构体
    if (QueueEmpty(*queue)) {
        (*queue)->front = newNode;
        (*queue)->rear = newNode;
    }
        //否则当前rear的下一个结点就是这个新结点，并将rear移动到新节点上
    else {
        (*queue)->rear->next = newNode;
        (*queue)->rear = newNode;
    }
}

//出队操作
bool DeQueue(LinkQueue *queue, ElemType *e) {
    //如果队列为空，就不用出队了
    if (QueueEmpty(*queue))
        return false;

    //先把当前front的元素赋值给e，然后将front后移
    *e = (*queue)->front->data;
    (*queue)->front = (*queue)->front->next;

    return true;
}

//读取队头元素
bool GetHead(LinkQueue queue, ElemType *e) {
    //如果队列为空,读取失败
    if (QueueEmpty(queue))
        return false;

    //把当前front的元素赋值给e
    *e = (*queue).front->data;

    return true;
}

int main(){
    //定义队列
    LinkQueue queue;
    ElemType Elem;

    //初始化队列
    InitQueue(&queue);

    //入队元素
    EnQueue(&queue,1);
    EnQueue(&queue,2);
    EnQueue(&queue,3);
    EnQueue(&queue,4);

    //读取当前队头元素
    GetHead(queue,&Elem);
    printf("当前队头元素为:%d\n",Elem);

    //依次出队元素，并打印出队的元素
    DeQueue(&queue,&Elem);
    printf("出队的元素为:%d\n",Elem);
    DeQueue(&queue,&Elem);
    printf("出队的元素为:%d\n",Elem);
    DeQueue(&queue,&Elem);
    printf("出队的元素为:%d\n",Elem);
    DeQueue(&queue,&Elem);
    printf("出队的元素为:%d\n",Elem);

    return 0;
}
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
111
112
113
114
115
116
117
118
119
120
121
122
123