单指针循环链表实现队列：初始化、入队、出队算法详解

本文将详细介绍使用单指针循环链表实现队列的算法，并提供 C++ 代码示例。

队列是一种先进先出的线性数据结构，其特点是只能在队尾添加元素，只能在队头删除元素。

循环链表是一种特殊的链表，其最后一个节点的 next 指针指向链表的第一个节点，形成一个环状结构。

在本例中，我们使用一个指针指向队尾结点，并通过操作该指针来实现队列的各种操作。

队列初始化算法

void InitQueue(LinkNode *&rear) {
    rear = new LinkNode; // 创建头结点
    rear->next = rear; // 将头结点的next指针指向自身，表示队列为空
}

创建一个新的结点作为头结点，并将其 next 指针指向自身，表示队列为空。

入队列算法

void EnQueue(LinkNode *&rear, ElemType x) {
    LinkNode *p = new LinkNode; // 创建新结点
    p->data = x; // 新结点赋值
    p->next = rear->next; // 新结点的next指针指向队头结点
    rear->next = p; // 队尾结点的next指针指向新结点
    rear = p; // 修改队尾指针
}

创建一个新的结点 p，并将要入队的元素 x 赋值给 p 的 data 字段。
将 p 的 next 指针指向队头结点 (rear->next)。
将队尾结点的 next 指针指向 p。
将队尾指针 rear 指向新结点 p。

出队列算法

bool DeQueue(LinkNode *&rear, ElemType &x) {
    if (rear->next == rear) { // 队列为空
        return false;
    }
    LinkNode *p = rear->next->next; // 取出队头结点
    x = p->data; // 保存队头元素
    if (p == rear) { // 队列只有一个元素
        rear = rear->next; // 修改队尾指针
    }
    rear->next->next = p->next; // 删除队头结点
    delete p; // 释放队头结点的空间
    return true;
}

判断队列是否为空。如果为空，返回 false。
取出队头结点 p (rear->next->next)。
将队头元素的值赋给 x。
如果队列只有一个元素，则将队尾指针 rear 指向队头结点 (rear->next)。
将队尾结点的 next 指针指向 p 的下一个节点 (p->next)，从而删除队头结点。
释放队头结点 p 的空间。
返回 true。

总结

本文介绍了使用单指针循环链表实现队列的初始化、入队和出队算法。这种方法简单易懂，并且可以有效地利用空间。在实际应用中，我们可以根据具体需求选择合适的队列实现方式。