Python实现Stack（栈）：POP函数功能异常问题排查

你的POP函数失效是因为代码存在几处关键错误，栈完全可以通过带prev指针的双向链表实现，这是合理且高效的实现方式，以下是具体问题分析和修正方案：

原代码的核心问题 #

1. 迭代器逻辑错误：__iter__方法中current = self.next是笔误，应该是current = current.next，这会导致你打印栈时无法正确遍历元素，误以为POP操作没生效。
2. Push时未维护prev指针：新增栈顶元素时，没有将新元素的prev指向当前栈顶，导致POP时无法回溯到前一个元素。
3. Pop逻辑错误：直接将self.top设为None，既没有正确更新栈顶到前一个元素，也没有断开原栈顶元素的链表引用，导致原元素依然存在于链表中。
4. Is_empty方法冗余：无需调用len()，直接判断栈顶/栈底是否为空即可。

修正后的完整代码 #

# FOLLOWS LIFO
class StackElement:
    def __init__(self, value, prev=None, next=None):
        self.value = value
        self.prev = prev
        self.next = next


class Stack:
    def __init__(self, values):
        self.bottom = None
        self.top = None

        for v in values:
            self.push(v)

    def __str__(self):
        res = [str(x.value) for x in self]
        return " -> ".join(res)

    def __iter__(self):
        current = self.bottom
        while current:
            yield current
            current = current.next  # 修正迭代逻辑

    def __len__(self):
        res = 0
        current = self.bottom
        while current:
            res += 1
            current = current.next
        return res

    def push(self, value):
        if self.bottom is None:
            self.bottom = self.top = StackElement(value)
        else:
            new_element = StackElement(value, prev=self.top)  # 维护prev指针
            self.top.next = new_element
            self.top = new_element
        return self.top

    def pop(self):
        if self.is_empty():
            return None
        
        popped_element = self.top
        # 处理栈中只剩一个元素的情况
        if self.top == self.bottom:
            self.bottom = self.top = None
        else:
            self.top = self.top.prev  # 将栈顶回溯到前一个元素
            self.top.next = None  # 断开原栈顶的引用
        
        return popped_element.value  # 返回弹出的元素值，符合常规栈API

    def peek(self):
        return self.top.value if not self.is_empty() else None

    def is_empty(self):
        return self.top is None  # 简化空栈判断


if __name__ == "__main__":
    s = Stack(["2", "3", "4"])
    print(s)
    s.push("5")
    print(s, s.top.value, s.bottom.value)
    popped_val = s.pop()
    print(f"弹出元素: {popped_val}")
    print(s, s.top.value, s.bottom.value)
    res = [str(x.value) for x in s]
    print(res)
    print(s)

修正后的控制台输出 #

2 -> 3 -> 4
2 -> 3 -> 4 -> 5 5 2
弹出元素: 5
2 -> 3 -> 4 4 2
['2', '3', '4']
2 -> 3 -> 4

说明 #

使用带prev指针的双向链表实现栈，能够保证push和pop操作都是**O(1)**时间复杂度，完全符合栈的LIFO（后进先出）特性，是一种标准的栈实现方式。

内容的提问来源于stack exchange，提问作者S.A.D.