用python实现以下内容。假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点(不设队头指针),试编写相应的置空队列、入队列、出队列的算法。
时间: 2024-05-13 10:13:36 浏览: 43
假定一个单向循环链表来表示队列(即循环链队),该队列只设一个队尾指针,不设队首指针,试编写下列各种运算的算法
4星 · 用户满意度95%
以下是Python代码实现:
```python
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
class Queue:
def __init__(self):
self.rear = Node() # 队尾指针指向头结点
self.rear.next = self.rear # 空队列时,队尾指针指向头结点自身
def is_empty(self):
return self.rear.next == self.rear # 队列为空时,队尾指针指向头结点自身
def enqueue(self, data):
new_node = Node(data)
new_node.next = self.rear.next # 新结点指向头结点
self.rear.next = new_node # 队尾指针指向新结点
self.rear = new_node # 更新队尾指针
def dequeue(self):
if self.is_empty():
raise Exception('队列为空')
else:
node = self.rear.next.next # 出队结点为头结点的下一个结点
data = node.data
if node == self.rear: # 如果出队的结点是队尾结点,则更新队尾指针
self.rear = self.rear.next
self.rear.next.next = node.next # 头结点指向出队结点的下一个结点
return data
def clear(self):
self.rear.next = self.rear # 队尾指针指向头结点自身,相当于清空队列
```
测试:
```python
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue()) # 1
print(queue.dequeue()) # 2
queue.enqueue(4)
queue.clear()
print(queue.is_empty()) # True
```
阅读全文