C语言实现队列数据结构思路与代码详解

JAY.LIN 收录于数据结构 C

2025-03-12 约 1438 字预计阅读 3 分钟

https://bing.ee123.net/img/rand?artid=146213703

C语言实现队列数据结构：思路与代码详解

作者主页：

一、引言

队列
是一种重要的
数据结构
，遵循
先进先出
（FIFO）的原则。在C语言中，我们可以通过自定义结构体和一系列操作函数来实现一个队列。
本文将详细介绍如何实现一个简单的队列，并对代码的各个部分进行深入分析。

二、整体思路

队列的实现主要涉及队列节点的定义、队列结构体的定义以及对队列的各种操作，如初始化、入队、出队、获取队头和队尾元素、判断队列是否为空和获取队列大小等。我们将这些操作模块化，每个函数负责一个特定的功能，使得代码结构清晰，易于维护和扩展。

三、代码模块分析

（一）头文件包含与宏定义

c
  
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 

_CRT_SECURE_NO_WARNINGS 宏定义用于 关闭Visual Studio中一些函数的安全警告。 后面依次包含了标准输入输出库、标准库、布尔类型库和断言库，为后续代码提供必要的功能支持。

（二）数据类型定义

c
  
typedef int QDatatype;
typedef struct QueueNode
{
    struct QueueNode* next;
    QDatatype data;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int size;
}Queue;
 

- QDatatype 定义为 int 类型，表示队列中存储的数据类型，这里是整型， 也可以根据实际需求改为其他类型。

- QueueNode 结构体 定义了队列节点，包含一个指向下一个节点的指针 next 和存储数据的 data 成员。

- Queue 结构体表示整个队列，包含指向队头的指针 head 、指向队尾的指针 tail 和记录队列元素个数的 size 。

（三）队列操作函数

1. 队列初始化

c
  
void QueueInit(Queue* pq)
{
    pq->head = pq->tail = NULL;
    pq->size = 0;
}
 

QueueInit 函数 用于 初始化一个队列 ，将队头和队尾指针设为 NULL ，队列大小设为 0 。

2. 队列销毁

c
  
void QueueDestroy(Queue* pq)
{
    assert(pq);
    Queue* cur = pq->head;
    while (cur)
    {
        pq->head = pq->head->next;
        free(cur);
        cur = pq->head;
    }
    pq->head = pq->tail = NULL;
    pq->size = 0;
}
 

QueueDestroy 函数 用于释放队列占用的内存空间。通过遍历队列，逐个释放每个节点，最后将队头、队尾指针设为 NULL ，队列大小设为 0 。

3. 入队操作

c
  
void QueuePush(Queue* pq, QDatatype x)
{
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        return;
    }
    newnode->data = x;
    newnode->next = NULL;

    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
    pq->size++;
}
 

QueuePush 函数 用于将一个元素入队。首先 分配一个新节点的内存空间 ，若分配失败则打印错误信息并返回。然后将新节点的数据设为传入的元素值， next 指针设为 NULL 。如果队列为空，则新节点既是队头也是队尾；否则将新节点连接到队尾，并更新队尾指针。最后队列大小加 1 。

4. 出队操作

c
  
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head != NULL);

    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
    pq->size--;
}
 

QueuePop 函数

用于将队头元素出队。首先进行 断言，确保队列指针有效且队列不为空 。如果队列只有一个元素，释放队头节点并将队头、队尾指针设为 NULL ；否则保存队头节点的下一个节点，释放队头节点，然后将队头指针指向下一个节点。最后队列大小减 1 。

5. 获取队头元素

c
  
QDatatype QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}

QueueFront 函数 用于获取队头元素的值。先进行断言确保队列有效且不为空，然后返回队头节点的数据。

6. 获取队尾元素

c
  
QDatatype QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}
 

QueueBack 函数 用于获取队尾元素的值。同样先进行断言确保队列有效且不为空，然后返回队尾节点的数据。

7. 获取队列大小

c
  
int QueueSize(Queue* pq)
{
    return pq->size;
}
 
 
 QueueSize  函数直接返回队列结构体中记录的元素个数。
 

8. 判断队列是否为空

c
  
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}
 

QueueEmpty 函数 通过判断队头指针是否为 NULL 来确定队列是否为空，为空则返回 true ，否则返回 false 。

（四）主函数测试

c
  
int main()
{
    Queue Q;
    QueueInit(&Q);
    QueuePush(&Q, 1);
    QueuePush(&Q, 2);
    QueuePush(&Q, 3);
    QueuePush(&Q, 4);
    QueuePush(&Q, 5);
    while (!QueueEmpty(&Q))
    {
        printf("%d ", QueueFront(&Q));
        QueuePop(&Q);
    }
    printf("\n");
    QueueDestroy(&Q);
    return 0;
}
 

在 main 函数 中，我们对实现的队列进行了测试。首先初始化一个队列，然后依次将 1 到 5 这五个元素入队，接着通过循环不断获取队头元素并打印，同时将其出队，直到队列为空。最后销毁队列，释放内存。

四、总结

通过以上模块化的代码实现，我们完成了一个基本的队列数据结构。每个函数都有明确的功能，使得代码逻辑清晰，易于理解和维护。在实际应用中，可以根据具体需求对队列进行进一步的扩展和优化，如添加更多的操作函数或者改变数据存储类型等。