用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,否则返回False。push方法用于将元素入栈,即将元素添加到列表末尾。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中的一个简单应用场景,栈还有许多其他用途。在实际开发中,栈常常作为一个重要的工具在算法和数据处理中使用,例如解析表达式、递归函数、深度优先搜索等。
