DA2-链式队列

C语言链式队列实现

1. 链式队列结构定义

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 队列节点结构定义
typedef struct QueueNode {
    int data;                    // 节点数据
    struct QueueNode* next;      // 指向下一个节点的指针
} QueueNode;

// 链式队列结构定义
typedef struct {
    QueueNode* front;    // 队头指针
    QueueNode* rear;     // 队尾指针
    int size;            // 队列中元素个数
} LinkQueue;

2. 核心函数实现

/**
 * 创建新节点
 * @param element 节点数据
 * @return 指向新节点的指针
 * 时间复杂度: O(1)
 * 空间复杂度: O(1)
 */
QueueNode* createNode(int element) {
    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    if (node == NULL) {
        return NULL;  // 内存分配失败
    }
    node->data = element;
    node->next = NULL;
    return node;
}

/**
 * 初始化链式队列
 * @return 指向初始化队列的指针
 * 时间复杂度: O(1)
 * 空间复杂度: O(1)
 */
LinkQueue* initQueue() {
    LinkQueue* queue = (LinkQueue*)malloc(sizeof(LinkQueue));
    if (queue == NULL) {
        return NULL;  // 内存分配失败
    }
    queue->front = NULL;  // 初始化队头指针为空
    queue->rear = NULL;   // 初始化队尾指针为空
    queue->size = 0;      // 初始化队列大小为0
    return queue;
}

/**
 * 判断队列是否为空
 * @param queue 队列指针
 * @return true表示空队列，false表示非空队列
 * 时间复杂度: O(1)
 * 空间复杂度: O(1)
 */
bool isEmpty(LinkQueue* queue) {
    return queue->front == NULL;  // 队头指针为空表示空队列
}

/**
 * 入队操作（在队尾添加元素）
 * @param queue 队列指针
 * @param element 要入队的元素
 * @return true表示成功，false表示失败
 * 时间复杂度: O(1)
 * 空间复杂度: O(1)
 */
bool enqueue(LinkQueue* queue, int element) {
    // 创建新节点
    QueueNode* newNode = createNode(element);
    if (newNode == NULL) {
        printf("内存分配失败，无法入队\n");
        return false;
    }

    // 如果队列为空，新节点既是队头也是队尾
    if (isEmpty(queue)) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        // 将新节点链接到队尾，并更新队尾指针
        queue->rear->next = newNode;
        queue->rear = newNode;
    }

    queue->size++;  // 队列大小加1
    return true;
}

/**
 * 出队操作（从队头删除元素）
 * @param queue 队列指针
 * @param element 用于接收出队元素的指针
 * @return true表示成功，false表示失败
 * 时间复杂度: O(1)
 * 空间复杂度: O(1)
 */
bool dequeue(LinkQueue* queue, int* element) {
    // 检查队列是否为空
    if (isEmpty(queue)) {
        printf("队列为空，无法出队\n");
        return false;
    }

    // 保存队头节点
    QueueNode* temp = queue->front;

    // 获取队头元素值
    *element = temp->data;

    // 更新队头指针
    queue->front = temp->next;

    // 如果队列变为空，需要同时更新队尾指针
    if (queue->front == NULL) {
        queue->rear = NULL;
    }

    // 释放原队头节点内存
    free(temp);
    queue->size--;  // 队列大小减1

    return true;
}

/**
 * 获取队头元素（不删除）
 * @param queue 队列指针
 * @param element 用于接收队头元素的指针
 * @return true表示成功，false表示失败
 * 时间复杂度: O(1)
 * 空间复杂度: O(1)
 */
bool getFront(LinkQueue* queue, int* element) {
    // 检查队列是否为空
    if (isEmpty(queue)) {
        printf("队列为空，无法获取队头元素\n");
        return false;
    }

    // 直接返回队头元素值
    *element = queue->front->data;
    return true;
}

/**
 * 获取队尾元素（不删除）
 * @param queue 队列指针
 * @param element 用于接收队尾元素的指针
 * @return true表示成功，false表示失败
 * 时间复杂度: O(1)
 * 空间复杂度: O(1)
 */
bool getRear(LinkQueue* queue, int* element) {
    // 检查队列是否为空
    if (isEmpty(queue)) {
        printf("队列为空，无法获取队尾元素\n");
        return false;
    }

    // 直接返回队尾元素值
    *element = queue->rear->data;
    return true;
}

/**
 * 获取队列中元素个数
 * @param queue 队列指针
 * @return 队列中元素个数
 * 时间复杂度: O(1)
 * 空间复杂度: O(1)
 */
int getSize(LinkQueue* queue) {
    return queue->size;
}

/**
 * 销毁链式队列
 * @param queue 队列指针
 * 时间复杂度: O(n)，其中n为队列中元素个数
 * 空间复杂度: O(1)
 */
void destroyQueue(LinkQueue* queue) {
    if (queue != NULL) {
        // 逐个释放队列中所有节点
        QueueNode* current = queue->front;
        while (current != NULL) {
            QueueNode* temp = current;
            current = current->next;
            free(temp);
        }
        // 释放队列结构体内存
        free(queue);
    }
}

/**
 * 打印队列中所有元素（从队头到队尾）
 * @param queue 队列指针
 * 时间复杂度: O(n)
 * 空间复杂度: O(1)
 */
void printQueue(LinkQueue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空\n");
        return;
    }

    printf("队列元素（从队头到队尾）: ");
    QueueNode* current = queue->front;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

3. 核心函数详解

3.1 关键操作说明

1. 入队操作(enqueue)：
2. 在队尾添加新元素
3. 需要维护队尾指针指向最后一个节点

4. 空队列时，新节点既是队头也是队尾

5. 出队操作(dequeue)：

6. 从队头删除元素
7. 需要维护队头指针指向第一个节点

8. 当队列只有一个元素时，出队后队列变空，需同时更新队尾指针

9. 边界条件处理：

10. 空队列入队：队头和队尾都指向新节点
11. 单元素队列出队：队头和队尾都置为NULL

3.2 指针操作要点

graph LR
    A[空队列] --> B[入队元素1]
    B --> C[front=rear=节点1]
    C --> D[入队元素2]
    D --> E[front=节点1, rear=节点2]
    E --> F[出队元素1]
    F --> G[front=节点2, rear=节点2]
    G --> H[出队元素2]
    H --> I[front=rear=NULL]

4. 复杂度分析

4.1 时间复杂度

• 入队(enqueue): O(1) - 直接在队尾添加节点
• 出队(dequeue): O(1) - 直接从队头删除节点
• 获取队头(getFront): O(1) - 直接访问队头节点
• 获取队尾(getRear): O(1) - 直接访问队尾节点
• 判断空(isEmpty): O(1) - 检查队头指针
• 获取大小(getSize): O(1) - 维护size变量

4.2 空间复杂度

• 总体空间: O(n) - n为队列中元素个数
• 每个节点: 需要额外的指针空间存储next指针
• 队列结构体: 固定大小，存储队头、队尾指针和大小计数

5. 链式队列特点

5.1 优势

1. 动态内存分配：按需分配内存，不会浪费空间
2. 无容量限制：理论上可以无限扩展（受限于系统内存）
3. 高效操作：入队和出队操作都是O(1)时间复杂度
4. 内存利用率：不需要预分配固定大小的数组

5.2 劣势

1. 额外内存开销：每个节点需要存储next指针
2. 内存不连续：节点在内存中可能不连续存储
3. 缓存局部性差：相比顺序队列，访问效率可能略低

5.3 适用场景

• 队列大小变化较大或无法预估
• 需要频繁的入队出队操作
• 内存资源相对充足
• 对队列容量没有严格限制要求

6. 与顺序队列对比

特性	链式队列	顺序队列
内存分配	动态分配	静态分配
容量限制	无理论限制	固定容量
空间效率	较低（有指针开销）	较高
操作效率	O(1)	O(1)
实现复杂度	中等	简单
内存连续性	不连续	连续

链式队列通过维护队头和队尾两个指针，实现了高效的队列操作，是实际应用中常用的队列实现方式。