数据结构 栈 / 队列(第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)