写代码时,你有没有想过:为什么同样的后进先出操作,有人用list,有人非要用deque?
栈(stack)是最基础的数据结构之一。它的规则很简单:最后放进去的元素,最先被拿出来。这种LIFO(后进先出)特性,让栈在撤销操作、函数调用、表达式求值等场景里无处不在。
![]()
一个标准栈支持三种操作:插入(push)、查看栈顶(peek)、删除(pop)。理想情况下,这三个操作都应该是O(1)时间复杂度——常数时间,与数据量无关。
![]()
Python里最常见的做法是用list。代码直观:append()模拟入栈,pop()模拟出栈,stack[-1]直接取栈顶。看起来一切完美,但list有个隐藏成本。
list的插入复杂度标注为"O(1)均摊"。这个"均摊"很关键。当list内部数组填满时,Python需要申请一块更大的内存,把所有元素搬过去。虽然通过倍增策略让这种搬家极少发生,但它确实存在。对于需要极致性能的场景,这是个隐患。
deque(双端队列)是更干净的选择。它基于链表实现,append()和pop()都是严格的O(1),没有均摊的 asterisk。从collections导入deque,代码几乎和list一样简洁,但时间表现更稳定。
![]()
实际测试一下:stack = [1, 7, 5, 6, 5, 12, 4],pop()移除4,peek看到12,append(30)压入新值。换成deque,逻辑完全一致,只是底层少了内存重分配的担忧。
选list还是deque?大多数场景下差别不大。但如果你在处理高频操作、或者对延迟极度敏感,deque的确定性性能更值得信任。这不是优化焦虑,而是理解工具背后的权衡。
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.