代码随想录算法训练营Day11 | 栈与队列基础 232.用栈实现队列 225. 用队列实现栈 20. 有效的括号

栈与队列

栈：先进后出     empty - push - push - pop

队列：先进先出

Tips： 栈和队列是STL（C++标准库）里面的两个数据结构。

STL最旁边的三个版本：HP STL、P.J.Plauger STL、SGI STL

232. 用栈实现队列

题目：232用栈实现队列

在python中，in主要负责push，out主要负责pop

初始：self.stack_in = [ ]   self.stack_out = [ ]

push(x) 将一个元素放入队列尾部：self.stack_in.append(x)

pop() 从队列首部移除元素：先判断是否为空；out栈是否为空，清空，再依次将in栈元素放入out栈，再清空。

        if self.empty():
            return None
        
        if self.stack_out:
            return self.stack_out.pop()
        else:
            for i in range(len(self.stack_in)):
                self.stack_out.append(self.stack_in.pop())
            return self.stack_out.pop()

peek() 返回队列首部元素：执行pop，在out栈加入pop元素，返回当前元素。

    def peek(self) -> int:
        """
        Get the front element.
        """
        ans = self.pop()
        self.stack_out.append(ans)
        return ans

empty() 返回队列是否为空：

    def empty(self) -> bool:
        """
        只要in或者out有元素，说明队列不为空
        """
        return not (self.stack_in or self.stack_out)

225. 用队列实现栈

题目：225. 用队列实现栈

在python中，in主要存放所有数据，out主要仅pop时使用

初始：self.queue_in  = deque()     self.queue_out = deque()

push(x)  元素 x 入栈：直接append即可

 def push(self, x: int) -> None:
        """
        直接append即可
        """
        self.queue_in.append(x)

pop()  移除栈顶元素：先判断是否为空，把in栈除最后一个元素依次放入out栈，交换in和out，此时out栈只有一个元素，把out中的pop出来，即原队列的最后一个。

  def pop(self) -> int:
     
        if self.empty():
            return None

        for i in range(len(self.queue_in) - 1):
            self.queue_out.append(self.queue_in.popleft())
        
        self.queue_in, self.queue_out = self.queue_out, self.queue_in    # 交换in和out，这也是为啥in只用来存
        return self.queue_out.popleft()

top()  获取栈顶元素：先判断不为空，仅有in存放数据，返回第一个即可

        if self.empty():
            return None
        
        return self.queue_in[-1]    # 这里实际上用到了栈，因为直接获取了queue_in的末尾元素

empty()  返回栈是否为空：

    def empty(self) -> bool:
        """
        因为只有in存了数据，只要判断in是不是有数即可
        """
        return len(self.queue_in) == 0

 20. 有效的括号

题目：20. 有效的括号

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

括号匹配是使用栈解决的经典问题。

方法：① 仅用栈，省空间  ② 用字典

思考三种不符合的情况：①最后栈不为空，没有配对完全 ② 遇到类型不匹配 ③ 栈为空还需要弹出

① 仅用栈

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        
        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            elif not stack or stack[-1] != item: #栈为空即第一种情况或第一个元素不是当前匹配元素，返回False
                return False
            else:
                stack.pop()
        
        return True if not stack else False

 # 栈为空即第一种情况或第一个元素不是当前匹配元素，返回False

②  使用字典

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {
            '(': ')',
            '[': ']',
            '{': '}'
        }
        for item in s:
            if item in mapping.keys():
                stack.append(mapping[item])
            elif not stack or stack[-1] != item: 
                return False
            else: 
                stack.pop()
        return True if not stack else False