队列 | C语言+链表实现+基本操作+逐步图解

队列 | C语言+链表实现+基本操作+逐步图解

引用

CSDN

1.

https://blog.csdn.net/m0_73726899/article/details/137126893

前言

本文将详细介绍队列这种数据结构的C语言实现，包括其基本概念、链表实现方式以及各种基本操作。通过图文结合的方式，帮助读者更好地理解队列的原理和实现方法。

正文

1. 队列的基本概念

队列是一种特殊的线性表，其特殊之处在于只允许在一端进行插入数据操作（队尾），在另一端进行删除数据操作（队头）。这种特性使得队列具有"先进先出"（FIFO）的特点。因此，队列中产生了两个专有名词：

• 队尾：进行插入操作的一端
• 队头：进行删除操作的一端

2. 队列的实现

队列可以通过两种方式实现：数组和链表。在实际应用中，链表实现更为常见，因为链表在出队操作时只需要移动指针到下一节点，而数组在出队操作时需要进行头删，效率较低。

3. 队列的结构

队列的结构由以下部分组成：

• 一个单链表，用于存储数据
• 头指针和尾指针，分别指向队头和队尾，便于实现出队和入队操作
• 队列长度

使用两个结构体共同组成队列的结构：

代码实现如下：

typedef int QDataType;
typedef struct QueueNode
{
    struct QueueNode* next; //指向下一节点
    QDataType data;         //存储元素，动态开辟数组
}QNode;
typedef struct Queue
{
    QNode* head; //头指针
    QNode* tail; //尾指针
    int size;    //队长
}Que;

4. 队列的基本操作

1. 初始化队列

队列初始化时为空状态，需要使用指针进行操作，因此传递过来的不能是空指针。初始化时，头指针和尾指针均为空，队列长度为0。

代码实现如下：

void QueueInit(Que* q)
{
    assert(q);
    q->head = q->tail = NULL;
    q->size = 0;
}

2. 入队

入队操作的基本步骤包括：

• 开辟新节点
• 判断队列是否为空
• 如果队列为空，头尾指针均指向新节点
• 如果队列不为空，将新节点添加到队尾

代码实现如下：

void QueuePush(Que* q, QDataType x)
{
    assert(q);
    //开辟结点
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (!newnode) 
    {
        perror("malloc failed");
        exit(-1);
    }
    //数组赋值
    newnode->data = x;
    newnode->next = NULL;
    //队列为空
    if (q->tail == NULL)
    {
        //头尾指针指向新节点
        q->head = q->tail = newnode;
        q->size++;
    }
    else {
        //队列不为空
        q->tail->next = newnode;//原先的队尾 的 next指向新节点
        q->tail = newnode; //尾指针指向新节点
        q->size++;
    }
}

3. 出队

出队操作需要注意以下几点：

• 传过来的指针不为空
• 队列也不为空
• 队列只有一个元素时，直接释放并置空
• 其他情况，更新头指针并释放当前头节点

代码实现如下：

void QueuePop(Que* q)
{
    assert(q);
    assert(q->head && q->tail);//队列不为空
    //只有一个元素  q->head->next == NULL
    //头尾指针均指向它
    if(q->head->next == NULL)
    {
        free(q->head);
        //因此释放掉空间之后，尾指针会成为野指针，必须置空
        q->head = q->tail = NULL;
    }
    else {
        QNode* _new = q->head->next;
        free(q->head);
        q->head = _new;
    }
    //释放掉结点之后，统一，size--
    q->size--;
}

4. 获取头部元素

直接利用头指针获取data

QDataType QueueFront(Que* q)
{
    assert(q);
    assert(q->tail);
    return q->head->data;
}

5. 获取队尾元素

直接利用尾指针获取data

QDataType QueueBack(Que* q)
{
    assert(q);
    assert(q->tail);
    return q->tail->data;
}

6. 队列长度

返回队列的size属性

int QueueSize(Que* q) {
    assert(q);
    return q->size;
}

7. 判断队列是否为空

检查头指针是否为空

bool QueueEmpty(Que* q)
{
    assert(q);
    return q->head == NULL;
}

8. 销毁队列

队列的销毁过程包括：

• 使用媒介指针cur和next进行各个节点之间的销毁
• 全部释放完毕后，将头、尾指针置空
• 队长size置为0

代码实现如下：

void QueueDestroy(Que* q)
{
    QNode* cur = q->head;
    //结点为空时，全部释放完毕
    while (cur)
    {
        QNode* next = cur->next;//存储下一节点的地址信息
        free(cur);//释放当前结点
        cur = next;
    }
    q->head = q->tail = NULL;
    q->size = 0;
}

总结

本文详细介绍了队列这种数据结构的C语言实现，包括其基本概念、链表实现方式以及各种基本操作。希望对大家有所帮助！