打牢地基-栈篇

章节

  • 栈的特性 & 图示
  • 栈的应用场景
  • 构建一个栈
  • 使用栈结构解决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))