Python 栈迭代的最佳实践

Question

在Python中，如何遍历一个栈？最好的方法是像遍历列表一样使用for循环吗？

Answer 1

在Python中，跟C++这样的编程语言不同，我们没有预定义的栈这种数据结构，只有普通的列表（List）。

所以，如果你想把你的“栈”当成普通列表来使用，你只需要像这样做：

for item in reversed(my_list): # to preserve LIFO
    # do something with item
    # ...

现在，如果你想让你的列表表现得像一个栈（后进先出，LIFO），你可以使用列表自带的两个功能：append和pop：

>>> stack = [1, 2]
>>> stack.append(3)
>>> stack.append(4)
>>> stack
[1, 2, 3, 4]
>>> stack.pop()
4
>>> stack
[1, 2, 3]

想了解更多，可以查看这个链接：http://docs.python.org/tutorial/datastructures.html#using-lists-as-stacks

Answer 2

如果你的栈可能会变得很大，那你绝对不应该使用 List 或者自己写的栈类。Raymond Hettinger 已经为你做好了这方面的工作，他写了一个很棒的 collections.deque。这个 deque 是一种类似列表的数据结构，可以在两端快速添加和删除元素。

>>> from collections import deque
>>>
>>> stack = deque()
>>> stack.append(1)
>>> stack.append(2)
>>> stack.append(3)
>>> print stack
deque([1,2,3])

通过合适地使用 deque.pop() 和 deque.popleft()，你可以分别实现后进先出（FILO）和先进先出（FIFO）。如果你想要先进先出，可以用 for item in stack 来遍历它；如果想要后进先出，可以用 for item in reversed(stack)，这样会生成一个内存使用更高效的反向迭代器。

Answer 3

正如其他人所说，Python其实没有内置的栈这种数据类型，但你可以用列表来模拟一个栈。

当你把列表当作栈用时，可以用append()方法来添加元素（相当于“压栈”），用pop()方法来移除元素（相当于“弹栈”），就像julio.alegria所描述的那样。

如果你想在for循环中使用这个列表，但又希望它保持后进先出（FILO）的特性，可以用这个切片语法来反转元素的顺序：[::-1]。

示例：

for element in stack[::-1]:
    print element

如果你使用的是一个自定义类来实现栈，只要这个类定义了__iter__()和next()方法，你就可以在列表推导式、for循环等地方使用它。

这样，你就可以实现一个自定义的迭代器，在遍历时移除元素，就像一个真正的栈应该那样。

示例：

class Stack:
    def __init__(self):
        self.data = []
    def push(self,n):
        self.data.append(n)
    def pop(self):
        return self.data.pop()
    def __iter__(self):
        return self
    def next(self):
        if len(self.data)>0:
            return self.pop()
        else:
            raise StopIteration

filo = Stack()
filo.push(1)
filo.push(2)
filo.push(3)

for i in filo:
    print i

Python 栈迭代的最佳实践

3 个回答

撰写回答