实现基于 list<T[N]> 的动态扩容数组栈
哪些公司问过
量化公司(明泓、佳琪、Avenir、九坤、非凸等)1
答案要点
- 底层为若干定长数组块,栈顶只在最后一块操作
- 维护块链表、末块已用数量和总 size
- 末块满时新建块挂到尾部,不搬移已有元素,地址稳定
- pop 后空块可保留一块备用,避免边界抖动
- 要求容量倍增时,每次扩容新增与现有块数相同的块,总容量翻倍,申请次数为对数级,push 均摊 O(1)
易错点
- 满块时把所有元素搬到新空间,失去分块的意义
- 在块边界反复 push、pop 导致频繁申请释放
- 忘记处理空栈时的 top 与 pop
面试官常见追问
- 为什么不用 vector 直接扩容?
- T[N] 对 T 有什么要求?
- 题目说的“容量倍增”怎么体现?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。