在Python中实现堆栈：POP函数的问题

Question

我正在尝试从头开始用Python实现堆栈数据结构。不幸的是，我的弹出功能有问题。

pop函数应该删除栈顶元素。不幸的是，在我的实现中，运行 pop 然后打印数组返回与 pop 函数之前相同的数组。

如何更好的实现pop功能？我可以做 self.top = self.top.prev，但我不确定在堆栈数据结构中我们是否可以访问以前的元素。

# FOLLOWS LIFO


class StackElement:
    def __init__(self, value, prev=None, next=None):
        self.value = value
        self.prev = prev # Not sure if this is available in the Stack DS...
        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:
            self.top.next = StackElement(value)
            self.top = self.top.next
        return self.top

    def pop(self):
        if not self.is_empty():
            self.top = None
        return self.top

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

    def is_empty(self):
        if len(self) != 0:
            return False
        return True


if __name__ == "__main__":
    s = Stack(["2", "3", "4"])
    print(s)
    s.push("5")
    print(s, s.top.value, s.bottom.value)
    s.pop()
    print(s, s.top, s.bottom.value)
    res = [str(x.value) for x in s]
    print(res)
    print(s)

控制台输出：

2 -> 3 -> 4
2 -> 3 -> 4 -> 5 5 2
2 -> 3 -> 4 -> 5 None 2
['2', '3', '4', '5']
2 -> 3 -> 4 -> 5

Answer 1

我试图为你简化逻辑。阅读添加的评论以了解。在我看来，使用 .next 或 .previous 适合链接列表。

代码：

# FOLLOWS LIFO

class StackElement:
    def __init__(self, value): 
        self.value = value


class Stack:
    def __init__(self, values):
        self.values = [] #all values in stack
        self.top = -1 #current element index

        for v in values: 
            self.push(v) 

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

    def __iter__(self):
        end = 0
        while end:
            yield self.values[end]
            end += 1

    def __len__(self):
        return len(self.values) #return list size simply

    def push(self, value):
        self.values.append(value) #assuming if there is no max size of stack, then push at the end of list
        self.top += 1 #current index + 1 as one element is added

    def pop(self):
        if not self.is_empty(): #atleast one element in stack
            self.values = self.values[:self.top] #overwrite list without the last element to follow lifo
            self.top -= 1 #current index - 1 as one element is removed

    def peek(self):
        if not self.is_empty():
            return self.values[self.top] #return last element in list

    def is_empty(self):
        if len(self.values) != 0:
            return False
        return True


if __name__ == "__main__":
    s = Stack(["2", "3", "4"])
    print(s)
    s.push("5")
    print(s, s.top)
    s.pop()
    print(s, s.top)
    res = [str(x) for x in s.values]
    print(res)
    print(s)

输出：

2 -> 3 -> 4
2 -> 3 -> 4 -> 5 3
2 -> 3 -> 4 2
['2', '3', '4']
2 -> 3 -> 4

作为程序员，最好不要使代码过于复杂，因为这样可以节省时间和内存。祝你有美好的一天！