假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的存储结构、初始化队列、入队列和出队列算法
时间: 2024-04-30 14:03:44 浏览: 55
数据结构算法习题答案带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针).docx
5星 · 资源好评率100%
存储结构:
```
struct Queue{
Node* rear; //指向队尾结点的指针
};
```
初始化队列:
```
void InitQueue(Queue* q){
q->rear = NULL;
}
```
入队列:
```
void Enqueue(Queue* q, ElemType x){
Node* s = (Node*)malloc(sizeof(Node)); //创建新结点
s->data = x;
if(q->rear == NULL){ //队列为空
s->next = s; //创建环
q->rear = s; //紧接着成为队尾
}
else{
s->next = q->rear->next; //新结点插入队尾
q->rear->next = s; //队尾后移
q->rear = s;
}
}
```
出队列:
```
bool Dequeue(Queue* q, ElemType* x){
if(q->rear == NULL){ //队列为空
return false;
}
else if(q->rear->next == q->rear){ //队列只有一个结点
*x = q->rear->data;
free(q->rear);
q->rear = NULL;
return true;
}
else{ //队列有多个结点
Node* p = q->rear->next; //找到队头
*x = p->data;
q->rear->next = p->next; //删除队头结点
free(p);
return true;
}
}
```
阅读全文