Stack

可以直接使用列表来实现。

Stack() creates a new stack that is empty. It needs no parameters and returns an empty stack.
push(item) adds a new item to the top of the stack. It needs the item and returns nothing.
pop() removes the top item from the stack. It needs no parameters and returns the item. The stack is modified.
peek() returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.
isEmpty() tests to see whether the stack is empty. It needs no parameters and returns a boolean value.
size() returns the number of items on the stack. It needs no parameters and returns an integer.



In [13]:

    
class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

if __name__ == '__main__':
    stack = Stack()
    stack.push(12)
    print stack.items

我们需要注意的是，在这里我们把列表的尾作为“栈顶”，因此 push 和 pop 的操作使用了列表的append和pop方法。这两个方法的时间复杂度都是 O(1)。

小练习：string 倒转



In [15]:

    
def revstring(mystr):
    # your code here
    stack = Stack()
    for x in mystr:
        stack.push(x)
    length = len(mystr)
    reversed_str = ''
    while not stack.isEmpty():
        reversed_str += stack.pop()
    return reversed_str

if __name__ == '__main__':
    assert revstring('apple') == 'elppa'

小练习：括号匹配