本文共 2737 字，大约阅读时间需要 9 分钟。

Python实现栈

栈的概念

栈（Stack），也称为后入先出（Last-In-First-Out，LIFO），是一种线性数据结构。栈支持在单个端点进行操作，常见操作包括：将元素推入栈顶（Push）、从栈顶取出元素（Pop）、查看栈顶元素（Peek）以及检查栈是否为空（Empty）。

栈的实现

为了实现栈，可以将其基于数组或列表来模拟。最常见的实现方法是利用列表的 append 和 pop 方法。具体实现步骤如下：

初始化一个空列表，这个列表将用来存储栈中的元素。

当元素需要被推入栈时，使用 append 方法将该元素添加到列表末尾。

当需要从栈中取出元素时，使用 pop 方法从列表末尾取出元素。

查看栈顶元素时，访问列表最后一个元素的索引。

判断栈是否为空时，检查列表的长度是否为0。

Python栈实现示例代码

class Stack:
    def __init__(self):
        self.items = []
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        return self.items.pop()
    
    def peek(self):
        if self.items:
            return self.items[-1]
        return None

基本操作演示

以下是一些基本的栈操作演示：

stack = Stack()
stack.push("M")  # 栈现在：["M"]
stack.push("a")  # 栈现在：["M", "a"]
stack.push("j")  # 栈现在：["M", "a", "j"]
stack.push("o")  # 栈现在：["M", "a", "j", "o"]
stack.push("r")  # 栈现在：["M", "a", "j", "o", "r"]
# 查看栈大小
print(stack.size())  # 5
# 查看栈顶元素
print(stack.peek())  # r
# 从栈中取出元素
print(stack.pop())  # 栈现在：["M", "a", "j", "o"]
print(stack.pop())  # 栈现在：["M", "a", "j"]
print(stack.pop())  # 栈现在：["M", "a"]

练习三部曲

第一部分：基本结构构建

编写一个简单的栈类，包含以下基本操作：

• 初始化栈：无需额外参数，使用 default 初始化即可。
• 返回栈大小：通过列表长度获取。
• 判断栈是否为空：比较列表长度是否为0。
• 将元素推入栈。
• 从栈中取出元素。
• 查看栈顶元素（未取出时）。

class Stack:
    def __init__(self):
        self.items = []
    
    def size(self):
        return len(self.items)
    
    def is_empty(self):
        return len(self.items) == 0
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if self.items:
            return self.items.pop()
        else:
            raise ValueError("栈为空，无法弹出元素")
    
    def peek(self):
        return self.items[-1] if self.items else None

第二部分：实现详细功能扩展

在基础实现的基础上，进一步实现以下功能：

• 退出栈：完全清空所有元素。
• 判断栈是否包含指定元素。 -bilir.propTypes = { children: React.ReactNode };

优化后的代码示例

class Stack:
    def __init__(self):
        self.items = []
    
    def __str__(self):
        return f"Stack({self.items})"
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)
    
    def push(self, elem):
        self.items.append(elem)
    
    def pop(self):
        if self.items:
            return self.items.pop()
        else:
            raise ValueError("栈为空，无法弹出元素")
    
    def peek(self):
        return self.items[-1] if self.items else None

最后练习

在完成基本实现后，可以尝试手动编写一个栈类，并对其核心功能进行单元测试。例如：

# 栈初始化
stack = Stack()
# 推入多个元素
stack.push("A")
stack.push("B")
stack.push("C")
# 查看栈顶元素
print(stack.peek())  # 输出 "C"
# 弹出元素
print(stack.pop())  # 输出 "C"
print(stack.peek())  # 输出 "B"
# 栈当前状态：["A", "B"]`

总结

通过以上练习可以掌握栈的基本操作和实现方法。即使在较小的项目中，熟练掌握栈的使用也是非常有帮助的。