python 基于循环链表队列 头歌

Python 中基于循环链表实现队列（Circular Linked List Queue）是一种数据结构的应用，它结合了链表的特点和队列的操作规则。在循环链表队列中，最后一个节点的下一个指针指向第一个节点，形成一个闭环，这样可以避免普通链表在插入和删除元素时可能出现的头节点空的问题。

创建一个简单的循环链表队列，我们可以这样设计：

1. 首先，我们需要定义一个Node类，表示链表节点，包含数据和指向下一个节点的引用。
2. 然后，创建Queue类，维护头节点、尾节点以及队列长度等信息。
- `enqueue()`方法用于在尾部添加元素，将新节点设置为尾节点并更新尾节点的next指针。
- `dequeue()`方法用于移除头部元素，如果队列为空则返回异常，否则调整头节点的next指针。
- `is_empty()`方法检查队列是否为空。
- `size()`方法获取队列当前元素的数量。

示例代码大致如下：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class CircularLinkedListQueue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    def enqueue(self, item):
        new_node = Node(item)
        if not self.is_empty():
            self.tail.next = new_node
        else:
            new_node.next = self.head
        self.tail = new_node
        self.length += 1

    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        else:
            temp = self.head
            self.head = self.head.next
            if self.head == self.tail:
                self.tail = None
            self.length -= 1
            return temp.data

    def is_empty(self):
        return self.head is None or self.length == 0

    def size(self):
        return self.length

# 使用示例
q = CircularLinkedListQueue()
q.enqueue(1)
q.enqueue(2)
print(q.dequeue())  # 输出：1