1. 时间复杂度（大O表示法）以及使用python实现栈
1.时间复杂度（大O表示法）：
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
(1)Python中常用数据结构的时间复杂度：
list内置操作的时间复杂度：
dict内置操作的时间复杂度：
(2)抽象数据类型（ADT: Abstract Data Type）:
常用数据运算（5种）：
增（插入）
删（删除）
改（修改）
查（查找）
排序
2. 栈的实现：
（1）栈的表现形式：
（2）栈的操作：
Stack(): 创建一个新的空栈
push(item):添加一个新元素item到栈顶
pop(): 弹出栈顶元素
peek(): 返回栈顶元素
is_empty(): 判断栈是否为空
size(): 返回栈的元素个数
（3）实现栈：
1 class Stack(object): 2 """栈的实现""" 3 def __init__(self): 4 self.__list = [] 5 6 # 添加一个新元素item到栈顶 7 def push(self, item): 8 self.__list.append(item) 9 10 # 弹出栈顶元素 11 def pop(self): 12 return self.__list.pop() 13 14 # 返回栈顶元素 15 def peek(self): 16 if self.__list: 17 return self.__list[-1] 18 else: 19 return None 20 21 # 判断栈是否为空 22 def is_empty(self): 23 return self.__list == [] 24 25 # 返回栈的元素个数 26 def size(self): 27 return len(self.__list) 28 29 30 if __name__ == "__main__": 31 s = Stack() 32 s.push(1) 33 s.push(2) 34 s.push(3) 35 s.push(4) 36 37 print(s.pop()) 38 print(s.pop()) 39 print(s.pop()) 40 print(s.pop())
运行结果：