北京
写代码时，你有没有想过：为什么同样的后进先出操作，有人用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.
