- 学习《Python Data Structure》3.10 - 3.24
Tech
队列
- FIFO,先进先出的有序集合
- 添加项的一端是队尾,删除项的一端是队首
Queue()
enqueue()
dequeue()
size()
is_empty()
- 约瑟夫问题,有n个人,按m报数,第m个人自杀,直到最后一个
打印机队列
- 有1台打印机每分钟打印k张纸,n个学生每个学生创建任务页数1-20页
- 打印机的任务队列,每个任务都有时间戳(用于标记任务创建的时间,最后用于计算任务开始的时候离创建的时候花费了多久)
- 每秒:
- 是否创建新的打印任务(通过一个随机函数来判断),若是,将任务添加到任务队列中
- 若打印机不忙,并且有任务在队列中
- 从打印机队列中删除一个任务,并将其分配给打印机
- 从当前时间减去创建时间,获得当前任务的等待时间
- 将等待时间添加到时间等待列表中,一共后续计算
- 根据打印任务的页数,计算打印机打印完这个任务需要多少时间
- 打印机需要1秒打印,需要从等待时间中减去一秒
- 若任务完成,所需时间已经达到零,打印机空闲
- 模拟完成后,从生成的等待时间列表中计算平均等待时间。
Deque
- 双向队列
Deque()
add_front(item)
add_rear(item)
remove_front()
remove_rear()
is_empty()
size()
回文检查
- 头尾相同的字符串,例如:rtotr, abba
- 用deque来做,存的时候
add_front()
, 取的时候remove_front()
,remove_rear()
比较即可
无序列表
List()
add(item)
remove(item)
search(item)
is_empty()
size()
append(item)
index(item)
insert(pos, item)
pop()
pop(pos)
链表
- 没有next节点的节点称为“接地节点”
有序列表
OrderList()