python - 如何在 python 中创建 Drop-Out Stack？

Question

我知道你们喜欢就某件事提出具体问题，但我无法弄清楚我到底做错了什么。也许是缺乏理解，所以我想我可以多用几双眼睛。我正在尝试在 python 中创建所谓的 Drop-Out 堆栈，其中顶部输入的值会弹出底部的值，就像程序中撤消函数使用的过程一样。当我将新值插入堆栈时，最旧的值应该消失。

这是我的 Node 类:

class Node(object):

    def __init__(self, data, next = None):
        """Instantiates a Node with default next of None"""
        self.data = data
        self.next = next

正文:

from node import Node

class DropOutStack(object):

    def __init__(self, n):
        self._top = None
        self._size = 0
        self._maxlen = n #Appointed last variable that we are interested in finding

    def push(self, newItem):
        """Inserts newItem at top of stack."""
        self._top = Node(newItem, self._top)
        if self._size < self._maxlen:
            self._size += 1
        #Pops off last link if max length has been reached
        else:
            while self._top.next.next != None:
                self._top = self._top.next
            removedItem = self._top.next.data
            self._top.next = None


    def pop(self):
        """Removes and returns the item at top of the stack.
        If stack is empty, returns none with an error message."""
        try:
            oldItem = self._top.data
            self._top = self._top.next
            self._size -= 1
            return oldItem
        except AttributeError:
            print "ERROR: Cannot pop. Stack is empty"
            return None

    def peek(self):
        """Returns the item at top of the stack.
        If stack is empty, returns none with an error message."""
        try:
            return self._top.data
        except AttributeError:
            print "ERROR: Cannot peek. Stack is empty"
            return None            

    def __len__(self):
        """Returns the number of items in the stack."""
        return self._size

    def isEmpty(self):
        return len(self) == 0

    def __str__(self):
        """Items strung from bottom to top."""

        # Helper recurses to end of nodes
        def strHelper(probe):
            if probe is None:
                return ""
            else:
                return strHelper(probe.next) + \
                       str(probe.data) + " "

        return strHelper(self._top)

问题似乎出在push方法上。我认为我的代码只会访问列表中的第三个节点，但我希望它能够处理 5 个值长的堆栈(本例中 n 为 5)。

你们认为我做错了什么？我是否需要另一个 .next 来使其成为 self._top.next.next.next ？

这是我通过 main 函数获得的示例输出:

def main():
    s = DropOutStack(5)
    for i in xrange(10):
        s.push(i+1)
        print s

1 
1 2 
1 2 3 
1 2 3 4 
1 2 3 4 5 
1 2 3 4 5 6 
1 2 3 4 5 6 7 
1 2 3 4 5 6 7 8 
1 2 3 4 5 6 7 8 9 
1 2 3 4 5 6 7 8 9 10 

1 2 3 4 5 之后的输出应如下所示

2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
6 7 8 9 10

附注我知道我可以对队列做同样的事情。但我们试图在这里搞乱堆栈。

编辑:稍微编辑了推送方法。

Answer 1

您应该使用局部变量(例如top)来遍历堆栈，而不是修改self._top

def push(self, newItem):
    """Inserts newItem at top of stack."""
    self._top = Node(newItem, self._top)
    #Pops off last link if max length has been reached
    top = self._top
    if self._size >= self._maxlen:
        while top.next.next != None:
            top = top.next
        removedItem = top.next.data
        top.next = None
    else:
        self._size += 1

如果添加和删除项目，也不应该增加大小