说双栈之前先说一下我愚钝的做法,链表实现最小值存储,后面发现最小栈与我这个十分相似
实现思想
进栈时:创建一个最小值链表,每次push元素的时候,和之前的最小值比较(当然,第一次push的就是最小的),与之前的最小值比较,小则头插最小值链表,大则执行下一步
退栈时:每次pop时检测退栈的元素是否和链表头最小的元素相等,如果相等链表头元素也删除,这保证了链表头元素一定在栈实时的元素中是最小的
1 | package stack; |
双栈结构
思想:与链表的思想相同,只是结构不同
1 | import java.util.Stack; |