打牢地基-棧篇
- 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))
