写一个数据结构代码:一个用单链表组成的循环队列,只设一个尾指针rear,不设头指针,请编写如下算法: (1) 向循环队列中插入一个元素为× 的结点; (2)从循环队列中删除一个结点。
时间: 2024-05-04 16:19:51 浏览: 212
假定一个单向循环链表来表示队列(即循环链队),该队列只设一个队尾指针,不设队首指针,试编写下列各种运算的算法
4星 · 用户满意度95%
以下是一个用单链表组成的循环队列的实现,只设一个尾指针rear,不设头指针,并提供插入和删除操作的算法实现。
```
#include <iostream>
using namespace std;
// 定义队列结点结构体
struct QueueNode {
int data;
QueueNode* next;
};
// 定义循环队列类
class CircularQueue {
public:
// 构造函数,初始时队列为空
CircularQueue() : rear(nullptr) {}
// 插入元素x到队列中
void enqueue(int x) {
QueueNode* newNode = new QueueNode();
newNode->data = x;
newNode->next = nullptr;
if (rear == nullptr) {
rear = newNode;
rear->next = rear;
}
else {
newNode->next = rear->next;
rear->next = newNode;
rear = newNode;
}
}
// 删除队头元素并返回其值,若队列为空则返回-1
int dequeue() {
if (rear == nullptr) {
cout << "队列为空" << endl;
return -1;
}
int res;
if (rear == rear->next) { // 队列中只剩一个元素
res = rear->data;
delete rear;
rear = nullptr;
}
else {
QueueNode* front = rear->next;
rear->next = front->next;
res = front->data;
delete front;
}
return res;
}
private:
QueueNode* rear; // 尾指针
};
int main() {
CircularQueue queue;
// 向队列中插入元素
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
// 删除队头元素
cout << queue.dequeue() << endl;
cout << queue.dequeue() << endl;
cout << queue.dequeue() << endl;
cout << queue.dequeue() << endl;
return 0;
}
```
注意,这里的循环队列是用单链表实现的,因此没有头指针。rear指向的是队列中最后一个结点,而不是头结点。同时,在插入和删除元素时要注意判断队列是否为空,否则会出现空指针错误。
阅读全文