第 2 章常用数据结构2.3 栈2.3.1 栈的概念栈Stack是一个线性结构其维护了一个有序的数据列表列表的一端称为栈顶top另一端称为栈底bottom。栈对数据的操作有明确限定插入元素只能从栈顶进行删除元素也只能栈顶开始逐个进行通常将插入元素称为入栈push删除元素称为出栈pop。正是由于上述规定栈保证了后进先出的原则LIFOLast-In-First-Out。栈的底层实现既可以选择数组也可以选择链表只要能保证后进先出的原则即可。2.3.2 栈的功能定义方法说明size()返回栈中元素个数is_empty()判断栈是否为空push(item)将新元素压入栈中pop()获取栈顶元素并将栈顶元素弹出栈peek()获取栈顶元素但不弹出栈2.3.3栈的实现使用动态数组实现一个栈。class Stack: def __init__(self): 初始化栈 self.__size 0 self.__items [] property def size(self): 获取栈元素个数 return self.__size def is_empty(self): 判断栈是否为空 return self.__size 0 def push(self, item): 入栈 self.__items.append(item) self.__size 1 def pop(self): 出栈 if self.is_empty(): raise Exception(栈为空) item self.__items[self.__size - 1] del self.__items[self.__size - 1] self.__size - 1 return item def peek(self): 访问栈顶元素 if self.is_empty(): raise Exception(栈为空) return self.__items[self.__size - 1]2.3.4栈的应用1 有效括号力扣20题https://leetcode.cn/problems/valid-parentheses/description/题目描述给定一个只包括“(”“)”“[”“]”“{”“}”的字符串s判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。示例示例 1输入s “()”输出true示例 2输入s “()[]{}”输出true示例 3输入s “(]”输出false示例 4输入s “([])”输出true思路分析遇到左括号则入栈遇到右括号则出栈一个左括号与之匹配如果能够匹配则继续如果匹配失败或者栈为空则返回False。代码实现class Solution: def isValid(self, s): stack [] for i in s: match i: case ( | [ | {: stack.append(i) case ): # 拿出栈顶元素 if (not stack) or (stack.pop() ! (): return False case ]: if (not stack) or (stack.pop() ! [): return False case }: if (not stack) or (stack.pop() ! {): return False # 空列表返回True return True if not stack else False if __name__ __main__: solution Solution() s ()[]{} print(s, solution.isValid(s)) s (] print(s, solution.isValid(s)) s ([)] print(s, solution.isValid(s)) s {[]} print(s, solution.isValid(s))