链式队列

链式队列 (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语言数据结构：队列