栈
特点：先进后出（浏览器后退功能）
| 类别 | 时间复杂度 |
|---|---|
| 访问 | O(1)(访问栈顶元素) |
| 搜索 | O(N) |
| 插入 | O(1) |
| 删除 | O(1) |
栈的常用操作：创建栈、添加元素、查看栈顶元素（即将出栈的元素）、删除栈顶元素（即将出栈的元素）、栈的长度、栈是否为空、遍历栈（边删除栈顶元素边遍历）
练习题：力扣20 496
python栈常用操作
#1.创建栈
stack=[]
#2.添加元素 O(1)
stack.append(1)
#3.获取栈顶元素 O(1)
stack[-1]
#4.删除栈顶元素 O(1)
temp=stack.pop()#返回删除的元素
#5.栈的大小 O(1)
len(stack)
#6.栈是否为空 O(1)
len(stack)==0
#7.栈的遍历 O(N) 边删除边遍历
while len(stack)>0:
temp=stack.pop()
print(temp)哈希表（散列表）
key:value 键值对 python中字典
key->哈希函数->内存地址->key/value放在对应的内存地址
哈希碰撞：两个不同的key通过同一个哈希函数得到同样的内存地址
| 类型 | 时间复杂度 |
|---|---|
| 访问 | 不存在 |
| 搜索 | O(1) 碰撞:O(k)，碰撞元素的个数 |
| 插入 | O(1) |
| 删除 | O(1) |
哈希表常用操作：创建哈希表、添加元素、删除元素、修改元素、获取Key的值、检查key是否存在、哈希表长度、哈希表是否还有元素
练习题：力扣217 389 496
python的哈希表常用操作
#1.创建哈希表
#用数组创建
hashTable=['']*4
#用字典创建
mapping={}
#2.添加元素 O(1)
hashTable[1]='whc'
hashTable[2]='xn'
hashTable[3]='gyj'
mapping[1]='whc'
mapping[2]='xn'
#3.修改元素 O(1) 直接访问对应元素地址
hashTable[1]='bs'
#4.删除元素 O(1)
hashTable[1]=''#数组创建时
mapping.pop(1)#将key为1的键值对直接删除
del mapping[1]
#5.获取元素 O(1)
hashTable[3]
mapping[3]
#6.检查key是否存在 O(1)
3 in mapping#返回true or false
#7.哈希表的长度，判断是否还有元素 O(1)
len(mapping)
len(mapping==0)
