博客

详解Python 栈（后进先出）

  • Post category:Python

Python 栈（stack）是一种后进先出（LIFO）的数据结构，意味着最后一个添加到栈中的元素是第一个被移除的。在 Python 中，我们可以使用内置的 list 列表类型来实现栈的相关操作。

以下是 Python 栈的使用方法：

创建一个栈

在 Python 中，我们可以通过创建一个空列表来作为一个栈。例如，我们可以使用以下代码创建一个栈：

stack = []

添加元素至栈顶

要将一个元素添加到栈中，我们可以使用 list 类型的 append() 方法将其添加到列表末尾。例如，我们将数字 1 和 2 添加到栈中：

stack = []
stack.append(1)
stack.append(2)
print(stack)  # 输出 [1, 2]

移除栈顶元素

要移除栈顶元素，我们可以使用 list 类型的 pop() 方法。默认情况下，pop() 方法移除并返回列表中的最后一个元素，因此这正好符合栈的行为。例如，我们将栈顶元素移除并返回它：

stack = [1, 2]
top = stack.pop()
print(top)    # 输出 2
print(stack)  # 输出 [1]

查看栈顶元素

要查看栈顶元素，我们可以使用 list 类型的索引运算符 [] 。例如，我们可以查看栈顶元素：

stack = [1, 2]
top = stack[-1]
print(top)  # 输出 2

检查栈是否为空

要检查栈是否为空，我们可以使用 list 类型的 __bool__() 魔术方法检查栈的长度是否为 0。例如，我们可以判断栈是否为空：

stack = []
if not stack:
    print("栈为空")
else:
    print("栈不为空")

示例

现在，我将使用两个示例来说明栈的使用方法。

第一个示例是使用栈反转一个字符串。实现方法是将字符串中的每个字符压入栈中，然后逐个弹出并连接起来，这样就能够反转字符串。

def reverse_string(string):
    stack = []
    for s in string:
        stack.append(s)
    result = ""
    while stack:
        result += stack.pop()
    return result

print(reverse_string("Hello, world!"))  # 输出 !dlrow ,olleH

第二个示例是使用栈来检查括号是否匹配。实现方法是将每个左括号压入栈中，遇到对应的右括号时从栈中弹出一个左括号。如果左括号与当前右括号匹配，则继续处理；否则，括号不匹配，直接返回 False。

def is_valid_parentheses(string):
    stack = []
    for s in string:
        if s in "([{":
            stack.append(s)
        elif s in ")]}":
            if not stack:
                return False
            if (s == ")" and stack[-1] == "(") or (s == "]" and stack[-1] == "[") or (s == "}" and stack[-1] == "{"):
                stack.pop()
            else:
                return False
    return not stack

print(is_valid_parentheses("()[]{}"))      # 输出 True
print(is_valid_parentheses("(]"))          # 输出 False
print(is_valid_parentheses("([)]"))        # 输出 False
print(is_valid_parentheses("{[()]}"))      # 输出 True
Tags: