在 Python 中反转堆栈

Question

反转堆栈：

我做了一个空的临时栈
我用了tempstack.push(stack.pop())
然后重命名为stack = tempstack

不过好像不行。知道为什么吗？

要调用它，我只想使用 reverse(stack)，而不是 stack = reverse(stack)。

def reverse(stack):
    new_stack = Stack()
    while not stack.is_empty():
        new_stack.push(stack.pop())
    stack = new_stack

Answer 1

看来你应该写while not stack.is_empty():

（编辑后）好的，现在 stack = new_stack 应该是 return new_stack。应使用 stack = reverse(stack).

调用该函数

（回复评论）如果返回一个值不是一个选项，那么我们需要知道有哪些方法可以修改Stack对象。说 stack = new_stack 或 stack = Stack() 不会在函数外更改它。

像这样的东西应该可以工作：

def reverse(stack):
    new_stack = Stack()
    while not stack.is_empty():
        new_stack.push(stack.pop())
    stack._items = new_stack._items

然而，这可能不是一个好主意，因为 _items 前面的下划线表明编写 Stack class 的人不希望以这种方式使用它。

此外，正如@user4815162342 指出的那样，这可能会反转堆栈两次，因此我们不应该使用临时 new_stack = Stack() 而应该只使用临时列表。真的@user4815162342 的回答是最好的。

Answer 2

添加一个return值

def reverse(stack):
    new_stack = Stack()
    while not stack.is_empty():
        new_stack.push(stack.pop())
    return new_stack

并在调用函数时执行此操作：

stack = reverse(stack)

您正在为函数内部堆栈赋值，但不是从您调用它的地方赋值。范围问题。

Answer 3

如果您使用实际的 list 来实现堆栈（也就是说，如果 Stack 继承自 list 或者基本上是一个列表），然后简单地反转 list 就地：

def reverse_stack(stack):
    stack.reverse()

为了避免混淆，我将函数重命名为 reverse_stack；你可以仍然称它为reverse。示例：

>>> stack = [1, 2, 3]
>>> reverse_stack(stack)
>>> stack
[3, 2, 1]

但是，您的 Stack class 似乎没有继承自 list 而是将基础 list 保留在私有属性中，因此您不能直接在 Stack 上使用任何 MutableSequence API。因此，

版本 2，仅使用 `Stack`

的 is_empty、push 和 pop 方法

并且仅使用 Stacks，而不是 lists 或 deques 等。首先，几个辅助函数：

def reverse_copy_stack(stack, rev_stack=None):
    '''Return a reversed copy of stack, which is emptied.
    rev_stack receives the reversed copy if it's not None
    '''
    if rev_stack is None:
        rev_stack = Stack()
    while not stack.is_empty():
        rev_stack.push(stack.pop())
    return rev_stack

def copy_stack(stack):
    '''Return a copy of stack, which is emptied.'''
    return reverse_copy_stack( reverse_copy_stack(stack))

现在我们可以实现reverse_stack:

def reverse_stack(stack):
    '''Reverse stack in-place'''
    new_stack = copy_stack(stack)
    # Empty stack
    while not stack.is_empty():
        stack.pop()
    # put reversed copy of new_stack in stack
    reverse_copy_stack(new_stack, stack)

Answer 4

先复制栈，清空原来的栈，再按照你的方法。

def reverse(stack):
    old_stack = stack[:]
    while not stack.is_empty():
        stack.pop()
    while not old_stack.is_empty():
        stack.push(old_stack.pop())

Answer 5

正如其他人所指出的，最后一项任务没有做任何事情。然而，这里练习背后的想法可能是只使用标准堆栈原语 push、pop 和 is_empty，而不依赖确切的堆栈实现来使用 [=16] =] 等等。

需要注意的重点是堆栈是后进先出结构，因此读取其内容会自动以相反的顺序生成它们。这就是为什么使用另一个堆栈进行临时存储的解决方案不起作用的原因：

def reverse(stack):
    # Doesn't work
    temp = Stack()
    while not stack.is_empty():
        temp.push(stack.pop())
    while not temp.is_empty():
        stack.push(temp.pop())

这里栈内容颠倒了两次：一次是从原始栈中读取，一次是从临时栈中读取，所以最后栈内容在原来的顺序。要真正反转堆栈，您需要将项目提取到列表中，然后按顺序遍历它（从头到尾），将项目推入原始堆栈：

def reverse(stack):
    items = []
    while not stack.is_empty():
        items.append(stack.pop())
    for item in items:
        stack.push(item)

编辑：受 BrianO 的回答启发，这里有一个完全不使用列表的版本（但会实例化两个临时堆栈）：

def reverse(stack):
    tmp1 = Stack()
    while not stack.is_empty():
        tmp1.push(stack.pop())
    tmp2 = Stack()
    while not tmp1.is_empty():
        tmp2.push(tmp1.pop())
    while not tmp2.is_empty():
        stack.push(tmp2.pop())

这里的想法是利用复制堆栈确实反转内容的事实 - 只是复制它 back 再次反转它。所以我们就复制三次，先从原来的栈到一个临时栈，然后从一个临时栈到另一个个临时栈，最后从另一个临时栈到原来的栈。把内容倒三遍，原来的内容倒过来，这是必须的。

Answer 6

如果堆栈 class 是你的或者你可以扩展它，那么另一种反转堆栈的方法是保持所有数据完好无损，并跟踪堆栈的上升方向（增长或向下）和 push/pop 到堆栈的顶部或底部，具体取决于堆栈方向。然后，您的堆栈反转方法只是更改标志的情况，该标志决定您的堆栈是向上还是向下增长。

我还没有任何代码，但如果您的堆栈很大，那么更改标志可能比反转大量数据要简单得多。

Answer 7

class Stack():
    def __init__(self):
        self.item=[]
        self.n=0
    def __len__(self):
        return self.n
    def isEmpty(self):
        return self.n==0
    def push(self,item):
        self.item.append(item)
        self.n+=1
    def pop(self):
        ele=self.item.pop()
        self.n-=1
        return ele
    def getPeek(self):
        if self.n>0:
            return self.item[-1]
        return "Stack is empty"
    def getStackitem(self):
        return [self.item[i] for i in range(self.n)]


def reversing(data):
    x=Stack()
    for i in data:
        x.push(i)
    y=Stack()
    while not x.isEmpty():
        y.push(x.pop())
    return "".join(y.getStackitem())

print(reversing("123456789"))

在 Python 中反转堆栈

Reversing a Stack in Python

python

stack

版本 2，仅使用 `Stack`

在 Python 中反转堆栈

Reversing a Stack in Python

python

stack

版本 2，仅使用 Stack

版本 2，仅使用 `Stack`