用python实现以下内容。假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点(不设队头指针),试编写相应的置空队列、入队列、出队列的算法。给出完整代码
时间: 2024-04-29 20:25:53 浏览: 2
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.rear = Node() # 队尾结点
self.rear.next = self.rear # 初始为空队列,队尾指向头结点
def is_empty(self):
return self.rear.next == self.rear
def clear(self):
self.rear.next = self.rear
def enqueue(self, item):
new_node = Node(item)
new_node.next = self.rear.next
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if self.is_empty():
return None
p = self.rear.next.next
if p.next == p: # 队列只有一个元素
self.rear = self.rear.next # 队列为空
else:
self.rear.next.next = p.next
return p.data
if __name__ == '__main__':
q = Queue()
print(q.is_empty()) # True
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue()) # 1
print(q.dequeue()) # 2
print(q.is_empty()) # False
q.clear()
print(q.is_empty()) # True
```