假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素节点(注意不设头指针),编写相应的队列初始化、入队列和出队列的算法。
时间: 2024-04-30 11:01:50 浏览: 20
队列初始化:
```
void initQueue(LinkList &rear) {
rear = (LinkList)malloc(sizeof(ListNode)); // 创建头结点
rear->next = rear; // 队列为空,指向自己
}
```
入队列:
```
void enQueue(LinkList &rear, ElemType x) {
LinkList p = (LinkList)malloc(sizeof(ListNode)); // 创建新节点
p->data = x;
p->next = rear->next; // 新节点插入队尾
rear->next = p;
rear = p; // 修改队尾指针
}
```
出队列:
```
bool deQueue(LinkList &rear, ElemType &x) {
if (rear == rear->next) return false; // 队列为空
LinkList p = rear->next->next; // 找到队头节点
x = p->data;
if (p == rear) rear = rear->next; // 队列中只有一个元素
rear->next->next = p->next; // 删除队头节点
free(p);
return true;
}
```
其中,`LinkList` 为指向链表节点的指针类型,`ListNode` 为链表节点的结构体类型,`ElemType` 为队列元素的数据类型。