使用数据类实现Deque时元素操作异常问题排查

问题描述 #

使用Python数据类实现Deque（双端队列）时，所有操作返回None，size始终为0，无法正常添加元素。主代码逻辑无误，需排查add_first、add_last等方法的问题。

主代码 #

import Deque as deq

# Program starts
empty = deq.Deque()     # An empty deque
deque = deq.Deque()     # To be filled

for i in range(1, 11):
    deque.add_last(i)
print(deque.to_string())
print("Size:", deque.size)

for i in range(11, 21):
    deque.add_first(i)
print(deque.to_string())
print("Size:", deque.size)

print("\nget_last():", deque.get_last())
print("get_last() on empty deque:", empty.get_last())

print("\nget_first():", deque.get_first())
print("get_first() on empty deque:", empty.get_first())

print("\nremove_first():", deque.remove_first())
print("remove_first() on empty deque:", empty.remove_first())

print("\nremove_last():", deque.remove_last())
print("remove_last() on empty deque:", empty.remove_last())

print(deque.to_string())
print("Size:", deque.size)

print("\nTest to remove all elements")
temp = deq.Deque()
for i in range(100, 106):
    temp.add_first(i)
print("After adding elements:", temp.to_string())
while temp.size > 0:
    temp.remove_last()
print("After removing all elements:", temp.to_string())
print("Size:", temp.size)

Deque类原始代码 #

from dataclasses import dataclass
from typing import Any

@dataclass
class Node:
    value: int = None
    nxt: Any = None  # Any since Node not properly defined at this point

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

 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 to_string(self):
    s = "{ "
    node = self.head
    while node is not None:
        s += str(node.value) + " "
        node = node.nxt
    s += "}"
    return s

def add_first(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
    else:
        return self.tail.value

def get_first(self):
    pass

def remove_first(self):
    pass

def remove_last(self):
    pass

当前错误输出 #

None
Size: 0
None
Size: 0

get_last(): None
get_last() on empty deque: None

get_first(): None
get_first() on empty deque: None

remove_first(): None
remove_first() on empty deque: None

remove_last(): None
remove_last() on empty deque: None
None
Size: 0

Test to remove all elements
After adding elements: None
After removing all elements: None
Size: 0

预期正确输出 #

{ 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

get_last(): 10
You can't access an empty queue
get_last() on empty deque: None

get_first(): 20
You can't access an empty queue
get_first() on empty deque: None

remove_first(): 20
You can't access an empty queue
remove_first() on empty deque: None

remove_last(): 10
You can't access an empty queue
remove_last() on empty deque: None
{ 19 18 17 16 15 14 13 12 11 1 2 3 4 5 6 7 8 9 }
Size: 18

Test to remove all elements
After adding elements: { 105 104 103 102 101 100 }
After removing all elements: { }
Size: 0

问题分析与修复方案 #

1. 类方法缩进错误（核心问题） #

原始代码中Deque类的所有方法（add_last、to_string等）都未缩进在类定义内部，导致这些方法是全局函数而非类的实例方法。调用deque.add_last(i)时，实际未修改实例的head、tail和size属性，这是size始终为0的根本原因。

2. add_first方法逻辑错误 #

原始add_first方法的else分支错误执行了add_last的逻辑（修改tail），正确逻辑应为将新节点的nxt指向当前head，再更新head为新节点。

3. 核心方法未实现 #

get_first、remove_first、remove_last方法仅写了pass，需补充实现逻辑。

4. 提示信息不一致 #

get_last方法的提示信息与预期输出不符，需统一修改为"You can't access an empty queue"。

修复后的Deque类代码 #

from dataclasses import dataclass
from typing import Any

@dataclass
class Node:
    value: Any = 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_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 to_string(self):
        s = "{ "
        node = self.head
        while node is not None:
            s += str(node.value) + " "
            node = node.nxt
        s += "}"
        return s

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

    def get_last(self):
        if self.tail is None:
            print("You can't access an empty queue")
            return None
        else:
            return self.tail.value

    def get_first(self):
        if self.head is None:
            print("You can't access an empty queue")
            return None
        else:
            return self.head.value

    def remove_first(self):
        if self.head is None:
            print("You can't access an empty queue")
            return None
        value = self.head.value
        self.head = self.head.nxt
        # 队列清空时同步更新tail
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value

    def remove_last(self):
        if self.tail is None:
            print("You can't access an empty queue")
            return None
        value = self.tail.value
        # 只有一个节点的情况
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            # 遍历找到倒数第二个节点
            current = self.head
            while current.nxt != self.tail:
                current = current.nxt
            current.nxt = None
            self.tail = current
        self.size -= 1
        return value

额外修正 #

• 主代码中的缩进错误已修正（如for i in range(11,21):下的deque.add_first(i)添加缩进），确保代码能正常执行。
• Node类的value类型改为Any以支持更多数据类型，nxt使用字符串引用'Node'解决前向引用问题。

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