打牢地基-栈篇
- 2020 年 4 月 8 日
- 筆記
章节
- 栈的特性 & 图示
- 栈的应用场景
- 构建一个栈
- 使用栈结构解决leetcode相关问题
1. 栈的特性 & 图示
栈是一种线性结构 相比数据，栈对应的操作是数组的子集 只能从一端add元素、get元素，这一端一般称之为栈顶 LIFO 后进先出
2. 栈的应用场景
2.1 undo 操作
比如撤销 "不法" 的输入操作
2.2 程序调用的系统栈
3. 构建一个栈
stack 基本操作包含以下5个操作api:
void push(obj) -> 入栈操作 obj pop() -> 弹出操作 obj peek() -> pick top 操作(获取栈顶元素) int getSize() -> 获取栈元素num 操作 bool isEmpty() -> 判断栈是否为空操作
底层实现并不关心, 栈通过动态array(capacity 可以动态变化)实现即可，栈的操作是array的子集
example:
#!/usr/bin/env python # -*- coding: utf-8 -*- """ # @Time : 2020/1/18 下午7:21 # @Author : [email protected] # @Site : # @File : Stack.py # @Software: PyCharm """ from array.Array import Array class Stack: def __init__(self, capacity=None): """ :param capacity: 栈的容积 """ if capacity is None: self.array = Array() else: self.array = Array(capacity) def push(self, val): """ 向数组的末尾添加一个元素 :param val: :return: """ self.array.add_last(val) def pop(self): """ 弹出栈顶的元素，其实是栈顶的元素, 并删除 :return: """ return self.array.remove_last() def peek(self): """ 获取栈顶的元素，其实是数组的末尾元素 :return: """ return self.array.get_last() def get_size(self): return self.array.get_size() def is_empty(self): return self.array.is_empty() def get_capacity(self): return self.array.get_capacity() def to_string(self): res_str_stack = [] res_str_stack.append('Stack: [') for i in range(0, self.array.get_size()): val = self.array.get(i) if isinstance(val, int): val = str(val) res_str_stack.append(val) if i != self.array.get_size() - 1: res_str_stack.append(',') res_str_stack.append('] top') return "".join(res_str_stack) if __name__ == '__main__': # 1. 构建一个栈 stack = Stack(10) for i in range(0, 5): stack.push(i) print(stack.to_string()) stack.pop() print(stack.to_string())
4. 使用栈解决相关问题
#!/usr/bin/env python # -*- coding: utf-8 -*- """ # @Time : 2020/2/4 下午3:29 # @Author : [email protected] # @Site : # @File : Solution.py # @Software: PyCharm """ from stack.Stack import Stack class Solution: def __init__(self): pass def is_valid(self, s): array_stack = Stack() str_list = list(s) for index, char in enumerate(str_list): if char == '(' or char == '{' or char == '[': array_stack.push(char) else: if array_stack.is_empty(): return False top_char = array_stack.pop() if char == ')' and top_char != '(': return False if char == ']' and top_char != '[': return False if char == '}' and top_char != '{': return False return array_stack.is_empty() if __name__ == '__main__': solution = Solution() valid_str = '}[[' print(solution.is_valid(valid_str)) valid_str = '{}' print(solution.is_valid(valid_str)) valid_str = '{[]}' print(solution.is_valid(valid_str))
