Python中栈的概念和使用

栈（Stack）是一种常见的数据结构，广泛应用于计算机科学和编程中。在 Python 中，栈的操作十分灵活且易于实现。本篇文章将详细介绍栈的概念、特点及其在 Python 中的实现和使用，配以代码示例和图解，帮助你轻松掌握栈的基础知识。

一、栈的概念

1. 栈的定义

栈是一种后进先出（LIFO，Last In First Out）的数据结构。这意味着，最后存入栈的元素最先被取出。

2. 栈的基本操作

栈支持以下核心操作：

• 压栈（Push）：将一个元素放入栈中。
• 弹栈（Pop）：移除并返回栈顶的元素。
• 查看栈顶（Peek/Top）：查看栈顶元素但不移除。
• 判断栈空（IsEmpty）：检查栈是否为空。

二、栈的实现方式

在 Python 中，我们可以使用以下方式实现栈：

1. 列表（list）：利用 Python 的内置列表模拟栈。
2. collections.deque：双端队列更适合作为栈。
3. 自定义类：通过封装实现栈的功能。

1. 使用列表实现栈

# 栈的实现
stack = []

# 压栈
stack.append(1)
stack.append(2)
stack.append(3)
print("栈的状态：", stack)  # 输出：[1, 2, 3]

# 弹栈
top_element = stack.pop()
print("弹出的元素：", top_element)  # 输出：3
print("栈的状态：", stack)        # 输出：[1, 2]

# 查看栈顶元素
if stack:
    print("栈顶元素：", stack[-1])  # 输出：2
else:
    print("栈为空")

图解：

1. 压栈操作：

   • 初始状态：[]
   • append(1) 后：[1]
   • append(2) 后：[1, 2]
   • append(3) 后：[1, 2, 3]

2. 弹栈操作：

   • pop() 移除栈顶元素 3，剩余 [1, 2]。

2. 使用 collections.deque 实现栈

deque 是双端队列，比列表在栈操作中更高效。

from collections import deque

# 使用 deque 实现栈
stack = deque()

# 压栈
stack.append(1)
stack.append(2)
stack.append(3)
print("栈的状态：", stack)  # 输出：deque([1, 2, 3])

# 弹栈
top_element = stack.pop()
print("弹出的元素：", top_element)  # 输出：3
print("栈的状态：", stack)         # 输出：deque([1, 2])

3. 自定义栈类

通过面向对象的方式封装栈操作。

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

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            raise IndexError("弹栈失败，栈为空")

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            return None

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

    def size(self):
        return len(self.stack)

# 测试自定义栈类
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print("栈顶元素：", stack.peek())  # 输出：3
print("弹出元素：", stack.pop())   # 输出：3
print("栈是否为空：", stack.is_empty())  # 输出：False

三、栈的应用场景

1. 括号匹配

栈常用于检查括号是否成对出现。

示例代码：

def is_valid_parentheses(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

# 测试
print(is_valid_parentheses("()[]{}"))  # 输出：True
print(is_valid_parentheses("(]"))      # 输出：False

2. 栈实现表达式求值

栈可以用于后缀表达式（逆波兰表达式）的求值。

示例代码：

def eval_rpn(tokens):
    stack = []
    for token in tokens:
        if token.isdigit() or (token[0] == '-' and len(token) > 1):  # 操作数
            stack.append(int(token))
        else:  # 操作符
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(int(a / b))  # Python 中整除
    return stack[0]

# 测试
expression = ["2", "1", "+", "3", "*"]  # 表示 (2 + 1) * 3
print(eval_rpn(expression))  # 输出：9

四、总结

1. 栈的特点：后进先出，适合管理具有层级关系的数据。

2. 实现方式：

   • 使用 Python 列表（简单、灵活）。
   • 使用 deque（性能更优）。
   • 自定义栈类（更清晰的逻辑封装）。

3. 常见应用：

   • 括号匹配
   • 表达式求值
   • 深度优先搜索等。

掌握栈的基本操作和实际应用，将为你在算法与数据结构学习中打下坚实基础！