用 C 语言实现队列数据结构

简介

在这个项目中，你将学习如何用C语言实现一个队列数据结构。队列在计算机科学中被广泛使用，例如，在用于在计算机中传输数据的消息队列中。

👀 预览

$ gcc queue.c -o queue
$./queue
11250

🎯 任务

在这个项目中，你将学习：

• 如何实现 front() 方法以返回队列中第一个元素的值
• 如何实现 pop() 方法以从队列中移除并返回第一个元素
• 如何实现 count() 方法以返回队列中当前元素的数量
• 如何实现 is_empty() 方法以检查队列是否为空

🏆 成果

完成这个项目后，你将能够：

• 理解队列数据结构的基本操作
• 用C语言实现队列的核心方法
• 应用你对队列的知识来解决实际问题

Skills Graph

实现 front() 方法

在这一步中，你将学习如何实现队列的 front() 方法。

front() 方法应返回队列中第一个元素的值。如果队列为空，该方法应使用 exit(-1) 退出程序。

按照以下步骤完成此步骤：

1. 打开位于 /home/labex/project/queue.c 的 queue.c 文件。
2. 在代码中找到 front() 方法。
3. 按如下方式实现 front() 方法：

static int front() {
    if(!phead) {
        exit(-1);
    }
    return phead->val;
}

front() 方法首先检查 phead 指针是否为 NULL，这表示队列为空。如果队列为空，该方法使用 exit(-1) 退出程序。

如果队列不为空，该方法返回存储在 phead 节点中的值，该值表示队列的第一个元素。

实现 pop() 方法

在这一步中，你将学习如何实现队列的 pop() 方法。

pop() 方法应该从队列中移除并返回第一个元素。如果队列为空，该方法应该使用 exit(-1) 退出程序。

按照以下步骤完成此步骤：

1. 打开位于 /home/labex/project/queue.c 的 queue.c 文件。
2. 在代码中找到 pop() 方法。
3. 按如下方式实现 pop() 方法：

static int pop() {
    if(!phead) {
        exit(-1);
    }
    int val = phead->val;
    phead = phead->next;
    return val;
}

pop() 方法首先检查 phead 指针是否为 NULL，这表示队列为空。如果队列为空，该方法使用 exit(-1) 退出程序。

如果队列不为空，该方法存储 phead 节点的值，该值代表队列的第一个元素。然后，它将 phead 指针更新为下一个节点，从而有效地从队列中移除第一个元素。最后，该方法返回存储的值。

实现 count() 方法

在这一步中，你将学习如何实现队列的 count() 方法。

count() 方法应该返回队列中当前元素的数量。

按照以下步骤完成此步骤：

1. 打开位于 /home/labex/project/queue.c 的 queue.c 文件。
2. 在代码中找到 count() 方法。
3. 按如下方式实现 count() 方法：

static int count() {
    int cnt = 0;
    for(struct node* p = phead; p; p=p->next) {
        cnt++;
    }
    return cnt;
}

count() 方法将一个 cnt 变量初始化为 0。然后，它通过跟随 phead 节点及其后继节点的 next 指针来遍历队列。对于遇到的每个节点，它都会增加 cnt 变量的值。最后，该方法返回 cnt 的值，该值表示队列中的元素数量。

实现 is_empty() 方法

在这一步中，你将学习如何实现队列的 is_empty() 方法。

如果队列为空，is_empty() 方法应返回 1，否则返回 0。

按照以下步骤完成此步骤：

1. 打开位于 /home/labex/project/queue.c 的 queue.c 文件。
2. 在代码中找到 is_empty() 方法。
3. 按如下方式实现 is_empty() 方法：

static int is_empty() {
    return phead == NULL;
}

is_empty() 方法只是检查 phead 指针是否为 NULL，这表示队列为空。如果 phead 为 NULL，该方法返回 1，表示队列为空。否则，它返回 0，表示队列不为空。

恭喜你！你现在已经实现了队列数据结构所需的所有方法。现在你可以编译并执行程序来测试队列的功能。

4. 编译并执行：

$ gcc queue.c -o queue
$./queue
00000

预期输出如下：

$ gcc queue.c -o queue
$./queue
11250

总结

恭喜你！你已经完成了这个项目。你可以在 LabEx 中练习更多实验来提升你的技能。