数据结构 栈 / 队列(第9天)

20. 有效的括号

判断输入的括号是否有效。
左右括号··能闭合，顺序合适。

思路：用栈实现。遇到左括号就保存在栈中，遇到右括号则需要从栈中弹出一个括号，与之配对。

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        pairs = {
                '(' : ')',
                '[' : ']',
                '{' : '}'
                }
        for c in s:
            if c in  pairs.keys() :
                stack.append(c)
            else:
                if len(stack) == 0:
                    return False
                left = stack.pop()
                if c != pairs.get(left) :  
                    return False
        return len(stack) == 0

232. 用栈实现队列

用栈实现队列（先进先出）。
思路：
栈是先进后出的，所以用一个栈显然无法实现。
用两个栈，一个栈​​​stackin​​​用来保存进来的元素，一个栈​​stackout​​​用来输出元素。
输入元素时，添加到​​​stackin​​​，输出元素时，将​​stackin​​​的所有元素添加到​​stackout​​​，再从​​stackout​​​输出。
这样相当于负负得正。

class MyQueue:

    def __init__(self):
        self.stackin  = []
        self.stackout = []


    def push(self, x: int) -> None:
        self.stackin.append(x)


    def pop(self) -> int:
        if self.empty():
            return None
        if not self.stackout:
            while self.stackin:
                self.stackout.append(self.stackin.pop())
        return self.stackout.pop()


    def peek(self) -> int:
        res = self.pop()
        self.stackout.append(res)
        return res


    def empty(self) -> bool:
        return not (self.stackin or self.stackout)