链式队列通过链表实现FIFO，含front和rear指针。1. 结构定义包括节点结构体和队列类；2. 入队时更新rear，空队列时front与rear均指向新节点；3. 出队时更新front并释放内存，队空则rear置空；4. 提供判空、取队首等方法；5. 析构函数释放所有节点。核心在于指针操作与边界处理，需注意内存管理。
在C++中，链式队列是通过链表结构实现的队列，具有动态分配内存的特点，避免了顺序队列可能出现的空间浪费或溢出问题。链式队列遵循“先进先出”（FIFO）原则，通常包含一个头指针（front）和一个尾指针（rear），分别指向队列的首节点和尾节点。
链式队列的基本结构
定义一个链式队列需要创建一个链表节点结构体和一个管理队列的类或结构体。
- 每个节点包含数据域和指向下一个节点的指针
- 队列结构维护 front 和 rear 指针
示例代码：
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class LinkedQueue {
private:
Node front;
Node rear;
public:
LinkedQueue() : front(nullptr), rear(nullptr) {}
~LinkedQueue();
void enqueue(int val);
void dequeue();
int getFront();
bool isEmpty();
};
立即学习“C++免费学习笔记（深入）”；
入队操作（enqueue）
将新元素插入到队列尾部，需更新 rear 指针。
- 创建新节点
- 若队列为空，front 和 rear 都指向新节点
- 否则，将原 rear 节点的 next 指向新节点，并更新 rear
实现方式：
void LinkedQueue::enqueue(int val) {
Node* newNode = new Node(val);
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
出队操作（dequeue）
删除并返回队头元素，需更新 front 指针。
- 检查队列是否为空
- 保存头节点数据和指针
- 移动 front 到下一个节点
- 释放原头节点内存
实现方式：
void LinkedQueue::dequeue() {
if (isEmpty()) {
std::cout << "队列为空，无法出队\n";
return;
}
Node* temp = front;
front = front->next;
delete temp;
if (front == nullptr) { // 若队列变空，更新 rear
rear = nullptr;
}
}
其他常用方法
提供判空、获取队首元素等辅助功能。
bool LinkedQueue::isEmpty() {
return front == nullptr;
}
int LinkedQueue::getFront() {
if (isEmpty()) {
throw std::runtime_error("队列为空");
}
return front->data;
}
析构函数用于释放所有节点内存：
LinkedQueue::~LinkedQueue() {
while (!isEmpty()) {
dequeue();
}
}
基本上就这些。链式队列的核心在于指针操作和边界处理，尤其是空队列时 front 和 rear 同时为 nullptr 的情况。只要注意内存管理和指针更新，就能稳定运行。不复杂但容易忽略细节。
