假设以不带头节点的循环链表表示队列,并且只设一个指针指向对尾结点,但不设头指针,设计相应的入队和出队的算法 给出代码
时间: 2024-10-21 15:09:29 浏览: 22
这是一个基于单指针的循环链表队列实现,它只有一个指针 `rear` 指向队尾。入队(enqueue)操作会在当前队尾之后插入新元素,而出队(dequeue)操作会从队首删除元素。由于是循环链表,出队前需要先将 `rear` 指针向前移动一位,直到找到新的队首。
```cpp
// 定义一个链表节点
struct Node {
int data;
Node* next;
};
class Queue {
private:
Node* rear; // 只有一个指针,指向队尾
public:
// 构造函数,初始化为空队列
Queue() : rear(nullptr) {}
// 入队(enqueue)操作
void enqueue(int value) {
if (!rear) { // 初始状态,直接添加在队尾
rear = new Node{value, nullptr};
rear->next = rear; // 形成循环
} else {
Node* newNode = new Node{value, rear}; // 创建新节点
rear->next = newNode; // 更新队尾指针
rear = newNode; // 新节点成为新的队尾
}
}
// 出队(dequeue)操作
int dequeue() {
if (rear == nullptr || rear->next == rear) { // 空队列或只有一个元素
return -1; // 返回错误码或特殊值表示队列空
} else {
Node* front = rear->next; // 获取新的队首
int value = front->data; // 保存值
delete front; // 删除队首节点
rear = rear->next; // 队尾指针向前移一位
if (rear == nullptr) { // 判断是否形成新的循环
rear = front; // 如果是最后一个元素,形成循环
}
return value; // 返回被删除的值
}
}
};
```
阅读全文