使用Python构建栈和队列：从基础列表到双端队列优化

栈和队列是计算机科学中最基础的数据结构之一，广泛应用于算法设计、内存管理、任务调度等场景。Python 提供了多种方式来实现这两种结构，既可以直接使用内置的 list，也可以借助标准库中的高效容器。

栈的实现：基于后进先出原则

栈（Stack）遵循"后进先出"（LIFO, Last In First Out）的原则，所有操作都在同一端——即栈顶进行。Python 的 list 天然支持在末尾添加和删除元素，因此非常适合用来模拟栈行为。

以下是封装后的栈类实现：

class Stack:
    def __init__(self):
        self._data = []

    def push(self, value):
        """将元素压入栈顶"""
        self._data.append(value)

    def pop(self):
        """弹出栈顶元素，若栈为空则返回 None"""
        return self._data.pop() if not self.is_empty() else None

    def top(self):
        """查看栈顶元素但不移除"""
        return self._data[-1] if not self.is_empty() else None

    def is_empty(self):
        """判断栈是否为空"""
        return len(self._data) == 0

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

# 使用示例
s = Stack()
s.push("first")
s.push("second")
print(s.top())       # 输出: second
print(s.pop())       # 输出: second
print(s.depth())     # 输出: 1

该实现利用了 list.append() 和 list.pop() 在尾部操作均为 O(1) 时间复杂度的优势，性能良好。

队列的基础实现及其局限性

队列（Queue）遵循"先进先出"（FIFO, First In First Out）规则，插入操作在尾部（入队），删除操作在头部（出队）。虽然可以使用 list 实现队列，但在头部执行 pop(0) 操作需要移动后续所有元素，时间复杂度为 O(n)，效率较低。

class NaiveQueue:
    def __init__(self):
        self._elements = []

    def enqueue(self, item):
        self._elements.append(item)

    def dequeue(self):
        return self._elements.pop(0) if not self.is_empty() else None

    def is_empty(self):
        return len(self._elements) == 0

    def length(self):
        return len(self._elements)

这种实现方式适用于小规模数据或教学演示，但在高频率出入队场景下应避免使用。

高性能队列：使用 deque 进行优化

为了获得高效的队列操作，推荐使用 collections.deque，它是一个双向队列，支持在两端以 O(1) 时间复杂度进行添加和删除操作。

from collections import deque

class EfficientQueue:
    def __init__(self):
        self._queue = deque()

    def enqueue(self, element):
        """向队尾添加元素"""
        self._queue.append(element)

    def dequeue(self):
        """从队首移除并返回元素"""
        return self._queue.popleft() if not self.is_empty() else None

    def front(self):
        """查看队首元素但不移除"""
        return self._queue[0] if not self.is_empty() else None

    def is_empty(self):
        """检查队列是否为空"""
        return len(self._queue) == 0

    def size(self):
        """获取队列长度"""
        return len(self._queue)

# 使用示例
q = EfficientQueue()
q.enqueue("task1")
q.enqueue("task2")
print(q.dequeue())   # 输出: task1
print(q.front())     # 输出: task2
print(q.size())      # 输出: 1

通过使用 deque，我们实现了真正高效的 FIFO 队列，特别适合用于广度优先搜索（BFS）、消息缓冲、线程间通信等对性能要求较高的场景。