python本关任务:用带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(不设头指针)。实现该队列的入队出队以及判断队列是否为空操作。
时间: 2024-10-19 11:12:34 浏览: 41
python如何对链表操作
在Python中,我们可以创建一个循环链表结构来实现这种特殊的队列,其中只有一个指针`tail`用于跟踪队尾节点。这里是一个简单的实现:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class CircularQueue:
def __init__(self):
self.tail = None
self.size = 0
# 入队(enqueue)
def enqueue(self, data):
new_node = Node(data)
if not self.is_empty():
self.tail.next = new_node
new_node.next = self.tail # 设置新节点的下一个节点为当前尾节点,形成循环
else:
new_node.next = new_node # 队列初始时,只有一个元素,尾指针也指向它
self.tail = new_node
self.size += 1
# 出队(dequeue)
def dequeue(self):
if self.is_empty():
return None
removed_data = self.tail.data
if self.size == 1: # 如果队列只剩一个元素,需要更新尾指针并减小size
self.tail = None
else:
self.tail = self.tail.next
self.size -= 1
return removed_data
# 判断队列是否为空
def is_empty(self):
return self.size == 0
# 获取队列长度
def get_size(self):
return self.size
# 使用示例
cq = CircularQueue()
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print(cq.dequeue()) # 输出:3
print(cq.get_size()) # 输出:2
```
在这个实现中,我们维护了一个`CircularQueue`类,内部包含`Node`类作为单向循环链表的节点。入队时,新建节点并将其连接到现有尾节点之后;出队时,删除尾部的节点;判断队列空则检查大小是否为0。
阅读全文