企业官网建设流程全解析

第 2 章常用数据结构

2.3 栈

2.3.1 栈的概念

栈（Stack）是一个线性结构，其维护了一个有序的数据列表，列表的一端称为栈顶（top），另一端称为栈底（bottom）。栈对数据的操作有明确限定，插入元素只能从栈顶进行，删除元素也只能栈顶开始逐个进行，通常将插入元素称为入栈（push），删除元素称为出栈（pop）。正是由于上述规定，栈保证了后进先出的原则（LIFO，Last-In-First-Out）。

栈的底层实现既可以选择数组也可以选择链表，只要能保证后进先出的原则即可。

2.3.2 栈的功能定义

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))

``