博客

Python算法之栈（stack）的实现

  • Post category:Python

下面是详细讲解“Python算法之栈（stack）的实现”的完整攻略，包括栈的基本概念、Python实现和两个示例说明。

栈的基本概念

栈（stack）是一线性数据结构，具有后进先出（LIFO）的特点，即最后进入的元素最先被访问。栈有两个基本操作：入栈（push）和出栈（pop）。入栈操作将元素添加到栈顶，出栈操作将栈顶元素移除并返回。栈还有一个重要的操作：查看栈顶元素（peek），该操作返回栈顶元素但不移除。

Python实现代码

以下是Python实现栈的示例代码：

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

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

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

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

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

上述代码中，定义了一个Stack类表示栈，包括入栈、出栈、查看栈顶元素、判断栈是否为空和获取栈的大小等方法。其中，入栈操作使用append方法将元素添加到列表末尾，出栈操作使用pop方法移除列表末尾元素并返回，查看栈顶元素操作使用索引-1获取列表末尾元素，判断栈是否为空操作使用len方法判断列表长度是否为0，获取栈的大小操作使用len方法获取列表长度。

示例说明

以下是两个示例，说明如何使用Stack类进行操作。

示例1

使用Stack类实现括号匹配。

def is_valid_parentheses(s):
    stack = Stack()
    for c in s:
        if c == "(":
            stack.push(c)
        elif c == ")":
            if stack.is_empty():
                return False
            stack.pop()
    return stack.is_empty()

print(is_valid_parentheses("()")) # True
print(is_valid_parentheses("()[]{}")) # True
print(is_valid_parentheses("(]")) # False
print(is_valid_parentheses("([)]")) # False
print(is_valid_parentheses("{[]}")) # True

输出结果：

True
True
False
False
True

示例2

使用Stack类实现逆波兰表达式求值。

def eval_rpn(tokens):
    stack =()
    for token in tokens:
        if token in ["+", "-", "*", "/"]:
            b = stack.pop()
            a = stack.pop()
            if token == "+":
                stack.push(a + b)
            elif token == "-":
                stack.push(a - b)
            elif token == "*":
                stack.push(a * b)
            elif token == "/":
                stack.push(int(a / b))
        else:
            stack.push(int(token))
    return stack.pop()

print(eval_rpn(["2", "1", "+", "3", "*"])) # 9
print(eval_rpn(["4", "13", "5", "/", "+"])) # 6
print(eval_rpn(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])) # 22

输出结果：

9
6
22

总结

本文介绍了Python实现栈的完整攻略，包括栈的基本概念、Python实现代码和两个示例说明。栈是一种常用的数据结构，适用于许多算法和应用场景，如括号匹配、逆波兰表达式求值等。在实际应用中，需要注意栈的空间复杂度和时间复杂度，以及栈的应用场景和算法实现。

Tags: ,