我有一个抽象的数据类型,可以看作是从左到右存储的列表,具有以下可能的操作:推送:在列表的左端添加一个新项目Pop:删除列表左端的项目Pull :删除列表右端的项目
使用三个堆栈和不断的额外内存来实现它,这样任何push,pop或pull操作的分摊时间都是不变的.堆栈具有基本操作,isEmpty,Push和Pop.
摊销时间的意思是"如果我花费这么长时间,我可以花费另一块时间将其存放在一堆时间中以便以后使用." 对于每次推送操作,花费三个恒定时间块,因此对于每个按下的元素,你有2个额外的恒定时间块.