如何用Python实现栈和队列？

使用列表实现栈高效，因append和pop操作均为O(1)；但用列表实现队列时，pop(0)为O(n)，性能差。应使用collections.deque实现队列，因其popleft为O(1)。封装类可提供更清晰接口和错误处理，适用于复杂场景。频繁出队或大数据量时优选deque，简单栈操作可选list。

在Python中实现栈（Stack）和队列（Queue）有几种常见且有效的方法，最直接的方式是利用Python内置的列表（list）或collections模块中的deque（双端队列）。这两种数据结构本身就具备了实现栈和队列所需的基本操作，只是在性能表现上各有侧重。

解决方案

实现栈（LIFO，后进先出）和队列（FIFO，先进先出）的核心在于控制元素的添加和移除顺序。

1. 使用Python列表实现栈

Python的list天生就非常适合作为栈。append()方法可以将元素添加到列表的末尾，而pop()方法则默认从列表末尾移除元素。这完美符合栈的LIFO特性。

# 栈的实现示例
stack = []

# 入栈 (Push)
stack.append('A')
stack.append('B')
stack.append('C')
print(f"入栈后: {stack}") # 输出: ['A', 'B', 'C']

# 出栈 (Pop)
item_c = stack.pop()
print(f"出栈 {item_c} 后: {stack}") # 输出: ['A', 'B']

item_b = stack.pop()
print(f"出栈 {item_b} 后: {stack}") # 输出: ['A']

# 查看栈顶元素 (Peek)
if stack:
    print(f"栈顶元素: {stack[-1]}") # 输出: 'A'

# 检查栈是否为空
print(f"栈是否为空: {not stack}") # 输出: False

2. 使用collections.deque实现队列

虽然列表也可以实现队列，但它在从列表头部移除元素时效率较低（list.pop(0)是O(n)操作）。这时，collections.deque（双端队列）就显得尤为出色了。deque支持在两端高效地添加和移除元素，其性能是O(1)。

from collections import deque

# 队列的实现示例
queue = deque()

# 入队 (Enqueue)
queue.append('Task1')
queue.append('Task2')
queue.append('Task3')
print(f"入队后: {queue}") # 输出: deque(['Task1', 'Task2', 'Task3'])

# 出队 (Dequeue)
task1 = queue.popleft() # 从左端移除
print(f"出队 {task1} 后: {queue}") # 输出: deque(['Task2', 'Task3'])

task2 = queue.popleft()
print(f"出队 {task2} 后: {queue}") # 输出: deque(['Task3'])

# 查看队首元素 (Peek)
if queue:
    print(f"队首元素: {queue[0]}") # 输出: 'Task3'

# 检查队列是否为空
print(f"队列是否为空: {not queue}") # 输出: False

Python内置列表作为栈和队列的性能瓶颈是什么？

说实话，用Python的内置list来模拟栈，也就是只用append()和pop()操作，效率是相当高的，这两种操作的时间复杂度都是O(1)。这意味着无论栈里有多少元素，添加或移除一个元素所需的时间基本是恒定的。所以，对于栈来说，list几乎没有性能瓶颈，非常适合。

但当list被用作队列时，情况就有点不一样了。队列的特性是先进先出，这意味着我们需要从列表的“头部”移除元素。如果你用list.pop(0)来模拟出队操作，那问题就来了。pop(0)这个操作，每次都会把列表中所有剩余的元素向前移动一位，以填补被移除元素留下的空位。想象一下，如果你的列表里有几百万个元素，每次出队都要移动几百万个元素，这无疑是个巨大的开销。它的时间复杂度是O(n)，n是列表中元素的数量。随着队列的增长，性能会急剧下降，这在处理大量数据或高并发场景下是完全不可接受的。我个人就遇到过一些老项目，为了方便直接用list.pop(0)做队列，结果在生产环境跑起来就发现CPU占用居高不下，一查才发现是这里出了问题。所以，对于队列操作，尤其是频繁出队的情况，我强烈建议避免使用list.pop(0)。

除了内置类型，如何用类封装栈和队列，实现更清晰的接口和错误处理？

虽然直接使用list或deque很方便，但在更复杂的应用场景中，我们往往希望拥有更清晰、更具表达力的接口，并且能够处理一些边界情况，比如从空栈或空队列中取出元素。这时候，将栈和队列封装成独立的类就显得很有必要了。这样做不仅能提供更语义化的方法名（比如push、pop、enqueue、dequeue），还能在内部隐藏实现细节，并加入自定义的错误处理逻辑。

下面是两个简单的类封装示例：

class MyStack:
    def __init__(self):
        # 内部使用列表存储栈元素
        self._items = []

    def push(self, item):
        """元素入栈"""
        self._items.append(item)

    def pop(self):
        """元素出栈，如果栈为空则抛出错误"""
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        """查看栈顶元素，不移除"""
        if not self._items:
            raise IndexError("peek from empty stack")
        return self._items[-1]

    def is_empty(self):
        """判断栈是否为空"""
        return not self._items

    def size(self):
        """返回栈中元素数量"""
        return len(self._items)

    def __str__(self):
        return f"Stack({self._items})"

    def __repr__(self):
        return self.__str__()

# 使用自定义栈
s = MyStack()
s.push(10)
s.push(20)
print(f"我的栈: {s}")
print(f"栈顶元素: {s.peek()}")
print(f"出栈: {s.pop()}")
print(f"栈是否为空: {s.is_empty()}")
print(f"栈大小: {s.size()}")
# s.pop()
# s.pop() # 再次pop会引发IndexError


from collections import deque

class MyQueue:
    def __init__(self):
        # 内部使用collections.deque存储队列元素，保证高效性
        self._items = deque()

    def enqueue(self, item):
        """元素入队"""
        self._items.append(item)

    def dequeue(self):
        """元素出队，如果队列为空则抛出错误"""
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()

    def peek(self):
        """查看队首元素，不移除"""
        if not self._items:
            raise IndexError("peek from empty queue")
        return self._items[0]

    def is_empty(self):
        """判断队列是否为空"""
        return not self._items

    def size(self):
        """返回队列中元素数量"""
        return len(self._items)

    def __str__(self):
        return f"Queue({list(self._items)})" # 转换为列表方便打印

    def __repr__(self):
        return self.__str__()

# 使用自定义队列
q = MyQueue()
q.enqueue('JobA')
q.enqueue('JobB')
print(f"我的队列: {q}")
print(f"队首元素: {q.peek()}")
print(f"出队: {q.dequeue()}")
print(f"队列是否为空: {q.is_empty()}")
print(f"队列大小: {q.size()}")
# q.dequeue()
# q.dequeue() # 再次dequeue会引发IndexError

通过类封装，我们不仅拥有了更直观的API，还可以在方法内部加入各种逻辑，比如在pop()或dequeue()之前检查是否为空，从而避免运行时错误，或者记录操作日志，甚至可以扩展成线程安全的版本。这让代码更健壮，也更易于维护和理解。

什么时候应该选择collections.deque而不是普通列表来模拟栈和队列？

这是一个很实际的问题，选择哪种数据结构确实需要根据具体场景来定。在我看来，collections.deque和普通列表各有其最佳使用场景，没有绝对的优劣，关键在于“合适”。

选择collections.deque的场景：

1. 作为队列使用时，特别是需要频繁从头部移除元素： 这是deque最主要的优势。正如前面提到的，list.pop(0)的O(n)性能在处理大量数据时会成为瓶颈，而deque.popleft()是O(1)。如果你在实现广度优先搜索（BFS）、任务调度器、日志处理队列等需要频繁“出队”的场景，那么deque几乎是唯一的选择。
2. 作为双端队列使用时： 如果你的需求不仅是栈或队列，而是需要在两端都进行高效的添加和移除操作，比如实现一个历史记录功能，既能添加新记录，又能回溯旧记录，deque的append(), appendleft(), pop(), popleft()都能提供O(1)的性能。
3. 对性能有严格要求，且数据量可能很大： 当你的程序需要处理大量数据，并且对响应时间有较高要求时，deque的恒定时间复杂度优势就非常明显了。它避免了列表在中间或头部操作时可能出现的元素复制和移动开销。
4. 需要固定大小的循环缓冲区： deque有一个maxlen参数，可以创建一个固定大小的双端队列。当队列满时，再添加新元素会自动从另一端移除最老的元素。这对于实现滑动窗口、最近访问列表等功能非常方便，省去了手动管理大小的麻烦。

选择普通列表（list）的场景：

1. 作为栈使用时： 如果你仅仅是需要一个栈，只在列表的末尾进行append()和pop()操作，那么普通列表完全够用，而且其实现也更简洁直观。在这种情况下，list和deque的性能差异可以忽略不计。
2. 数据量较小，且对性能要求不那么极致： 对于小规模数据，即使偶尔有list.pop(0)这样的O(n)操作，其影响也可能微乎其微。代码的简洁性和可读性有时比极致性能更重要。
3. 需要频繁随机访问元素： 列表支持通过索引进行O(1)的随机访问（my_list[index]），而deque虽然也支持索引访问，但在内部实现上，它的随机访问效率不如列表。如果你除了栈/队列操作外，还需要频繁地根据索引访问中间元素，那么列表可能更合适。

总的来说，当涉及到队列操作，尤其是需要从头部移除元素时，collections.deque是Pythonic且高效的选择。而如果只是简单的栈操作，或者数据量不大且需要随机访问，那么列表的简洁性也很有吸引力。理解它们底层的工作原理和时间复杂度，能帮助我们做出更明智的技术决策。