设计一个带头尾指针的循环单链表,头指针rear,尾指针front,模拟队列,给出入队出队代码
时间: 2024-10-09 20:14:25 浏览: 46
头指针、尾指针的设立-数据结构 栈和队列
设计一个带头尾指针的循环单链表作为队列,需要考虑两个关键操作:入队(enqueue)和出队(dequeue)。这里是一个简单的实现思路:
```cpp
// 定义节点结构
struct Node {
int data;
Node* next;
};
// 初始化链表
Node* rear = nullptr; // 尾指针
Node* front = nullptr; // 头指针
// 入队操作 (enqueue)
void enqueue(int value) {
if (rear == nullptr) {
front = rear = new Node();
front->data = value;
front->next = front; // 链表形成环形
} else {
Node* newNode = new Node();
newNode->data = value;
newNode->next = rear->next; // 插入到尾部
rear->next = newNode;
rear = newNode; // 更新尾指针
}
}
// 出队操作 (dequeue)
int dequeue() {
if (front == nullptr) {
return -1; // 空队列,无法出队
}
int removedValue = front->data;
Node* temp = front;
if (front->next == front) { // 队列只有一个元素
front = rear = nullptr;
} else {
front = front->next; // 更新头指针
delete temp; // 释放原头结点
}
return removedValue;
}
```
阅读全文