当前位置: 首页 > news >正文

链表实现双端队列

  • 定义链表
class ListNode:  def __init__(self, value):  self.val = value  # 节点存储的值  self.prev = None  # 指向前一个节点的指针  self.next = None  # 指向后一个节点的指针
  • 定义双端队列
class DoublyLinedList:  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 add_at_head(self, value):  """在链表头部添加节点"""  # 创建新节点  node = ListNode(value)  # 如果链表为空,新节点既是头节点也是尾节点  if self.size == 0:  self.head = node  self.tail = node  else:  # 链表不为空时,将新节点插入到头部  node.next = self.head  # 新节点的next指向原头节点  self.head.prev = node  # 原头节点的prev指向新节点  self.head = node  # 更新头节点为新节点  self.size += 1  # 链表长度加1  return self.size
  • 队列尾部插入元素
def add_at_tail(self, value):  """在链表尾部添加节点"""  # 创建新节点  node = ListNode(value)  # 如果链表为空,新节点既是头节点也是尾节点  if self.size == 0:  self.head = node  self.tail = node  else:  # 链表不为空时,将新节点插入到尾部  node.prev = self.tail  # 新节点的prev指向原尾节点  self.tail.next = node  # 原尾节点的next指向新节点  self.tail = node  # 更新尾节点为新节点  self.size += 1  # 链表长度加1  return self.size
  • 查看队列头元素的值
def peek_at_head(self):  """查看头节点的值(不删除节点)"""  if self.size == 0:  raise Exception("DoublyLinkedList is empty")  return self.head.val
  • 查看队列尾元素的值
def peek_at_tail(self):  """查看尾节点的值(不删除节点)"""  if self.size == 0:  raise Exception("DoublyLinkedList is empty")  return self.tail.val
  • 从队列头部弹出
def pop_at_head(self):  """删除并返回头节点的值"""  if self.size == 0:  raise Exception("DoublyLinkedList is empty")  # 保存头节点的值用于返回  head_value = self.head.val  # 如果链表中只有一个节点  if self.head == self.tail:  self.head = self.tail = None  # 清空链表  else:  # 链表中有多个节点  next_node = self.head.next  # 保存头节点的下一个节点  next_node.prev = None  # 断开原头节点与后续节点的连接  self.head = next_node  # 更新头节点为下一个节点  self.size -= 1  # 链表长度减1  return head_value  # 返回被删除节点的值
  • 从队列尾部弹出
def pop_at_tail(self):  """删除并返回尾节点的值"""  if self.size == 0:  raise Exception("DoublyLinkedList is empty")  # 保存尾节点的值用于返回  tail_value = self.tail.val  # 如果链表中只有一个节点  if self.head == self.tail:  self.head = self.tail = None  # 清空链表  else:  # 链表中有多个节点  prev_node = self.tail.prev  # 保存尾节点的前一个节点  prev_node.next = None  # 断开原尾节点与前驱节点的连接  self.tail = prev_node  # 更新尾节点为前一个节点  self.size -= 1  # 链表长度减1  return tail_value  # 返回被删除节点的值å
http://www.hskmm.com/?act=detail&tid=22489

相关文章:

  • FFmpeg和ZLMediaKit 实现本地视频推流
  • SQL 多表查询速查:JOIN、子查询一文全掌握 - 详解
  • 深入解析:数字和字节:Linux 中的内存如何工作?
  • AtCoder Beginner Contest 424 425 部分题解
  • 关于滚动数组
  • 第九篇
  • 2025 年宁波搬家公司推荐 TOP 权威榜单发布,多维度解读宁波搬家服务公司创新亮点举措
  • 2025 年检测器厂家推荐 TOP 品牌权威排名,防爆火焰 / 一体化火焰 / 紫外线火焰 / 离子火焰 / 红外线火焰 / 红紫外复合火焰 / 智能火焰检测器公司推荐
  • 9-29
  • 10-1
  • 2025母线槽源头厂家 TOP 工厂权威榜单揭晓,密集型、封闭、浇筑、耐火、防火、防水、插接式母线槽公司推荐!
  • 2025 年衬氟鹤管源头厂家 TOP 企业品牌推荐排行榜,天然气 / 低温 / LNG / 撬装 / 底装 / 火车 / 装卸车 / 上装 / 衬氟 / 下装鹤管公司推荐这 10 家
  • 2025 铜覆钢圆钢生产商厂家 TOP 企业品牌推荐榜单,铜覆钢接地极 / 棒 / 圆钢 / 扁钢 / 圆线 / 绞线 / 角钢 / 扁铁 / 管公司推荐这 10 家
  • 2025 年喷雾干燥机厂家 TOP 企业品牌推荐排行榜,无锡 / 常州喷雾干燥机 / 离心式 / 压力式 / 气流 / 造粒 / 有机溶剂 / 闭路循环 / 闭式循环 / 实验喷雾干燥机公司推荐!
  • 2025 年工业吊扇最新推荐权威排行榜:TOP5 优质品牌全面解析,助力企业高效选购
  • 2025 同步带源头厂家 TOP 排行榜单公示,碳纤维 / 高扭矩碳纤维 / 高强力 / 保力强 / 摩托车 / 自行车同步带公司推荐
  • 20250928 组合计数
  • 哈希问题的一类技巧
  • CVPR-2025 | 具身导航指令高效生成!MAPInstructor:基于场景图的导航指令生成Prompt调整策略 - 详解
  • 2025 年无锡西门子产品供应商 TOP 企业品牌排行榜,PLC,高低压变频器,高低压电机代理分销商推荐
  • 2025 年树脂排水沟厂家 TOP 品牌权威排行榜单,U 形、线性、成品、混凝土、园林、市政、玻璃钢树脂排水沟公司推荐
  • 2025 年石墨烯厂家推荐 TOP 品牌排行榜单最新发布,氧化 / 羧基化 / 巯基化 / 羟基化 / 氨基化 / 氮掺杂氧化 / 氮掺杂石墨烯公司推荐
  • AtCoder Grand Contest 015 - E - Mr.Aoki Incubator
  • 9.30 CSP-S模拟25 改题记录
  • 全球抗体药表达系统:CHO 细胞主导下,未来十年将迎哪些突破?
  • 完整教程:[论文阅读]Benchmarking Poisoning Attacks against Retrieval-Augmented Generation
  • 绕过Cloudflare IP白名单限制的技术解析
  • 撕裂的乡土:在人性荒原上寻找微光
  • 2025蔬菜配送服务公司 TOP 企业推荐排行榜,深圳、宝安、光明、松岗、东莞、长安、虎门、沙田、厚街、大岭山蔬菜配送推荐
  • 2025液压缸TOP企业品牌推荐排行榜!抓斗、伺服、大吨位、车辆、工程、拉杆、冶金、重载、港机液压缸推荐