Python如何删除dataclass实现的双端队列实例中的末尾节点

补全后的完整实现代码 #

from dataclasses import dataclass
from typing import Any

@dataclass
class Node:
     value: int = None
     nxt: Any = None


@dataclass
class Deque:
    head: Node = None
    tail: Node = None
    size: int = 0

    def remove_last(self):
        # 空队列直接返回
        if self.tail is None:
            return None
        # 队列仅存1个节点的特殊情况处理
        if self.head == self.tail:
            removed_val = self.head.value
            self.head = None
            self.tail = None
            self.size -= 1
            return removed_val
        # 多节点场景：从头遍历找尾节点的前驱节点
        _node = self.head
        while _node.nxt != self.tail:
            _node = _node.nxt
        # 保存被删除节点的值
        removed_val = self.tail.value
        # 断开前驱节点和原尾节点的连接
        _node.nxt = None
        # 更新尾节点为前驱节点
        self.tail = _node
        # 维护队列长度属性
        self.size -= 1
        return removed_val

实现说明 #

由于你定义的Node类仅保存了后继节点指针nxt，没有前置节点指针，因此删除尾节点必须从头遍历找到尾节点的前驱节点才能完成操作：

• 空队列场景直接返回即可，原代码返回str(None)不符合常规设计，调整为直接返回None
• 单独处理队列只有1个节点的边界情况，避免遍历逻辑失效
• 遍历终止条件为当前节点的下一个节点等于尾节点，此时当前节点就是尾节点的前驱节点
• 操作完成后必须更新tail和size属性，保证双端队列其他方法可以正常运行

按照你给出的队列示例调用该方法后，会删除值为10的尾节点，新的尾节点为值为9的节点，和你预期的head结构完全一致。

内容的提问来源于stack exchange，提问作者William Abrahamsson