假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的队列初始化、入队列和出队列的算法。
时间: 2023-06-02 10:06:17 浏览: 71
好的,这是一个计算机科学的问题,可以回答。下面是算法实现:
队列初始化:
```
void InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = new QNode; // 创建头结点并将队头、队尾指针指向头结点
Q.front->next = Q.front; // 头结点的next指针指向它本身,表示空队列
}
```
入队列:
```
void EnQueue(LinkQueue &Q, ElemType x)
{
QNode *s = new QNode; // 创建新结点s
s->data = x; // 将新元素x赋值给新结点s的数据域
s->next = Q.rear->next; // 新结点s的next指针指向头结点的next指针指向的结点,即尾结点
Q.rear->next = s; // 尾结点的next指针指向新结点s,更新尾结点指针
Q.rear = s; // 队尾指针指向新结点s
}
```
出队列:
```
bool DeQueue(LinkQueue &Q, ElemType &x)
{
if (Q.front == Q.rear) return false; // 队列为空,无法出队
QNode *p = Q.front->next; // p指向队头结点
x = p->data; // 保存队头结点的数据域到x
Q.front->next = p->next; // 头结点的next指针指向队头结点的下一个结点
if (Q.rear == p) Q.rear = Q.front; // 如果p指向的结点是队尾结点,则更新尾指针为头结点
delete p; // 释放队头结点的内存
return true;
}
```
阅读全文