链式队列：用链表实现的队列

链式队列：用链表实现的队列

上两节我们用数组实现了队列和循环队列。但数组有个天生的限制——需要提前分配固定大小。如果队列长度变化很大怎么办？这时候，链式队列就派上用场了。

一、链式队列的思路

链式队列就是用链表来实现队列：

• 用头指针指向队头（出队的那一端）
• 用尾指针指向队尾（入队的那一端）
• 入队：在链表尾部添加节点
• 出队：删除链表头部节点

这就像火车：车头是front（先出去），车尾是rear（新车厢挂这里）。

二、具体操作

1. 入队（在尾部添加）

新节点 → [data | next]
rear.next = 新节点
rear = 新节点

想象排队：新来的人直接站到队尾，rear指针跟着移动到他。

2. 出队（从头部删除）

item = front.data
front = front.next
return item

队头的人走了，front指针移动到下一个。

特殊情况：如果出队后队列为空（front == rear），需要把rear也设为null，否则rear还指向已删除的节点。