python必背源代码栈和队列用list实现代码

在 Python 中，内置的列表（list）是一个支持随机访问与动态扩容的底层数组结构。利用 list.append() 与无参数的 list.pop()，可以在 O(1) 均摊时间复杂度下实现后进先出（LIFO）的“栈”；而利用 list.append() 与 list.pop(0)，则可以直观实现先进先出（FIFO）的“队列”，不过头部出队需移动后续全部元素，时间复杂度为 O(n)。本文将给出标准封装源代码、逐行原理解释及操作状态对比。

图 0：基于 Python List 实现栈与队列的结构形态与基本调用关系

一、栈（Stack）的核心原理与 List 源代码实现

栈是一种受限的线性表，遵循“后进先出”（Last In First Out，LIFO）原则。所有元素的插入（入栈）与删除（出栈）都只能发生在同一端，这一端称为“栈顶”（Top），相对的另一端则固定不动，称为“栈底”（Bottom）。

在 Python 中，使用 list 实现栈是最自然、最高效的方式。我们将列表的末尾视作栈顶：调用 list.append(x) 追加元素即入栈；调用不带参数的 list.pop() 弹出末尾元素即出栈。二者都是原地操作，均摊时间复杂度为 O(1)。

1. 栈的面向对象完整源代码

class Stack:
    """基于 Python list 实现的后进先出栈（LIFO）"""
    def __init__(self):
        # 使用空列表作为底层容器
        self._items = []

    def push(self, item):
        """入栈操作：向栈顶追加元素"""
        self._items.append(item)

    def pop(self):
        """出栈操作：移除并返回栈顶元素；若为空栈则抛出 IndexError"""
        if self.is_empty():
            raise IndexError("pop from empty stack: 栈为空，无法执行出栈操作")
        return self._items.pop()

    def peek(self):
        """查看栈顶元素但不弹出"""
        if self.is_empty():
            raise IndexError("peek from empty stack: 栈为空，无栈顶元素")
        return self._items[-1]

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

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

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


# 验证与调用示例
if __name__ == "__main__":
    stack = Stack()
    stack.push(10)
    stack.push(20)
    stack.push(30)
    print("当前栈状态:", stack)
    print("查看栈顶 peek():", stack.peek())
    print("执行出栈 pop():", stack.pop())
    print("出栈后栈状态:", stack)
    print("当前栈大小 size():", stack.size())
    print("栈是否为空 is_empty():", stack.is_empty())

图 1：基于 List 的栈操作流程，push 与 pop 始终在尾部进行，无需挪动其他元素

二、队列（Queue）的核心原理与 List 源代码实现

队列与栈相反，遵循“先进先出”（First In First Out，FIFO）原则。它有两个开口：允许插入数据的一端称为“队尾”（Rear），允许删除数据的一端称为“队首”（Front）。先存入的数据必定先被处理取出，类似日常排队买票。

使用 Python 的 list 实现队列时，标准做法是以列表末尾作为队尾（执行 append(x) 入队），以列表索引 0 处作为队首（执行 pop(0) 出队）。

1. 队列的面向对象完整源代码

class Queue:
    """基于 Python list 实现的先进先出队列（FIFO）"""
    def __init__(self):
        # 内部使用列表存储元素
        self._items = []

    def enqueue(self, item):
        """入队操作：从队尾追加元素，时间复杂度 O(1)"""
        self._items.append(item)

    def dequeue(self):
        """出队操作：从队首弹出元素，时间复杂度 O(n)"""
        if self.is_empty():
            raise IndexError("dequeue from empty queue: 队列为空，无法执行出队操作")
        return self._items.pop(0)

    def peek(self):
        """查看队首元素但不弹出"""
        if self.is_empty():
            raise IndexError("peek from empty queue: 队列为空，无队首元素")
        return self._items[0]

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

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

    def __repr__(self):
        return f"Queue({self._items})"


# 验证与调用示例
if __name__ == "__main__":
    queue = Queue()
    queue.enqueue("任务A")
    queue.enqueue("任务B")
    queue.enqueue("任务C")
    print("当前队列状态:", queue)
    print("查看队首元素 peek():", queue.peek())
    print("执行出队 dequeue():", queue.dequeue())
    print("出队后队列状态:", queue)
    print("当前队列大小 size():", queue.size())
    print("队列是否为空 is_empty():", queue.is_empty())

图 2：队列入队（追加尾部）与出队（弹出首部）在底层数组中的内存变化

三、栈与队列核心操作步骤及代码映射对照

为了让初学者在面试或编码中能够脱口而出、不出差错，这里将栈与队列在实现中的 5 个核心步骤进行了横向对比：

• 步骤 1：容器初始化 —— 内部创建空的动态数组 self._items = []。
• 步骤 2：状态检测与判空 —— 利用 Python 原生语法 len(self._items) == 0 或布尔判断 not self._items，杜绝空容器访问错误。
• 步骤 3：数据存入 —— 栈（push）与队列（enqueue）在存入端完全一致，均使用 self._items.append(item) 追加到末尾。
• 步骤 4：数据查看（Peek） —— 栈查看栈顶取末尾元素 self._items[-1]；队列查看队首取第一项 self._items[0]。
• 步骤 5：数据提取与防御性拦截 —— 栈调用无参 self._items.pop()；队列调用首位弹出 self._items.pop(0)。两者都必须先做 is_empty() 检查，防止抛出未捕获的 IndexError。

图 3：栈与队列核心操作步骤与底层 List 方法详细对照流程

四、时间复杂度分析与工程实践避坑

虽然用 list 实现栈和队列代码非常简洁，但在实际开发和算法面试中，必须清晰认识到它们在时间复杂度上的本质区别：

图 4：技术选型总结路径，明确说明了 list 实现栈与队列的使用边界

五、全文总结

“python必背源代码栈和队列用list实现代码”的核心要点可以概括为两句话：

• 栈的实现：借用 list 尾部，进栈用 append()，出栈用 pop()，两者时间复杂度均为 O(1)，是 Python 中实现栈的标准写法。
• 队列的实现：借用 list 头部出队，进队用 append()，出队用 pop(0)，直观简单；但在处理大规模数据时，需注意 pop(0) 的 O(n) 平移开销，必要时平滑过渡到 collections.deque。