队列

THEDI2025-11-082025-11-08

队列

队列介绍

队列（Queue）：一种线性表数据结构，遵循先进先出FIFO(First In First Out)原则，只允许在一端插入元素（队尾），在另一端删除元素（队头）。

典型场景：排队、缓冲区、消息队列、广度优先搜索（BFS）、生产者-消费者等。
逻辑概念：
- front（队头）：指向队列中要被取出的元素。
- rear（队尾）：指向下一个可插入的位置或当前队尾（实现上有细微差别）。
- enqueue（入队/入列）与 dequeue（出队/出列）。

基本操作

入队（enqueue）：在队尾插入元素
出队（dequeue）：从队头删除元素

队列的实现方式

与线性表类似，队列常见的存储方式有两种：顺序存储 和 链式存储。

顺序存储队列：使用一段连续的存储空间（如数组），依次存放队列中从队头到队尾的元素。通过指针front标记队头元素的位置，rear标记队尾元素的位置。
链式存储队列：采用单链表实现，元素按插入顺序依次链接。front指向链表的头节点（即队头元素），rear指向链表的尾节点（即队尾元素）。

需要注意的是，front 和 rear 的具体指向方式可能因实现细节而异。为简化算法或代码，有时front会指向队头元素的前一个位置，rear也可能指向队尾元素的下一个位置。具体以实际实现为准。

顺序队列

这种方法实现较为简单，入队和出队只需要控制front和rear指针的移动即可。

但是这种方法在队列满的时候(queue->rear == queue->size)的时候，就无法再插入新元素，即使前面有空位也无法利用，导致假溢出的问题

假溢出：指队列存储区未满时发生溢出的现象。该现象常见于顺序存储队列结构中：顺序队列的前端有空间但因未复用导致队尾指针到达数组末尾时无法再入队，造成“假满”现象。

如图为初始队列：

入队出队后造成的假溢出：前面有空间但是无法入队

为解决这个问题，常用两种方法：

方法一：每次出队后整体前移元素

这样可以利用前面的空位，但每次出队都要移动所有元素，效率低，时间复杂度O(n)，不推荐。

方法二：使用循环队列

将队列的首尾视为相连，通过取模运算实现指针的循环移动，从而充分利用存储空间。采用循环队列后，所有基本操作的时间复杂度均为O(1)，高效且无假溢出问题。

循环队列(顺序存储循环队列)

**循环队列: **是一种特殊的队列结构，使用数组完成，它将顺序队列的数组看作一个首尾相接的环形空间，从而解决了顺序队列中可能出现的假溢出问题。在循环队列中，队列的头尾指针可以通过模运算实现循环移动。

循环队列结构体定义

/** 循环队列容量，默认值 8；可在编译期通过 -DCQ_CAPACITY=NN 覆盖 */
#ifndef CQ_CAPACITY
#define CQ_CAPACITY 8
#endif

/** 队列元素类型（可按需修改） */
typedef int ElemType;

/**
 * @brief 循环队列结构体
 *
 * @var data_base 指向长度为 CQ_CAPACITY 的连续存储区
 * @var front     队首索引，指向当前可读元素的位置（若队空，front 的值无实际数据）
 * @var rear      队尾索引，指向下一个可写入的位置（即队尾元素的后继位置）
 * @var size      当前元素个数（范围 0 .. CQ_CAPACITY）
 */
typedef struct {
    ElemType* data_base;  /**< 存储数组首地址（长度恒为 CQ_CAPACITY） */
    size_t front;         /**< 队首指针：指向当前可读元素的位置 */
    size_t rear;          /**< 队尾指针：指向下一个可写入的位置（队尾的下一个位置） */
    size_t size;          /**< 当前元素个数（0..CQ_CAPACITY） */
} CircularQueue;

ElemType* data_base：数据项，这里使用一个指针存储数组的首地址，后续我们仍然可以像操作数组一样使用下标访问，我们也可以直接将其设置为固定长度的数组如：ElemType data[CQ_CAPACITY]

front: 队首指针：指向队列的第一个元素

rear：队尾指针：指向队列最后一个元素的下一位置，也叫做下一个入队元素位置

size: 当前元素个数

API设计

// 初始化/销毁
bool cq_init(CircularQueue* q);
void cq_free(CircularQueue* q);

// 判空/判满/当前大小/容量
bool cq_is_empty(const CircularQueue* q);
bool cq_is_full(const CircularQueue* q);
size_t cq_size(const CircularQueue* q);
size_t cq_capacity(const CircularQueue* q);

// 入队/出队/取队首
bool cq_enqueue(CircularQueue* q, ElemType value);
bool cq_dequeue(CircularQueue* q, ElemType* out_value);
bool cq_front(const CircularQueue* q, ElemType* out_value);

// 清空（不释放容量）
void cq_clear(CircularQueue* q);

循环队列源码实现

github仓库：https://github.com/keqiudi/Queue/tree/master/circular_queue

circular_queue.h

#ifndef CIRCULAR_QUEUE_H
#define CIRCULAR_QUEUE_H

#include <stddef.h>
#include <stdbool.h>

#ifdef __cplusplus
extern "C" {
#endif

/** 循环队列容量，默认值 8；可在编译期通过 -DCQ_CAPACITY=NN 覆盖 */
#ifndef CQ_CAPACITY
#define CQ_CAPACITY 8
#endif

/** 队列元素类型（可按需修改） */
typedef int ElemType;

/**
 * @brief 循环队列结构体
 *
 * @var data_base 指向长度为 CQ_CAPACITY 的连续存储区
 * @var front     队首索引，指向当前可读元素的位置（若队空，front 的值无实际数据）
 * @var rear      队尾索引，指向下一个可写入的位置（即队尾元素的后继位置）
 * @var size      当前元素个数（范围 0 .. CQ_CAPACITY）
 */
typedef struct {
    ElemType* data_base;  /**< 存储数组首地址（长度恒为 CQ_CAPACITY） */
    size_t front;         /**< 队首指针：指向当前可读元素的位置 */
    size_t rear;          /**< 队尾指针：指向下一个可写入的位置（队尾的下一个位置） */
    size_t size;          /**< 当前元素个数（0..CQ_CAPACITY） */
} CircularQueue;

/**
 * @brief 初始化循环队列并分配底层存储
 *
 * 在成功返回时，队列处于空状态（front==rear==0, size==0）。
 *
 * @param q 指向待初始化的 CircularQueue（不得为 NULL）
 * @return true  初始化成功
 * @return false 参数为 NULL 或 内存分配失败
 * @note 成功后请使用 cq_free 释放内部分配的 data_base；若 CircularQueue 对象本身是动态分配的，
 *       调用方还需在 cq_free 之后 free 该对象。
 */
bool cq_init(CircularQueue* q);

/**
 * @brief 释放队列内部分配的存储并复位队列字段
 *
 * @param q 指向 CircularQueue（可为 NULL；为 NULL 时函数无操作）
 * @note 调用后 q->data_base 设为 NULL，front/rear/size 置为 0。
 */
void cq_free(CircularQueue* q);

/**
 * @brief 判断队列是否为空
 *
 * @param q 指向 CircularQueue（可为 NULL，NULL 将被视作空队列）
 * @return true  队列为空（或 q == NULL）
 * @return false 队列非空
 */
bool cq_is_empty(const CircularQueue* q);

/**
 * @brief 判断队列是否已满
 *
 * @param q 指向 CircularQueue（若 q == NULL 返回 false）
 * @return true  队列已满（size == CQ_CAPACITY）
 * @return false 未满
 */
bool cq_is_full(const CircularQueue* q);

/**
 * @brief 返回当前元素个数
 *
 * @param q 指向 CircularQueue（若 q == NULL 返回 0）
 * @return 当前队列元素个数
 */
size_t cq_size(const CircularQueue* q);

/**
 * @brief 返回队列容量（固定值 CQ_CAPACITY）
 *
 * @param q 可为 NULL（未使用）
 * @return 队列最大可存放元素个数（CQ_CAPACITY）
 */
size_t cq_capacity(const CircularQueue* q);

/**
 * @brief 入队：向队尾插入一个元素
 *
 * 在 rear 指向的位置写入元素，然后将 rear 前移（循环回绕），同时 size++。
 *
 * @param q     指向 CircularQueue（不得为 NULL）
 * @param value 要入队的元素
 * @return true  入队成功
 * @return false q 为 NULL 或 队列已满
 */
bool cq_enqueue(CircularQueue* q, ElemType value);

/**
 * @brief 出队：移除并返回队首元素
 *
 * 从 front 指向的位置读取元素写入 *out_value，然后将 front 前移（循环回绕），同时 size--。
 *
 * @param q         指向 CircularQueue（不得为 NULL）
 * @param out_value 指向接收出队元素的缓冲（不得为 NULL）
 * @return true  出队成功（并写回 *out_value）
 * @return false q 为 NULL、队列为空或 out_value 为 NULL
 */
bool cq_dequeue(CircularQueue* q, ElemType* out_value);

/**
 * @brief 获取队首元素但不出队（peek）
 *
 * 将队首元素值写入 *out_value，但不修改队列状态。
 *
 * @param q         指向 CircularQueue（不得为 NULL）
 * @param out_value 指向接收队首元素的缓冲（不得为 NULL）
 * @return true  读取成功（并写回 *out_value）
 * @return false q 为 NULL、队列为空或 out_value 为 NULL
 */
bool cq_front(const CircularQueue* q, ElemType* out_value);

/**
 * @brief 清空队列（复位 front/rear/size），但不释放底层存储
 *
 * @param q 指向 CircularQueue（可为 NULL；为 NULL 时无操作）
 * @note 调用后队列等同于新初始化但保留已分配的 data_base。
 */
void cq_clear(CircularQueue* q);

#ifdef __cplusplus
}
#endif

#endif // CIRCULAR_QUEUE_H

circular_queue.c

//
// Created by keqiu on 25-11-2.
//

#include "circular_queue.h"
#include "stdlib.h"


// 初始化/销毁
bool cq_init(CircularQueue* q)
{
    if (q == NULL)
    {
        return false;
    }

    q->data_base = (ElemType*) malloc(sizeof(ElemType)* CQ_CAPACITY); // 分配指定大小的内存
    if (q->data_base == NULL)
    {
        return false;
    }

    q->front = 0;
    q->rear = 0;
    q->size = 0;
    return true;
}

void cq_free(CircularQueue* q)
{
    if (q == NULL)
    {
        return;
    }

    free(q->data_base); // 释放分配的内存
    q->data_base = NULL;
    q->front = 0;
    q->rear = 0;
    q->size = 0;
}

// 判空/判满/当前大小/容量
bool cq_is_empty(const CircularQueue* q)
{
    if (q == NULL)
    {
        return false;
    }

    return q->size == 0;
}

bool cq_is_full(const CircularQueue* q)
{
    if (q == NULL)
    {
        return false;
    }

    return q->size == CQ_CAPACITY;
}

size_t cq_size(const CircularQueue* q)
{
    if (q == NULL)
    {
        return 0;
    }

    return q->size;
}

size_t cq_capacity(const CircularQueue* q)
{
    return CQ_CAPACITY;
}

// 入队/出队/取队首
bool cq_enqueue(CircularQueue* q, ElemType value)
{
    if (q == NULL || cq_is_full(q))
    {
        return false;
    }

    q->data_base[q->rear] = value;
    q->rear = (q->rear + 1) % CQ_CAPACITY; // 移动队尾指针到下一个写入位置，使用模运算形成循环
    q->size++;

    return true;
}

bool cq_dequeue(CircularQueue* q, ElemType* out_value)
{
    if (q == NULL || cq_is_empty(q) || out_value == NULL)
    {
        return false;
    }

    *out_value = q->data_base[q->front]; // 元素出队
    q->front = (q->front + 1) % CQ_CAPACITY; // 移动队首指针到下一个读取位置，使用模运算形成循环
    q->size--;

    return true;
}

bool cq_front(const CircularQueue* q, ElemType* out_value)
{
    if (q == NULL || cq_is_empty(q) || out_value == NULL)
    {
        return false;
    }

    *out_value = q->data_base[q->front]; // 元素出队

    return true;
}

// 清空（不释放容量）
void cq_clear(CircularQueue* q)
{
    if (q == NULL)
    {
        return;
    }

    q->front = 0;
    q->rear = 0;
    q->size = 0;
}

测试代码

#include <stdio.h>
#include <assert.h>
#include "circular_queue.h"

// 辅助打印当前队列所有元素
void print_circular_queue(const CircularQueue* q)
{
    if (!q || cq_is_empty(q))
    {
        printf("队列为空\n");
        return;
    }
    printf("队列元素: [");
    for (size_t i = 0; i < cq_size(q); ++i)
    {
        size_t idx = (q->front + i) % CQ_CAPACITY;
        printf("%d", q->data_base[idx]);
        if (i + 1 < cq_size(q)) printf(", ");
    }
    printf("]\n");
}

int main(void)
{
    CircularQueue q;

    // 初始化
    assert(cq_init(&q));
    printf("初始化成功，容量=%zu\n", cq_capacity(&q));
    assert(cq_is_empty(&q));
    assert(!cq_is_full(&q));
    assert(cq_size(&q) == 0);
    print_circular_queue(&q);

    // 入队直到满
    printf("依次入队1~%zu：\n", cq_capacity(&q));
    for (int i = 1; i <= (int)cq_capacity(&q); ++i) {
        assert(cq_enqueue(&q, i));
        printf("入队: %d, ", i);
        print_circular_queue(&q);
    }
    assert(!cq_enqueue(&q, 999)); // 队满应失败
    assert(cq_is_full(&q));
    assert(!cq_is_empty(&q));
    assert(cq_size(&q) == cq_capacity(&q));

    // 查看队首
    int front_val = 0;
    assert(cq_front(&q, &front_val));
    printf("队首元素: %d\n", front_val);
    print_circular_queue(&q);

    // 出队2个元素
    printf("出队2个元素：\n");
    int val = 0;
    for (int i = 0; i < 2; ++i) {
        assert(cq_dequeue(&q, &val));
        printf("出队: %d, ", val);
        print_circular_queue(&q);
        assert(val == i + 1);
    }
    assert(!cq_is_full(&q));
    assert(!cq_is_empty(&q));
    assert(cq_size(&q) == cq_capacity(&q) - 2);

    // 再入队2个新元素，测试环绕
    printf("再次入队100, 200，测试环绕：\n");
    assert(cq_enqueue(&q, 100));
    printf("入队: 100, ");
    print_circular_queue(&q);
    assert(cq_enqueue(&q, 200));
    printf("入队: 200, ");
    print_circular_queue(&q);
    assert(cq_is_full(&q));

    // 依次全部出队，检查顺序
    printf("全部出队，检查顺序：\n");
    int expect[] = {3,4,5,6,7,8,100,200};
    size_t idx = 0;
    while (!cq_is_empty(&q)) {
        assert(cq_dequeue(&q, &val));
        printf("出队: %d, ", val);
        print_circular_queue(&q);
        assert(val == expect[idx++]);
    }
    assert(cq_is_empty(&q));
    assert(idx == cq_capacity(&q));

    // 清空与再次入队
    printf("测试清空与再次入队：\n");
    for (int i = 1; i <= 3; ++i) {
        assert(cq_enqueue(&q, i * 10));
        printf("入队: %d, ", i * 10);
        print_circular_queue(&q);
    }
    cq_clear(&q);
    assert(cq_is_empty(&q));
    assert(cq_size(&q) == 0);
    print_circular_queue(&q);

    // 释放队列
    cq_free(&q);
    printf("循环队列测试通过！\n");

    return 0;
}

输出结果：

C:\Users\keqiu\myProjects\CLionProjects\C\Queue\circular_queue\build\circular_queue.exe
初始化成功，容量=8
队列为空
依次入队1~8：
入队: 1, 队列元素: [1]
入队: 2, 队列元素: [1, 2]
入队: 3, 队列元素: [1, 2, 3]
入队: 4, 队列元素: [1, 2, 3, 4]
入队: 5, 队列元素: [1, 2, 3, 4, 5]
入队: 6, 队列元素: [1, 2, 3, 4, 5, 6]
入队: 7, 队列元素: [1, 2, 3, 4, 5, 6, 7]
入队: 8, 队列元素: [1, 2, 3, 4, 5, 6, 7, 8]
队首元素: 1
队列元素: [1, 2, 3, 4, 5, 6, 7, 8]
出队2个元素：
出队: 1, 队列元素: [2, 3, 4, 5, 6, 7, 8]
出队: 2, 队列元素: [3, 4, 5, 6, 7, 8]
再次入队100, 200，测试环绕：
入队: 100, 队列元素: [3, 4, 5, 6, 7, 8, 100]
入队: 200, 队列元素: [3, 4, 5, 6, 7, 8, 100, 200]
全部出队，检查顺序：
出队: 3, 队列元素: [4, 5, 6, 7, 8, 100, 200]
出队: 4, 队列元素: [5, 6, 7, 8, 100, 200]
出队: 5, 队列元素: [6, 7, 8, 100, 200]
出队: 6, 队列元素: [7, 8, 100, 200]
出队: 7, 队列元素: [8, 100, 200]
出队: 8, 队列元素: [100, 200]
出队: 100, 队列元素: [200]
出队: 200, 队列为空
测试清空与再次入队：
入队: 10, 队列元素: [10]
入队: 20, 队列元素: [10, 20]
入队: 30, 队列元素: [10, 20, 30]
队列为空
循环队列测试通过！

进程已结束，退出代码为 0

链式队列(链式存储队列)

链式队列：是一种用链表实现的队列结构，每个元素封装为一个节点（包含数据域和指针域），队列通过两个指针维护首尾：front指向队头（下一个将被出队的节点），rear指向队尾（新节点在此后追加）。链式队列不依赖连续内存，也没有固定容量，因此不会出现顺序队列的假溢出问题，适合元素数量不可预知或需要动态扩展的场景。

链式队列结构体定义

/** 队列中元素的数据类型（可根据需要调整） */
typedef int ElemType;

/**
 * @brief 链表节点
 *
 * 每个节点包含数据域和指向下一个节点的指针。
 */
typedef struct LQNode {
    ElemType data;        /**< 节点存放的数据 */
    struct LQNode* next;  /**< 指向下一个节点，若为 NULL 表示链表尾 */
} LQNode;

/**
 * @brief 链式队列结构体
 *
 * 字段说明：
 *  - front: 指向队头节点（下一个将被出队的节点），为空时为 NULL。
 *  - rear:  指向队尾节点（最近入队的节点），为空时为 NULL。
 *  - size:  当前元素个数（size_t）。
 */
typedef struct LinkedQueue {
    LQNode* front; /**< 队头指针（出队方向） */
    LQNode* rear;  /**< 队尾指针（入队方向） */
    size_t size;   /**< 当前元素个数 */
} LinkedQueue;

API设计

// 初始化/销毁
void lq_init(LinkedQueue* q);
void lq_destroy(LinkedQueue* q);

// 入队/出队/取队首
bool lq_enqueue(LinkedQueue* q, ElemType data);
bool lq_dequeue(LinkedQueue* q, ElemType* out);
bool lq_front(const LinkedQueue* q, ElemType* out);

// 判空//容量
int lq_size(const LinkedQueue* q);
bool lq_is_empty(const LinkedQueue* q);

链式队列因为基于链表实现，所以没有判空和容量相关的api

链式队列源码实现

github仓库：https://github.com/keqiudi/Queue/tree/master/linked_queue

linked_queue.h

//
// Created by keqiu on 25-11-8.
//

#ifndef LINKED_QUEUE_H
#define LINKED_QUEUE_H

#include <stddef.h>
#include <stdbool.h>

#ifdef __cplusplus
extern "C" {
#endif

/** 队列中元素的数据类型（可根据需要调整） */
typedef int ElemType;

/**
 * @brief 链表节点
 *
 * 每个节点包含数据域和指向下一个节点的指针。
 */
typedef struct LQNode {
    ElemType data;        /**< 节点存放的数据 */
    struct LQNode* next;  /**< 指向下一个节点，若为 NULL 表示链表尾 */
} LQNode;

/**
 * @brief 链式队列结构体
 *
 * 字段说明：
 *  - front: 指向队头节点（下一个将被出队的节点），为空时为 NULL。
 *  - rear:  指向队尾节点（最近入队的节点），为空时为 NULL。
 *  - size:  当前元素个数（size_t）。
 */
typedef struct LinkedQueue {
    LQNode* front; /**< 队头指针（出队方向） */
    LQNode* rear;  /**< 队尾指针（入队方向） */
    size_t size;   /**< 当前元素个数 */
} LinkedQueue;

/**
 * @brief 初始化链式队列
 *
 * 将队列置为空：front = rear = NULL，size = 0。
 *
 * @param q 指向要初始化的 LinkedQueue 对象（不得为 NULL）
 */
void lq_init(LinkedQueue* q);

/**
 * @brief 销毁队列并释放所有节点内存
 *
 * 遍历并 free 队列中所有节点，然后将 front/rear 置为 NULL，size 置为 0。
 * 注意：该函数不会 free LinkedQueue 对象本身（如果 LinkedQueue 是通过 malloc 分配的，调用者负责释放）。
 *
 * @param q 指向要销毁的 LinkedQueue（若为 NULL，函数直接返回）
 */
void lq_destroy(LinkedQueue* q);

/**
 * @brief 在队尾追加元素（入队）
 *
 * 创建新节点并追加至队尾。若内存分配失败或 q 为 NULL 则返回 false。
 *
 * @param q 指向 LinkedQueue（不得为 NULL）
 * @param data 要入队的数据
 * @return true 成功入队；false 失败（如内存分配失败或 q 为 NULL）
 */
bool lq_enqueue(LinkedQueue* q, ElemType data);

/**
 * @brief 从队头移除元素（出队）
 *
 * 将队头节点移除并释放它的内存；若 out 非 NULL，会把出队元素写入 *out。
 * 若队列为空或 q 为 NULL，返回 false。
 *
 * @param q 指向 LinkedQueue
 * @param out 用于接收出队元素的缓冲（可为 NULL，表示忽略返回值）
 * @return true 成功出队；false 失败（如空队列或 q 为 NULL）
 */
bool lq_dequeue(LinkedQueue* q, ElemType* out);

/**
 * @brief 读取队首元素但不移除（peek）
 *
 * 将队头元素写入 *out（out 不能为空）。若队列为空或 q 为 NULL，返回 false。
 *
 * @param q 指向常量 LinkedQueue
 * @param out 接收队首元素的缓冲（不得为 NULL）
 * @return true 成功读取；false 失败（如队空或参数非法）
 */
bool lq_front(const LinkedQueue* q, ElemType* out);

/**
 * @brief 判断队列是否为空
 *
 * 若 q 为 NULL，函数返回 true（将 NULL 视为“空队列”）。
 *
 * @param q 指向常量 LinkedQueue
 * @return true 队列为空（或 q == NULL）；false 队列非空
 */
bool lq_is_empty(const LinkedQueue* q);

/**
 * @brief 获取队列当前元素个数
 *
 * 注意：返回类型为 int 并在 q == NULL 时返回 -1（保持与已有签名一致）。
 * 建议：如需更严格类型，可将返回类型改为 size_t 并在 q == NULL 时返回 0。
 *
 * @param q 指向常量 LinkedQueue
 * @return 元素个数（int）；若 q == NULL 则返回 -1
 */
int lq_size(const LinkedQueue* q);

#ifdef __cplusplus
}
#endif

#endif //LINKED_QUEUE_H

linked_queue.c

#include "linked_queue.h"
#include <stdlib.h>

void lq_init(LinkedQueue* q)
{
    if (q == NULL) {
        return;
    }

    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}

void lq_destroy(LinkedQueue* q)
{
    if (q == NULL) {
        return;
    }

    LQNode* current = q->front;
    while (current != NULL) {
        LQNode* next = current->next;
        free(current);
        current = next;
    }

    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}

bool lq_enqueue(LinkedQueue* q, ElemType data)
{
    if (q == NULL) {
        return false;
    }

    LQNode* node = (LQNode*)malloc(sizeof(LQNode));
    if (node == NULL) {
        return false;
    }

    node->data = data;
    node->next = NULL;

    if (q->rear != NULL) {
        /* 队列非空：将新节点接到尾部 */
        q->rear->next = node;
    } else {
        /* 队列为空：新节点为 front */
        q->front = node;
    }

    q->rear = node;
    q->size++;

    return true;
}

bool lq_dequeue(LinkedQueue* q, ElemType* out)
{
    if (q == NULL || q->front == NULL) {
        return false;
    }

    LQNode* node = q->front;

    if (out != NULL) {
        *out = node->data;
    }

    q->front = node->next;
    if (q->front == NULL) {
        /* 出队后队列为空，需要把 rear 也置为 NULL */
        q->rear = NULL;
    }

    free(node);
    q->size--;

    return true;
}

bool lq_front(const LinkedQueue* q, ElemType* out)
{
    if (q == NULL || q->front == NULL || out == NULL) {
        return false;
    }

    *out = q->front->data;
    return true;
}

bool lq_is_empty(const LinkedQueue* q)
{
    if (q == NULL) {
        return true;
    }
    return q->size == 0;
}

int lq_size(const LinkedQueue* q)
{
    if (q == NULL) {
        return -1;
    }
    return (int)q->size;
}

测试代码

#include <stdio.h>
#include <assert.h>
#include "linked_queue.h"

/* 辅助：打印队列当前所有元素（从 front 到 rear） */
void print_linked_queue(const LinkedQueue* q) {

    if (q == NULL || lq_is_empty(q))
    {
        printf("队列: [empty]\n");
        return;
    }
    printf("队列: [");
    LQNode* p = q->front;
    while (p)
    {
        printf("%d", p->data);
        if (p->next)
        {
            printf(", ");
        }
        p = p->next;
    }
    printf("] (size=%d)\n", lq_size(q));
}

int main(void) {
    LinkedQueue q;
    lq_init(&q);

    printf("初始化队列\n");
    assert(lq_is_empty(&q));
    assert(lq_size(&q) == 0);
    print_linked_queue(&q);

    /* 依次入队 1..10（数据为 10,20,...,100）并打印 */
    printf("\n逐个入队并打印状态：\n");
    for (int i = 1; i <= 10; ++i)
    {
        int val = i * 10;
        bool ok = lq_enqueue(&q, val);
        assert(ok);
        printf("enqueue %d -> ", val);
        print_linked_queue(&q);
        assert(lq_size(&q) == i);
    }

    /* 读取队首但不出队 */
    int front_val = 0;
    assert(lq_front(&q, &front_val));
    printf("\n当前队首 (front): %d\n", front_val);
    print_linked_queue(&q);
    assert(front_val == 10);

    /* 出队 5 个元素，检查返回值与顺序 */
    printf("\n出队 5 个元素：\n");
    for (int i = 1; i <= 5; ++i)
    {
        int out = -1;
        bool ok = lq_dequeue(&q, &out);
        assert(ok);
        printf("dequeue -> %d, ", out);
        print_linked_queue(&q);
        assert(out == i * 10);
    }
    assert(lq_size(&q) == 5);

    /* 将剩余元素全部出队并检查顺序 */
    printf("\n清空队列并检查顺序：\n");
    int expect[] = {60, 70, 80, 90, 100};
    for (int i = 0; i < 5; ++i)
    {
        int out = -1;
        bool ok = lq_dequeue(&q, &out);
        assert(ok);
        printf("dequeue -> %d, ", out);
        print_linked_queue(&q);
        assert(out == expect[i]);
    }
    assert(lq_is_empty(&q));
    assert(lq_size(&q) == 0);

    /* 空队列出队应失败 */
    int tmp;
    assert(!lq_dequeue(&q, &tmp));
    assert(!lq_front(&q, &tmp));

    /* 再次入队若干元素，测试 destroy */
    printf("\n再次入队 3 个元素，用于测试 destroy：\n");
    for (int i = 1; i <= 3; ++i)
    {
        assert(lq_enqueue(&q, i));
    }
    print_linked_queue(&q);

    /* 销毁队列（释放所有节点） */
    lq_destroy(&q);
    printf("已调用 lq_destroy\n");
    /* 结构已被重置，确认为空 */
    assert(lq_is_empty(&q));
    assert(lq_size(&q) == 0);
    print_linked_queue(&q);

    printf("\n链式队列所有测试通过!\n");
    return 0;
}

输出结果：

C:\Users\keqiu\myProjects\CLionProjects\C\Queue\linked_queue\build\linked_queue.exe
初始化队列
队列: [empty]

逐个入队并打印状态：
enqueue 10 -> 队列: [10] (size=1)
enqueue 20 -> 队列: [10, 20] (size=2)
enqueue 30 -> 队列: [10, 20, 30] (size=3)
enqueue 40 -> 队列: [10, 20, 30, 40] (size=4)
enqueue 50 -> 队列: [10, 20, 30, 40, 50] (size=5)
enqueue 60 -> 队列: [10, 20, 30, 40, 50, 60] (size=6)
enqueue 70 -> 队列: [10, 20, 30, 40, 50, 60, 70] (size=7)
enqueue 80 -> 队列: [10, 20, 30, 40, 50, 60, 70, 80] (size=8)
enqueue 90 -> 队列: [10, 20, 30, 40, 50, 60, 70, 80, 90] (size=9)
enqueue 100 -> 队列: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] (size=10)

当前队首 (front): 10
队列: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] (size=10)

出队 5 个元素：
dequeue -> 10, 队列: [20, 30, 40, 50, 60, 70, 80, 90, 100] (size=9)
dequeue -> 20, 队列: [30, 40, 50, 60, 70, 80, 90, 100] (size=8)
dequeue -> 30, 队列: [40, 50, 60, 70, 80, 90, 100] (size=7)
dequeue -> 40, 队列: [50, 60, 70, 80, 90, 100] (size=6)
dequeue -> 50, 队列: [60, 70, 80, 90, 100] (size=5)

清空队列并检查顺序：
dequeue -> 60, 队列: [70, 80, 90, 100] (size=4)
dequeue -> 70, 队列: [80, 90, 100] (size=3)
dequeue -> 80, 队列: [90, 100] (size=2)
dequeue -> 90, 队列: [100] (size=1)
dequeue -> 100, 队列: [empty]

再次入队 3 个元素，用于测试 destroy：
队列: [1, 2, 3] (size=3)
已调用 lq_destroy
队列: [empty]

链式队列所有测试通过!

进程已结束，退出代码为 0