Python基于dataclass实现Deque双端队列运行异常问题求解

• add_first方法问题
  1. 缺失非空队列的头部插入逻辑，队列不为空时调用该方法不会修改链表结构，新节点无法被插入到队列头部
  2. 方法内部耦合了队列序列化打印逻辑，违反单一职责原则，插入方法不应该负责队列内容输出
• remove_first方法问题
  1. 逻辑冗余且不完整：self.head == self.tail和self.size == 1是等价判断，后者分支永远无法触发；同时缺失队列长度大于1时的删除逻辑，长度大于1时调用该方法无任何效果
  2. 空队列删除分支没有返回值，和其他分支返回节点值的逻辑不一致
• 缺失remove_last方法：代码中完全未实现尾部删除功能，无法完成双端队列的尾部删除操作
• 额外隐患：Node类的nxt属性类型标注使用了未完成定义的Node类，低版本Python会触发类型标注报错

1. 补全add_first非空场景的插入逻辑，将打印逻辑抽为单独的__str__内置方法
2. 清理remove_first的冗余判断，补全长度大于1时的删除逻辑，统一所有分支的返回值
3. 实现remove_last方法，处理空队列、长度为1、长度大于1三种场景的删除逻辑
4. 新增from __future__ import annotations兼容类内部的类型标注

from __future__ import annotations
from dataclasses import dataclass

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

@dataclass
class Deque:
    head: Node = None      # First node in queue
    tail: Node = None      # Last node in queue
    size: int = 0

    def add_first(self, n):
        new = Node(n, None)
        if self.head is None:
            self.head = new
            self.tail = new
        else:
            # 新节点指向旧头节点，更新头节点为新节点
            new.nxt = self.head
            self.head = new
        self.size += 1

    def add_last(self, n):
        new = Node(n, None)
        if self.head is None:
            self.head = new
            self.tail = new
        else:
            self.tail.nxt = new
            self.tail = new
        self.size += 1

    def get_last(self):
        if self.tail is None:
            print("Get can't be applied on an empty list")
            return None
        return self.tail.value       

    def get_first(self):
        if self.head is None:
            print("Get can't be applied on an empty list")
            return None
        return self.head.value

    def remove_first(self):
        if self.head is None:
            print("Remove can't be applied on an empty list")
            return None
        res = self.head.value
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.nxt
        self.size -= 1
        return res
    
    def remove_last(self):
        if self.head is None:
            print("Remove can't be applied on an empty list")
            return None
        res = self.tail.value
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            # 遍历找到倒数第二个节点
            cur = self.head
            while cur.nxt != self.tail:
                cur = cur.nxt
            cur.nxt = None
            self.tail = cur
        self.size -= 1
        return res

    # 队列序列化方法，调用print时自动触发
    def __str__(self):
        s = "{ "
        node = self.head
        while node is not None:
            s += str(node.value) + " "
            node = node.nxt
        s += "}"
        return s

使用如下测试代码运行：

d = Deque()
# 尾部插入1-10
for i in range(1, 11):
    d.add_last(i)
print(d)
print("Size:", d.size)
# 头部插入11-20
for i in range(11, 21):
    d.add_first(i)
print(d)
print("Size:", d.size)

输出结果和你给出的运行结果完全一致：

{ 1 2 3 4 5 6 7 8 9 10 }
Size: 10
{ 20 19 18 17 16 15 14 13 12 11 1 2 3 4 5 6 7 8 9 10 }
Size: 20

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