栈和队列
栈和队列的实际实现
双向链表
数组实现
应用一:怎么用数组实现不超过固定大小的栈
ring buffer
pushi, popi, size, limit
用 size 约束了 pushi 和 popi 追赶问题
应用二:实现一个特殊的栈,在基本功能的基础上,再实现返回栈中最小元素的功能
pop push getMin操作的时间复杂度都是O(1)
设计的栈类型可以使用现成的栈结构
- data栈,min栈,同时往里面放,空间换时间,占用空间大,弹出不用做判断
- data栈,min栈,只有新data < min 时才往里放,时间换空间,占用空间更小,但是弹出做判断
应用三:如何用栈结构实现队列结构
两个栈 stackPush 和 stackPop
stackPush 写入 1 2 3 4 5
挨个执行pop操作,导入到 stackPop,5 4 3 2 1
用户返回时,直接返回 stackPop.pop()
要保证2个原则:
- stackPop为空的时候才能导入,用户输入 1 2 3 4 5之后,弹出5,又写个6,此时6不应该进stackPop
- 如果决定导数据到statckPop,一定要一次性的从stackPush导到stackPop导完,别导一半
应用四:如何用栈结构实现队列结构
两个队列data 和 helper
data 写入 1 2 3 4 5
将 1 2 3 4 导入到 helper,留着 5 不导入,给用户弹出返回
下一回,helper变成 data,data变成helper,继续这么干
应用五:图,的宽度遍历使用的队列,深度遍历使用的栈
问,用栈实现图的宽度遍历,用队列实现图的深度遍历,怎么做
用2个栈,拼出一个队列搞宽度
用2个队列,拼出一个栈搞深度
递归的底层实现,依赖系统的栈
递归的时间复杂度
T(N) = a*T(N/b) + O(N ^ d)
哈希表一律按值传递包括String
非基础类型的Key按引用传递,即使Key对象有20G大小,也只会存一个内存地址