Stack

栈是一个后入先出(LIFO)的数据结构，其中添加移除新项总发生在同一端。这一 端通常称为“顶部”。与顶部对应的端称为“底部”。

栈

栈操作如下

Stack() 创建一个空的新栈。 它不需要参数，并返回一个空栈。

**push(item)**将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。

pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。

peek() 从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。

isEmpty() 测试栈是否为空。不需要参数，并返回布尔值。

size() 返回栈中的 item 数量。不需要参数，并返回一个整数

python实现

class Stack:
    def __init__(self):
        self.data = []

    def push(self, ele):
        self.data.append(ele)
    
    def pop(self):
        return self.data.pop()
      
    def peek(self):
        return self.data[-1]

    def isEmpty(self):
        return len(self.data) == 0
    
    def size(self):
        return len(self.data)

常见算法

最小栈

最小栈

class MinStack:
    def __init__(self):
        self.s1 = Stack()
        self.s2 = Stack()

    def push(self, ele):
        self.s1.push(ele)
        if self.s2.size() > 0:
            self.s2.push(min(ele, self.s2.peek()))
        else:
            self.s2.push(ele)

    def pop(self):
        self.s2.pop()
        return self.s1.pop()

    def get_min(self):
        return self.s2.peek()

    def peek(self):
        return self.s1.peek()
    
    def isEmpty(self):
        return len(self.s1)

括号匹配：

给定一个只包括 ‘('，')'，'{'，'}'，'['，']’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1:

输入: “()” 输出: true 示例 2:

输入: “()[]{}” 输出: true 示例 3:

输入: “(]” 输出: false 示例 4:

输入: “([)]” 输出: false 示例 5:

输入: “{[]}” 输出: true

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        stack = []
        left_char_list = ['(', '{', '[']
        right_char_list = [')', '}', ']']
        for e in s:
            if e in left_char_list:
                stack.append(e)
            elif e in right_char_list:
                if left_char_list.index(
                        stack.pop()) != right_char_list.index(e):
                    return False

        return len(stack) == 0