C语言专题：7.Queue（队列）与 Linked List（链表）

        在数据结构中，队列（Queue）和链表（Linked List）是两个常见的线性结构，具有不同的访问和操作特性。掌握它们的实现方式和使用场景，是深入理解 C 语言和算法设计的重要基础。

一、队列（Queue）

1.1 基本概念

​         队列是一种先进先出（FIFO）的线性数据结构。元素从队尾入队（enqueue），从队头出队（dequeue）。

1.2 循环队列的结构定义

#define MAX_SIZE 100
#define ARRAY_SIZE (MAX_SIZE + 1)

typedef struct {
    int data[ARRAY_SIZE];
    int front;
    int rear;
} Queue;

• front：指向队头元素；

• rear：指向下一个要插入的位置。

1.3 初始化与基本操作

void initQueue(Queue *q) {
    q->front = 1;
    q->rear = 0;
}

int isEmpty(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front ;
}

int isFull(Queue *q) {
    return (q->rear + 2) % MAX_SIZE == q->front;
}

1.4 入队操作

int enqueue(Queue *q, int value) {
    if (isFull(q)) return 0;
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return 1;
}

1.5 出队操作

int dequeue(Queue *q, int *value) {
    if (isEmpty(q)) return 0;
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return 1;
}

1.6 循环队列特点

• 利用模运算 (index + 1) % MAX_SIZE 实现循环；

• 实现空间最大化利用；

• 需要特别注意“空”与“满”的判断条件差异。

• 预留一个空位防止混淆空与满；

• 可存储的元素最多是 MAX_SIZE (ARRAY_SIZE-1)个。

1.7 使用示例

Queue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
int val;
dequeue(&q, &val);  // val = 10

二、链表（Linked List）

2.1 基本概念

链表是一种动态线性结构，通过指针连接每个节点，支持高效的插入和删除。

• 单向链表：每个节点只包含下一个节点的指针。

• 双向链表：每个节点包含前驱与后继指针。

2.2 单向链表节点定义

typedef struct Node {
    int data;
    struct Node *next;
} Node;

2.3 基本操作

创建新节点

Node* createNode(int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

插入节点（头插法）

void insertFront(Node **head, int value) {
    Node *newNode = createNode(value);
    newNode->next = *head;
    *head = newNode;
}

插入节点（尾插法）

void insertEnd(Node **head, int value) {
    Node *newNode = createNode(value);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node *cur = *head;
    while (cur->next) cur = cur->next;
    cur->next = newNode;
}

删除节点

void deleteValue(Node **head, int value) {
    Node *cur = *head, *prev = NULL;
    while (cur && cur->data != value) {
        prev = cur;
        cur = cur->next;
    }
    if (!cur) return;
    if (!prev) *head = cur->next;
    else prev->next = cur->next;
    free(cur);
}

2.4 遍历链表

void printList(Node *head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

2.5 使用示例

Node *head = NULL;
insertEnd(&head, 10);
insertEnd(&head, 20);
insertFront(&head, 5);
printList(head);  // 输出: 5 -> 10 -> 20 -> NULL
deleteValue(&head, 10);
printList(head);  // 输出: 5 -> 20 -> NULL

三、双向链表（Doubly Linked List）

3.1 概念

        双向链表的每个节点有两个指针，分别指向前一个节点（prev）和后一个节点（next），支持双向遍历、双端操作。

3.2 节点定义

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

3.3 插入节点（尾插法）

void insertEnd(DNode **head, int val) {
    DNode *newNode = malloc(sizeof(DNode));
    newNode->data = val;
    newNode->next = NULL;
    newNode->prev = NULL;

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    DNode *cur = *head;
    while (cur->next) cur = cur->next;
    cur->next = newNode;
    newNode->prev = cur;
}

3.4 删除节点（按值）

void deleteNode(DNode **head, int val) {
    DNode *cur = *head;
    while (cur && cur->data != val) {
        cur = cur->next;
    }
    if (!cur) return;

    if (cur->prev)
        cur->prev->next = cur->next;
    else
        *head = cur->next;

    if (cur->next)
        cur->next->prev = cur->prev;

    free(cur);
}

3.5 遍历链表（正向 / 反向）

void printForward(DNode *head) {
    while (head) {
        printf("%d <-> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

void printBackward(DNode *tail) {
    while (tail) {
        printf("%d <-> ", tail->data);
        tail = tail->prev;
    }
    printf("NULL\n");
}

3.6 使用场景

四、队列 vs 链表 对比

五、扩展场景与应用技巧

• 队列常用于生产者-消费者模型、宽度优先搜索BFS；

• 链表更适合频繁插入、删除、动态增长的结构；

• 链表可以构建：栈（stack）、队列（queue）、**哈希桶（hash bucket）**等；

• 双向链表可用于实现LRU缓存淘汰算法等。

六、内存与指针注意事项

• 使用链表必须搭配 malloc / free 管理内存；

• 操作链表时注意空指针（NULL）判断；

• 队列在满与空状态容易出错，尤其是循环队列中需特别处理边界条件；

• 用 typedef struct Node Node; 可简化递归类型定义。

七、总结