采用一个不带头结点只有一个尾结点指针rear的循环单链表存储队列,设计队列的初始化、进队和出队等算法。
时间: 2024-05-01 20:21:51 浏览: 102
只有尾结点的链表表示的队列算法
好的,我来回答你的问题。
1. 队列的初始化算法:
```c
void InitQueue(LinkQueue &Q)
{
Q = (LinkQueue) malloc(sizeof(QNode)); // 创建头结点
Q->rear = Q->next = Q; // 队尾和队头指向头结点
}
```
2. 进队算法:
```c
void EnQueue(LinkQueue &Q, ElemType x)
{
QueuePtr p = (QueuePtr) malloc(sizeof(QNode)); // 创建新结点
p->data = x; // 将元素 x 赋值给新结点
p->next = Q->rear->next; // 新结点插入到队尾后面
Q->rear->next = p;
Q->rear = p; // 更新队尾指针
}
```
3. 出队算法:
```c
bool DeQueue(LinkQueue &Q, ElemType &x)
{
if (Q->rear == Q) // 队列为空
return false;
QueuePtr p = Q->next; // 取队头结点
x = p->data; // 取出队头元素
Q->next = p->next; // 修改头指针
if (Q->rear == p) // 若队列中只有一个结点
Q->rear = Q; // 修改尾指针
free(p); // 释放结点空间
return true;
}
```
这样,我们就实现了基于循环单链表存储队列的初始化、进队和出队算法。
阅读全文