基于单链表的队列完整实现

注意 QueueDestroy 中的循环释放逻辑，保存 next 指针后再释放当前结点，这是处理链表内存安全的标准写法。

4. 入队与出队逻辑

入队操作 入队本质是单链表的尾插操作。需要分配新结点，并更新尾指针。若队列为空，新结点同时成为头结点和尾结点。

void QueuePush(Queue* pQueue, QDataType data) {
    assert(pQueue);
    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    if (newNode == NULL) {
        perror("malloc failed\n");
        return;
    }
    newNode->data = data;
    newNode->next = NULL;

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

这里增加了内存分配失败的检查，实际工程中应确保健壮性。当 head 为空时，说明队列初始状态，直接赋值即可；否则将新结点挂到原尾结点之后，并更新 tail。

出队操作 出队即删除头结点。需注意处理仅剩一个结点时的特殊情况，此时删除后头尾指针均需置空。为了代码简洁，可以先保存头结点指针，统一进行指针移动和释放。

void QueuePop(Queue* pQueue) {
    assert(pQueue);
    assert(pQueue->head != NULL); // 确保队列非空

    QNode* cur = pQueue->head;
    if (pQueue->head == pQueue->tail) {
        // 仅剩一个结点
        pQueue->head = pQueue->tail = NULL;
    } else {
        // 多个结点，头指针后移
        pQueue->head = pQueue->head->next;
    }
    free(cur);
    cur = NULL;
    pQueue->size--;
}

这种写法避免了重复的 free 调用，逻辑更紧凑。无论剩余几个结点，最终都要释放原来的头结点，只需根据情况调整 head 指针指向。

5. 辅助功能实现

获取队头队尾数据相对简单，直接访问指针指向的 data 字段即可，但务必先判空。

QDataType QueueFront(Queue* pQueue) {
    assert(pQueue);
    assert(!QueueEmpty(pQueue));
    return pQueue->head->data;
}

QDataType QueueBack(Queue* pQueue) {
    assert(pQueue);
    assert(!QueueEmpty(pQueue));
    return pQueue->tail->data;
}

获取大小和判空利用了之前定义的 size 成员，实现了 O(1) 查询。

int QueueSize(Queue* pQueue) {
    assert(pQueue);
    return pQueue->size;
}

bool QueueEmpty(Queue* pQueue) {
    assert(pQueue);
    return pQueue->size == 0;
}

6. 测试验证

编写测试函数模拟典型场景：连续入队、查看首尾、连续出队、清空检查。

void TestQueue() {
    Queue queue;
    QueueInit(&queue);
    QueuePush(&queue, 1);
    QueuePush(&queue, 2);
    QueuePush(&queue, 3);
    QueuePush(&queue, 4);
    QueuePush(&queue, 6);

    printf("队尾：%d 有效元素个数：%d\n", QueueBack(&queue), QueueSize(&queue));
    printf("队头：%d 有效元素个数：%d\n", QueueFront(&queue), QueueSize(&queue));

    QueuePop(&queue);
    printf("队尾：%d 有效元素个数：%d\n", QueueBack(&queue), QueueSize(&queue));
    printf("队头：%d 有效元素个数：%d\n", QueueFront(&queue), QueueSize(&queue));

    QueuePop(&queue);
    QueuePop(&queue);
    printf("队列有效元素个数：%d\n", QueueSize(&queue));

    while (!QueueEmpty(&queue)) {
        printf("%d ", QueueFront(&queue));
        QueuePop(&queue);
    }
    QueueDestroy(&queue);
}

int main() {
    TestQueue();
    return 0;
}

总结

通过上述步骤，我们完成了基于单链表的队列实现。关键点在于：

1. 双指针维护：head 和 tail 保证了 O(1) 的入队出队效率。
2. 内存管理：init 和 destroy 确保了资源的安全申请与释放。
3. 状态监控：size 字段提供了高效的容量查询能力。

掌握这些细节，不仅能写出健壮的队列代码，也能加深对指针操作和内存管理的理解。