链式队列

链式队列是用链表实现的队列，需要同时维护队头指针和队尾指针。为了操作方便，通常附设一个头结点。

存储结构

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

typedef struct {
    LinkNode *front;  // 队头指针
    LinkNode *rear;   // 队尾指针
} LinkQueue;

基本操作实现

初始化

void InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));  // 头结点
    Q.front->next = NULL;
}

判空

bool QueueEmpty(LinkQueue Q) {
    return Q.front == Q.rear;
}

入队（尾插法）

bool EnQueue(LinkQueue &Q, int x) {
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;  // 新结点插入到队尾
    Q.rear = s;         // 更新队尾指针
    return true;
}

出队

bool DeQueue(LinkQueue &Q, int &x) {
    if (QueueEmpty(Q)) return false;
    LinkNode *p = Q.front->next;  // p指向队头元素结点
    x = p->data;
    Q.front->next = p->next;      // 头结点指向新的队头
    if (Q.rear == p) {             // 如果删除的是最后一个元素
        Q.rear = Q.front;          // 更新队尾指针指向头结点
    }
    free(p);
    return true;
}

时间复杂度：所有操作均为 $O(1)$。

习题

习题 1

最适合用作链队的链表是（ ）

A. 带队头指针和队尾指针的循环单链表 B. 带队头指针和队尾指针的非循环单链表 C. 只带队头指针的循环单链表 D. 只带队头指针的非循环单链表

习题 2

简述链式队列的出队操作需要注意什么问题？为什么？