假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点,试编写相应的初始化队列,入队列和出队列算法用c++表示
时间: 2023-06-09 21:02:57 浏览: 117
好的,我明白了。以下是相应的算法:
初始化队列:
```
void initQueue(LinkQueue &Q) {
Q.front = Q.rear = (LinkNode*) malloc(sizeof(LinkNode)); // 创建头结点
Q.front->next = Q.front; // 头结点指向自己,表示空队列
}
```
入队列:
```
void enQueue(LinkQueue &Q, ElemType x) {
LinkNode *s = (LinkNode*) malloc(sizeof(LinkNode));
s->data = x;
s->next = Q.rear->next; // 新节点指向头结点
Q.rear->next = s; // 将新节点插入队尾
Q.rear = s; // 修改队尾指针
}
```
出队列:
```
bool deQueue(LinkQueue &Q, ElemType &x) {
if(Q.front == Q.rear) return false; // 空队列
LinkNode *p = Q.front->next;
x = p->data;
Q.front->next = p->next; // 将头结点指向删除节点的下一个节点
if(Q.rear == p) Q.rear = Q.front; // 如果删除的是队尾节点,修改队尾指针
free(p); // 释放空间
return true;
}
```
其中,`LinkNode` 是循环链表的节点结构体,`LinkQueue` 是队列结构体,`ElemType` 是数据元素类型。
阅读全文