Python使用List实现栈

1、打开Python开发工具IDLE，新建‘Stack.py’文件，并写代码如下：

class Stack:

  def __init__(self):

    self.items = []

  def isEmpty(self):

    return self.items == []

  def length(self):

    return len(self.items)

  def push(self,item):

    self.items.append(item)

  def pop(self)

    return self.items.pop()

这里先实现了构造函数，初始栈的列表为空，用list的append和pop方法实现入栈和出栈，好处在于时间复杂度均仅为O(1).

2、编写main函数如下;

if __name__ == '__main__':

  stack = Stack()

  print (stack.isEmpty())

  stack.push(1)

  stack.push(2)

  print (stack.isEmpty())

  print (stack.length())

  print (stack.pop())

3、F5运行程序，程序初始为空，先后入栈1，2，出栈时候2先出。

True

False

2

2

4、继续编写peek函数，peek函数只是查看栈顶元素，在这里是栈内部的List的底。

def peek(self):

    return self.items[-1]

5、peek函数还可以写成如下形式，同时改写main以测试peek函数

  def peek(self):

    return self.items[len(self.items)-1]

if __name__ == '__main__':

  stack = Stack()

  print (stack.isEmpty())

  stack.push(1)

  stack.push(2)

  print (stack.isEmpty())

  print (stack.length())

  print (stack.pop())

  print (stack.peek())

6、F5运行程序，打印出信息如下peek得到栈顶元素为1

True

False

2

2

1