假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的队列初始化、入队和出队的C++代码
时间: 2024-02-11 17:03:46 浏览: 68
可以按照以下方式实现带头结点的循环链表队列的初始化、入队和出队操作:
```C++
struct Node{
int data;
Node* next;
Node(int x):data(x), next(nullptr){};
};
class Queue{
private:
Node* rear;
public:
Queue():rear(nullptr){
rear = new Node(0);
rear->next = rear;
}
void enqueue(int x){
Node* newNode = new Node(x);
newNode->next = rear->next;
rear->next = newNode;
rear = newNode;
}
void dequeue(){
if(rear == rear->next){
cout<<"Queue is empty"<<endl;
return;
}
Node* temp = rear->next->next;
delete rear->next;
rear->next = temp;
}
};
```
其中,队列初始化时创建一个头结点,头结点的next指针指向自己,rear指针指向头结点,表示队列为空。入队时先创建一个新结点,将其next指针指向头结点的next,再将头结点的next指针指向新结点,最后将rear指向新结点,表示队尾在新结点处。出队时先判断队列是否为空,若为空则输出提示信息;否则将头结点的next指针指向下一个结点,再将原队头结点删除即可。
阅读全文