单链表实现队列

题目解析

队列的特点是先进先出，其实和单链表的结构类似。我们只需要实现队列的基本功能即可。

• 定义队列

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  # 返回被移除的元素值