题目解析
队列的特点是先进先出，其实和单链表的结构类似。我们只需要实现队列的基本功能即可。
- 定义队列
class LinkedListQueue: def __init__(self): # 初始化队列的头尾指针和大小 self.head = None # 队列头部节点 self.tail = None # 队列尾部节点 self.size = 0 # 队列中元素的数量
- 判空
def is_empty(self): """检查队列是否为空""" return self.size == 0
- 查看当前有多少元素
def get_size(self): """返回队列中元素的数量""" return self.size
- 入栈
def offer(self, value): """向队列尾部添加元素""" # 创建新节点 node = ListNode(value) if self.is_empty(): # 如果队列为空，新节点同时成为头尾节点 self.head = node self.tail = node self.size += 1 else: # 如果队列不为空，将新节点链接到尾部，并更新尾指针 self.tail.next = node self.tail = node self.size += 1 return self # 支持链式调用
- 查看head元素
def peek(self): """查看队列头部元素但不移除""" if self.is_empty(): return None # 队列为空时返回None else: return self.head.val # 返回头部节点的值
- 处栈
def poll(self): """移除并返回队列头部元素""" if self.is_empty(): raise Exception("Queue is empty") # 队列为空时抛出异常 # 保存头部节点的值 value = self.head.val # 将头指针移动到下一个节点 self.head = self.head.next self.size -= 1 # 重要：如果移除后队列为空，需要同时更新尾指针为None # 防止tail指针悬空指向已移除的节点 if self.head is None: self.tail = None return value # 返回被移除的元素值