链式队列

链式队列 (Linked Queue)

基于双向链表（或带尾指针的单向链表）实现的队列。入队/出队均为 O(1)，无容量上限。

---

结构定义

typedef struct QNode {
    int data;
    struct QNode *next;
} QNode;
 
typedef struct {
    QNode *front;  /* 队头 */
    QNode *rear;   /* 队尾 */
    size_t size;
} LQueue;

---

函数签名

函数	复杂度	说明
void lq_init(LQueue *q)	O(1)	初始化空队列
void lq_enqueue(LQueue *q, int val)	O(1)	在 rear 端插入
int lq_dequeue(LQueue *q)	O(1)	在 front 端删除
int lq_front(LQueue *q)	O(1)	查看队头
int lq_empty(LQueue *q)	O(1)	判空
void lq_free(LQueue *q)	O(n)	释放所有节点

---

核心实现

void lq_enqueue(LQueue *q, int val) {
    QNode *node = malloc(sizeof(QNode));
    node->data = val;
    node->next = NULL;
    if (q->rear)
        q->rear->next = node;
    else
        q->front = node;   /* 首个元素 */
    q->rear = node;
    q->size++;
}
 
int lq_dequeue(LQueue *q) {
    if (lq_empty(q)) return -1;
    QNode *tmp = q->front;
    int val = tmp->data;
    q->front = tmp->next;
    if (q->front == NULL)
        q->rear = NULL;    /* 队列变空 */
    free(tmp);
    q->size--;
    return val;
}

---

循环队列 vs 链式队列

特性	循环队列	链式队列
容量限制	有（定长或倍增）	无
内存布局	连续（缓存友好）	分散
每元素开销	0 额外字节	1 个指针 (8B)
动态扩容	需 realloc + 元素移动	无需

---

跨语言参考

• C语言数据结构：队列