欢迎访问宙启技术站
智能推送

用Python实现栈的数据结构。

发布时间:2023-12-04 13:49:24

栈(Stack)是一种具有以下特点的数据结构:先进后出(FILO,即先进入栈的元素最后出栈),后进先出(LIFO,即后进入栈的元素最先出栈)。栈通常具有两个基本操作:入栈(Push)和出栈(Pop)。

下面是使用Python实现栈的一个例子:

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

    def is_empty(self):
        return self.items == []

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

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

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

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

在上述代码中,我们使用一个列表来存储栈的元素。is_empty方法用于判断栈是否为空,如果栈为空,返回True,否则返回Falsepush方法用于将元素入栈,即将元素添加到列表末尾。pop方法用于从栈中弹出元素,即删除并返回列表末尾的元素。peek方法用于返回栈顶的元素,但不移除它。size方法用于返回栈的元素数量。

下面是一个使用栈的例子,计算字符串中的括号是否匹配:

def is_balanced(expression):
    stack = Stack()
    opening_brackets = ['(', '[', '{']
    closing_brackets = [')', ']', '}']

    for char in expression:
        if char in opening_brackets:
            stack.push(char)
        elif char in closing_brackets:
            if stack.is_empty() or opening_brackets.index(stack.pop()) != closing_brackets.index(char):
                return False

    return stack.is_empty()

expression1 = "((2 + 3) * 5)"
expression2 = "(((5) * 3 + 2) / 2]"
expression3 = "{[5 * (4 + 3)]}"

print(is_balanced(expression1))  # True
print(is_balanced(expression2))  # False
print(is_balanced(expression3))  # True

在上述代码中,我们定义了一个is_balanced函数,该函数接收一个表达式作为参数。函数中使用了一个栈来判断表达式中的括号是否匹配。如果表达式中的括号匹配,则返回True,否则返回False

运行上述代码,输出结果分别为True、False和True,说明代码正确地判断了表达式中括号的匹配情况。

这只是栈数据结构在Python中的一个简单应用场景,栈还有许多其他用途。在实际开发中,栈常常作为一个重要的工具在算法和数据处理中使用,例如解析表达式、递归函数、深度优先搜索等。