正文

Python中计算stack长度只需使用len函数直接对列表或栈对象求长度即可

/0 浏览量
1008

哎，这话听着挺有道理，但咱得掰开揉碎了聊聊。因为”栈”这东西在Python里其实有好几副面孔，len()到底能用、好用、还是有点小坑，里面门道还挺多的。

先说最最常见的那种——用列表当栈

Python官方文档自己都说了，用列表模拟栈是最自然的做法。append()是入栈，pop()是出栈，这谁不会呢？

# 用列表当栈
stack = []
stack.append(1)
stack.append(2)
stack.append(3)

print(len(stack))  # 输出 3，完美
print(stack.pop()) # 3
print(len(stack))  # 输出 2

这种情况你说得完全没错，len(list)就是O(1)的时间复杂度，Python底层对列表长度有缓存，每次append或pop之后长度值直接更新，根本不重新遍历。所以用列表当栈，len()随便用，放心用。

但问题来了——列表是栈吗？

从数据结构的角度讲，栈是一种”后进先出”（LIFO）的抽象概念。列表确实能实现这个功能，但它同时也能干队列的事、干数组的事、干随便什么都行。所以严格来说，用列表当栈是一种”借鸡下蛋”的做法，它不是真正的栈类型，只是你用栈的方式来用列表而已。

标准库里的真·栈——collections.deque

如果你真的在意”栈”这个概念，Python标准库里有个更合适的选择：collections.deque。

from collections import deque

stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)

print(len(stack))  # 输出 3
print(stack.pop()) # 3
print(len(stack))  # 输出 2

deque是双端队列，但它在这里被我们当作栈来用。它和列表的区别在于——pop操作在deque的左端和右端都是O(1)，而在列表的左端pop是O(n)。虽然当栈用的时候我们只用右端pop，所以性能上两者差别不大，但deque的语义更明确：它就是为高效进出两端设计的。

这里len(deque)也是O(1)，没问题。

那 Queue.LifoQueue 呢？

Python还有一个queue模块，里面的LifoQueue才是真正的线程安全栈。

import queue

stack = queue.LifoQueue()
stack.put(1)
stack.put(2)
stack.put(3)

print(stack.qsize())  # 输出 3，注意！不是len()
print(stack.get())    # 3
print(stack.qsize())  # 输出 2

看到没？这里不能用len()，得用qsize()方法。这是很多初学者容易踩的坑。

LifoQueue是线程安全的，内部用了锁机制来保证并发操作的正确性。正因为它有锁，所以它没有直接暴露内部的容器，也就没有__len__魔术方法。你如果硬写len(stack)，会直接报TypeError: object of type 'LifoQueue' has no len()。

所以回到你的那句话——”计算stack长度只需使用len函数直接对列表或栈对象求长度即可”——这里有个前提：你用的栈对象必须支持len()。LifoQueue就不支持，它用qsize()。

自定义栈类呢？

很多人喜欢自己封装一个Stack类，这时候len()能不能用，完全取决于你有没有实现__len__方法。

class Stack:
    def __init__(self):
        self._items = []
    
    def push(self, item):
        self._items.append(item)
    
    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()
    
    def is_empty(self):
        return len(self._items) == 0
    
    # 关键：实现__len__才能让len()生效
    def __len__(self):
        return len(self._items)
    
    def __repr__(self):
        return f"Stack({self._items!r})"

# 测试
s = Stack()
s.push(10)
s.push(20)
s.push(30)

print(len(s))   # 输出 3，因为实现了__len__
print(s)        # 输出 Stack([10, 20, 30])
print(s.pop())  # 输出 30
print(len(s))   # 输出 2

如果你忘了实现__len__，那len(s)就会报错。所以”只需使用len函数”这句话，隐含的前提是你的栈对象已经正确实现了len协议。

性能层面再聊几句

既然你是专家角色，咱就得深入一点。len()为什么快？

Python的list内部维护了一个ob_size字段，每次增删元素时都会更新这个值。所以len(list)本质上就是读一个整数，时间复杂度O(1)。

deque也一样，它内部也维护了长度计数，len(deque)同样是O(1)。

但LifoQueue为什么没有len()？因为它的内部数据结构可能被多个线程同时修改，直接读长度会有竞态条件。qsize()方法加了锁，保证读到的是一致的值。代价是qsize()比len()慢一点，但在多线程场景下这是必要的。

import time
from collections import deque
import queue

# 性能对比
d = deque(range(1000000))
q = queue.LifoQueue()
for i in range(1000000):
    q.put(i)

start = time.time()
for _ in range(100000):
    len(d)
print(f"len(deque) 10万次: {time.time() - start:.4f}s")

start = time.time()
for _ in range(100000):
    q.qsize()
print(f"q.qsize() 10万次: {time.time() - start:.4f}s")

一般结果会是deque的len()明显快于LifoQueue的qsize()，因为前者无锁，后者有锁。

实际开发中的建议

  1. 单机单线程场景：用列表或deque都行，len()随便用，推荐deque因为语义更清晰
  2. 多线程场景：用LifoQueue，但记住用qsize()而不是len()
  3. 自定义类：务必实现__len__，这样用户才能用len()，符合Python惯例
  4. 检查空栈：推荐用if not stack:而不是if len(stack) == 0:，前者更Pythonic，也适用于所有实现了__bool__或__len__的对象
# 更Pythonic的写法
stack = []
if not stack:          # 推荐
    print("empty")

if len(stack) == 0:    # 能用，但不够优雅
    print("empty")

一句话总结

你的说法在大多数情况下是对的——用列表或deque当栈时，len()确实简单好用。但要注意LifoQueue这种线程安全的栈对象用的是qsize()，自定义栈类得自己实现__len__。所以”只需使用len函数”这句话，得加上”前提是对象支持len()“这个限定条件才严谨。

Python的世界里，没有银弹，只有合适的工具。len()是个好工具，但它不是万能的。

-- 展开阅读全文 --