假设以带头节点的循环链表表示队列,并且只设一个指针指向队尾元素节点(注意: 不设头指针),试编写相应的置空队列、判断队列是否为空、人队和出队等算法。
时间: 2023-04-26 10:05:43 浏览: 156
数据结构算法-习题-答案-带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点注意不设头指针.docx
5星 · 资源好评率100%
置空队列算法:
1. 将队尾指针指向头节点。
2. 将头节点的next指针指向自身。
代码实现:
void clearQueue(Node* rear) {
rear->next = rear;
}
判断队列是否为空算法:
1. 判断队尾指针的next指针是否指向自身。
2. 如果是,则队列为空;否则,队列不为空。
代码实现:
bool isQueueEmpty(Node* rear) {
return rear->next == rear;
}
入队算法:
1. 创建一个新节点,并将数据存入其中。
2. 将新节点的next指针指向队尾节点的next指针。
3. 将队尾节点的next指针指向新节点。
4. 将队尾指针指向新节点。
代码实现:
void enqueue(Node* rear, int data) {
Node* newNode = new Node(data);
newNode->next = rear->next;
rear->next = newNode;
rear = newNode;
}
出队算法:
1. 判断队列是否为空,如果为空则返回。
2. 将队头节点的next指针指向下一个节点。
3. 释放队头节点的内存空间。
代码实现:
void dequeue(Node* rear) {
if (isQueueEmpty(rear)) {
return;
}
Node* head = rear->next->next;
rear->next->next = head->next;
delete head;
}
阅读全文