C语言数据结构——详细讲解《队列》

前言

• 在上一篇博客中，我们详细探讨了栈这种数据结构，今天，让我们深入了解另一种与栈类似重要的数据结构 —— 队列。

一、队列的概念

• 队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列遵循先进先出的原则
• 入队列：进行插入操作的一端称为队尾。
• 出队列：进行删除操作的一端称为队头。

• 大家思考一个问题，队列的底层结构是数组还是链表

• 基于数组实现的队列
• 优点

实现简单，逻辑清晰；可直接通过索引随机访问元素，时间复杂度为 O (1)。

• 缺点

需预先确定队列大小。若队列元素超数组大小，扩容操作复杂且耗时

• 基于链表实现的队列
• 优点

可动态调整大小，无需预先确定队列长度；队头和队尾的插入、删除操作时间复杂度为 O (1)

• 缺点

每个节点需额外存储指针，占用空间。
无法直接通过索引访问元素，随机访问效率低

二、队列的操作

（一）定义队列结构

• 首先我们需要定义队列链表节点结构体

//定义队列结点的结构
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;

• 队列结点结构中的data成员用于存储队列中的实际数据
• 接下来，我们定义队列结构体本身

//定义队列的结构
typedef struct Queue
{
    QueueNode* phead;  //队头
    QueueNode* ptail;  //队尾
}Queue;

• 接下来需要初始化队列

// 初始化队列
void initQueue(Queue *pq) {
    pq->phead = NULL;
    pq->ptail = NULL;
}

（二）初始化队列

• 在使用队列之前，我们需要对其进行初始化操作，将队头和队尾指针都设置为 NULL，表示队列为空。

// 初始化队列
void initQueue(Queue *pq) 
{
    pq->phead = NULL;
    pq->ptail = NULL;
}

（三）入队列操作

// 入队操作
void enqueue(Queue *pq, int x) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = x;
    newNode->next = NULL;

    if (pq->ptail == NULL) 
    {
        // 队列为空的情况
        pq->phead = newNode;
        pq->ptail = newNode;
    } 
    else 
    {
        pq->ptail->next = newNode;
        pq->ptail = newNode;
    }
}

• 先创建一个新节点，给它分配内存空间，
• 把要入队的元素值赋给新节点的 data，并把 next 设为 NULL。
• 然后看队列是不是空的，如果空，新节点就既是队头又是队尾；
• 如果不空，就把新节点接到队尾节点后面，并更新队尾指针指向新节点

（四）出队列操作

//出队列
int dequeue(Queue* pq)
{
    assert(pq->phead != NULL);
    Node* temp = pq->phead;
    int x = temp->data;
    if (pq->phead == pq->ptail)
    {
        pq->phead = NULL;
        pq->ptail = NULL;
    }
    else
    {
        pq->phead = pq->phead->next;
    }
    free(temp);
    return x;
}

• 从队列的队头取出一个元素并删掉对应的节点。
• 先检查队列不能是空的，然后把队头节点的数据存起来，
• 接着看队列是不是只有一个元素，
• 如果是就把队头和队尾指针都设为 NULL；
• 如果不止一个元素，就更新队头指针指向下一个节点，
• 最后释放原来队头节点的内存并返回取出的元素值。

（五）获取队头元素

// 获取队头元素
int front(Queue* pq)
{
    assert(pq->phead != NULL);
    return pq->phead->data;
}

• 能获取队列的队头元素的值，但不把这个元素从队列里取出来。
• 先得确保队列不是空的，然后直接返回队头节点的 data 值就行

（六）检查队列是否为空

int isEmpty(Queue *pq) 
{
    return pq->front == NULL;
}

• 如果是就说明队列为空，返回相应结果，这样在其他操作前可以先检查下队列状态，避免在空队列上做无效操作

（七）销毁队列

// 释放队列内存
void freeQueue(Queue* pq)
{
    Node* current = pq->phead;
    Node* next;
    while (current != NULL)
    {
        next = current->next;
        free(current);
        current = next;
    }
    pq->phead = NULL;
    pq->ptail = NULL;
}

• 在队列用完后用来释放它占用的内存资源。
• 从队头开始，逐个遍历队列里的节点，释放每个节点的内存，
• 最后把队头和队尾指针都设为 NULL，让队列回到初始的空状态

（三）本文所有代码

1.Queue.h文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 队列结构体
typedef struct Queue {
    Node* phead;
    Node* ptail;
} Queue;

// 初始化队列
void initQueue(Queue* pq) {
    pq->phead = NULL;
    pq->ptail = NULL;
}

//入队列
void enqueue(Queue* pq, int x)
{
    Node* newnode = (Node*)malloc(sizeof(Node));
    newnode->data = x;
    newnode->next = NULL;
    if (pq == NULL)
    {
        pq->phead = newnode;
        pq->ptail = newnode;
    }
    else
    {
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }
}


//出队列
int dequeue(Queue* pq)
{
    assert(pq->phead != NULL);
    Node* temp = pq->phead;
    int x = temp->data;
    if (pq->phead == pq->ptail)
    {
        pq->phead = NULL;
        pq->ptail = NULL;
    }
    else
    {
        pq->phead = pq->phead->next;
    }
    free(temp);
    return x;
}

// 获取队头元素
int front(Queue* pq)
{
    assert(pq->phead != NULL);
    return pq->phead->data;
}


// 检查队列是否为空
int isEmpty(Queue* pq) 
{
    return (pq->phead != NULL) ? 0 : 1;
}



// 释放队列内存
void freeQueue(Queue* pq)
{
    Node* current = pq->phead;
    Node* next;
    while (current != NULL)
    {
        next = current->next;
        free(current);
        current = next;
    }
    pq->phead = NULL;
    pq->ptail = NULL;
}

2.Queue.c文件

#include "Queue.h"
#include <stdio.h>

int main() {
    Queue myQueue;
    initQueue(&myQueue);

    // 先输入一串数据来初始化队列
    int num;
    printf("请输入一串整数，以空格分隔，用于初始化队列，输入非整数结束输入：\n");

    // 逐个读取输入的数据并将其入队
    while (scanf_s("%d", &num) == 1) {
        enqueue(&myQueue, num);
    }

    // 清除输入缓冲区中的剩余字符（例如换行符等）
    while (getchar() != '\n');

    int choice, value;

    do {
        printf("请选择操作：\n");
        printf("1. 入队\n");
        printf("2. 出队\n");
        printf("3. 获取队头元素\n");
        printf("4. 检查队列是否为空\n");
        printf("5. 退出\n");
        scanf_s("%d", &choice);

        switch (choice) {
        case 1:
            printf("请输入要入队的值：");
            scanf_s("%d", &value);
            enqueue(&myQueue, value);
            break;
        case 2:
            if (!isEmpty(&myQueue)) {
                printf("出队元素: %d\n", dequeue(&myQueue));
            }
            else {
                printf("队列为空，无法出队\n");
            }
            break;
        case 3:
            if (!isEmpty(&myQueue)) {
                printf("当前队头元素: %d\n", front(&myQueue));
            }
            else {
                printf("队列为空，无队头元素\n");
            }
            break;
        case 4:
            if (isEmpty(&myQueue)) {
                printf("队列为空\n");
            }
            else {
                printf("队列不为空\n");
            }
            break;
        case 5:
            printf("退出程序\n");
            break;
        default:
            printf("无效的选择，请重新输入\n");
        }

    } while (choice != 5);

    // 释放队列内存
    freeQueue(&myQueue);

    return 0;
}