如果用带头结点的循环单链表来实现队列数据结构,并且仅有一个尾指针NodeRear指向队尾节点(无队头指针Nodefront),给出入队、出队算法的代码
时间: 2024-10-18 08:07:52 浏览: 48
当你使用带头结点的循环单链表作为队列的数据结构时,由于只有一个尾指针`NodeRear`指向队尾,操作相对简单。以下是出入队的操作算法:
**入队(enqueue):**
```cpp
void enqueue(int value) {
// 创建新的节点
Node* newNode = new Node(value);
// 如果队列为空(即NodeRear等于头节点)
if (NodeRear == NodeHead) {
// 尾部节点直接连接新节点
NodeRear->next = newNode;
// 新节点成为新的尾部
NodeRear = newNode;
} else {
// 非空队列,新节点链接到当前尾部之后
newNode->next = NodeRear->next;
// 更新尾部指针
NodeRear->next = newNode;
}
}
```
**出队(dequeue):**
```cpp
int dequeue() {
// 检查队列是否为空
if (NodeRear == NodeHead && NodeHead->next == NodeHead) {
// 空队列,返回错误值或抛异常
return -1; // 或者 throw an exception
}
// 获取并删除队首元素
int removedValue = NodeHead->value;
Node* temp = NodeHead;
// 将前一个节点的next指向前一个节点,形成循环
NodeHead->next = NodeHead->next->next;
// 如果是最后一个节点,更新尾部指针
if (NodeHead->next == NodeRear) {
NodeRear = NodeHead;
}
delete temp; // 释放内存
return removedValue;
}
```
阅读全文