今日任务：

1. 二叉树理论基础
2. 递归遍历  
3. 迭代遍历
4. 统一迭代



资料来源：

1. [代码随想录 | 二叉树理论基础](https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | 递归遍历](https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
3. [代码随想录 | 迭代遍历](https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html)
4. [代码随想录 | 统一迭代](https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html#%E6%80%9D%E8%B7%AF)

### 1 二叉树理论基础

1. **满二叉树**：如果一棵二叉树的所有节点的度要么是0要么是2，并且度为0的节点在同一层上，那么它就是一棵满二叉树。

2. **完全二叉树**：在完全二叉树中，除了最底层以外，其余每层节点数量都达到最大值，并且最下面一层的节点都集中在该层的最左边的若干位置。若最底层为第h层，则该层的节点数不超过$1$到$2^{h-1}$这个范围。

3. **二叉搜索树**：二叉搜索树是一个有序树，它符合以下条件：

     - 若它的左子树不空，则左子树上的所有节点的值均小于它的根节点的值
     - 若它的右子树不空，则右子树上的所有节点的值均大于它的根节点的值
     - 它的左右子树也分别为二叉排序树

4. **平衡二叉搜索树**：AVL树，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树。

5. **二叉树的遍历方式**：深度优先搜索（DFS，可以前序中序后序，使用栈）、广度优先搜索（BFS，可以层序，使用队列）、前序（中左右，可以递归可以迭代）、中序（左中右，可以递归可以迭代）、后序（左右中，可以递归可以迭代）、层序（可以迭代）。

6. 二叉树的定义

``` python
class TreeNode:
    def __init__(self, val: int, left: TreeNode = None, right: TreeNode = None):
        self.val = val
        self.left = left
        self.right = right
```

### 2 递归遍历

递归的三要素：

1. 递归函数的参数和返回值

2. 终止条件

3. 单层递归的逻辑

以前序遍历为例：

1. 递归函数的参数和返回值：遍历不需要处理数据什么的，所以只需要传入要遍历的节点和存放遍历结果的数据即可。

2. 终止条件：如果当前要遍历的节点是空，遍历就要结束了，这就是终止条件。

3. 单层递归的逻辑：前序遍历是中左右，那就是先遍历中间的，然后调用函数遍历左子树的，最后是右子树的。

根据这三个条件，前序遍历的代码就是这样：

``` python
# 二叉树的前序遍历 递归写法
from typing import Optional, List

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        return self.traversal(root, [])  # 进入递归

    def traversal(self, node: Optional[TreeNode], result: List[int]) -> List[int]:  # 参数和返回值
        if node is None:  # 终止条件
            return result
        else:
            # 单层递归的逻辑
            result.append(node.val)
            self.traversal(node.left, result)
            self.traversal(node.right, result)
            return result
```

举一反三，中序和后序的代码也是差不多：

``` python
# 二叉树的中序遍历 递归写法
from typing import Optional, List

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        return self.traversal(root, [])

    def traversal(self, node: TreeNode, result: List[int]) -> List[int]:
        if node is not None:
            self.traversal(node.left, result)
            result.append(node.val)
            self.traversal(node.right, result)
        return result
```

``` python
# 二叉树的后序遍历 递归写法
from typing import Optional, List

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        return self.traversal(root, [])

    def traversal(self, node: TreeNode, result: List[int]) -> List[int]:
        if node is None:
            return result
        else:
            self.traversal(node.left, result)
            self.traversal(node.right, result)
            result.append(node.val)
            return result
```     

### 3 迭代遍历

之前的前序，中序和后序遍历都用的递归来写的，而栈又是递归所用的函数栈的底层，那么栈也能替代递归，使得二叉树的遍历不使用递归方式完成。

前序遍历：要先处理的是根节点，之后是左节点，最后是右节点。在栈中也是先弹出当前节点进行处理，然后加入它的左节点和右节点，下次循环再出栈一个元素。

``` python
# 二叉树的前序遍历 迭代写法
from collections import deque
from typing import Optional, List

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack = deque()
        if root is None:
            return []
        result = []
        node = root
        stack.append(node)
        while node is not None and len(stack) != 0:
            node = stack.pop()
            result.append(node.val)
            if node.right is not None:  # 栈是先进后出 所以先进右节点
                stack.append(node.right)
            if node.left is not None:
                stack.append(node.left)

        return result
```        

中序遍历：这次维护的栈，必须保证栈顶是目前子树中最“左”的节点，如果已经指到叶子节点了，之后指向空了，就可以从栈中取出元素，处理并且指向右节点了。

``` python
# 二叉树的中序遍历 迭代写法
from collections import deque
from typing import Optional, List

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        stack = deque()
        result = []
        node = root
        while node is not None or len(stack) != 0:
            if node is not None:  # 这一部分的目的是先让栈顶存着目前子树最“左”的节点
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()  # 到这一步可以确定没有再“左”的节点了 从栈中弹出并且处理之前的节点
                result.append(node.val)
                node = node.right
        return result
```     

后序遍历：由于后序遍历的顺序和前序完全相反，所以直接先前序调整一下顺序，然后出了结果反转一下即可。

![image.png](https://www.misaka19327.cc/static/img/dee2688b9a4c69a6514f5dd56b9a872c.image.png)

``` python
# 二叉树的后序遍历 迭代写法
from collections import deque
from typing import Optional, List

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        stack = deque()
        result = []
        node = root
        stack.append(node)
        while len(stack) != 0:
            node = stack.pop()
            result.append(node.val)
            if node.left is not None:
                stack.append(node.left)
            if node.right is not None:
                stack.append(node.right)
        result.reverse()
        return result
```        

### 4 统一迭代（标记法）

在之前的迭代法中，前、后序和中序的写法有截然不同的区别。这是因为前、后序要处理加入结果数组的节点，和每次循环弹出的节点是一致的，而中序不是一致的。而不一致的解决方法，可以通过在栈中加入标记来解决，因此就有了统一写法的迭代法（也称标记法）。

这种统一写法的迭代法不是很好想，但是优势前中后序改变很容易，也很好记。也需要会写。

``` python
# 二叉树的前序遍历 统一迭代写法
from collections import deque
from typing import Optional, List

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        stack = deque()
        result = []
        node = root
        stack.append(node)
        while len(stack) != 0:
            node = stack.pop()
            if node is not None:
                if node.right is not None:
                    stack.append(node.right)
                if node.left is not None:
                    stack.append(node.left)
                stack.append(node)
                stack.append(None)  # 标记在这里 这个标记的含义是它前面的节点已经被处理 不再需要向下找子节点了
            else:
                node = stack.pop()
                result.append(node.val)  # 因为有标记所以直接加入值
        return result
```        

``` python
# 二叉树的后序遍历 统一迭代写法
from collections import deque
from typing import Optional, List

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        stack = deque()
        result = []
        node = root
        stack.append(node)
        while len(stack) != 0:
            node = stack.pop()
            if node is None:
                node = stack.pop()
                result.append(node.val)
            else:
                # 相比前序 只有下面这6行代码有顺序变化
                stack.append(node)
                stack.append(None)
                if node.right is not None:
                    stack.append(node.right)
                if node.left is not None:
                    stack.append(node.left)
        return result
```

``` python
# 二叉树的中序遍历 统一迭代写法
from collections import deque
from typing import Optional, List

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        stack = deque()
        result = []
        node = root
        stack.append(node)
        while len(stack) != 0:
            node = stack.pop()
            if node is None:
                node = stack.pop()
                result.append(node.val)
            else:
                # 同理 只有下面有顺序变化
                if node.right is not None:
                    stack.append(node.right)
                stack.append(node)
                stack.append(None)
                if node.left is not None:
                    stack.append(node.left)
        return result
```

代码随想录算法训练营第十四天 | 二叉树基础，四种遍历方式

今日任务

1. LeetCode239 滑动窗口最大值
2. LeetCode347 前K个高频元素
3. 栈和队列总结



资料来源

1. [代码随想录 | LeetCode239 滑动窗口最大值](https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | LeetCode347 前K个高频元素](https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
3. [代码随想录 | 栈和队列总结](https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html#%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%9A%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80)

### 1 LeetCode239 滑动窗口最大值

:::info{title="题目"}
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

 

示例 1：
```
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
 ```
示例 2：
```
输入：nums = [1], k = 1
输出：[1]
```

提示：

- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
- 1 <= k <= nums.length
:::

解析看最后那一块。

``` python
from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = MonotonousQueue()
        result = [0] * (len(nums) - k + 1)
        for i in range(k - 1):
            queue.append(nums[i])
        for i in range(len(nums) - k + 1):
            queue.append(nums[i + k - 1])
            result[i] = queue.getFirst()
            if nums[i] == queue.getFirst():
                queue.pop(nums[i + k - 1])
        return result


class MonotonousQueue:
    def __len__(self):
        return len(self.queue)

    def __init__(self):
        self.queue = deque()

    def getFirst(self):
        return self.queue[0]

    def pop(self, number: int):
        self.queue.popleft()
        if len(self.queue) > 0:
            while self.queue[0] < number:
                self.queue.popleft()

    def append(self, number: int):
        if len(self.queue) == 0:
            self.queue.append(number)
            return
        while self.queue[-1] < number:
            self.queue.pop()
            if len(self.queue) == 0:
                break
        self.queue.append(number)
```

### 2 LeetCode347 前K个高频元素

:::info{title="题目"}
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

 

示例 1:
```
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
```
示例 2:
```
输入: nums = [1], k = 1
输出: [1]
```

提示：

- 1 <= nums.length <= 105
- k 的取值范围是 [1, 数组中不相同的元素的个数]
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
:::

解析看最后那一块。

``` python
import heapq
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        map = dict()
        for i in nums:
            if i in map.keys():
                map[i] += 1
            else:
                map[i] = 1

        pri_que = []

        for key, freq in map.items():
            heapq.heappush(pri_que, (freq, key))
            if len(pri_que) > k:
                heapq.heappop(pri_que)

        result = []
        for i in pri_que:
            result.append(i[1])
        return result
```     

### 3 栈和队列总结

#### 3.1 栈题目

栈的先进后出的特性，使得它能够快速的解决一些邻近的捉对问题，比如说之前的查括号是否都是一对一对的，或者说删除相邻相同字符。另外在一些要保留之前元素顺序的同时对当前元素和之前的若干个元素进行处理的话，栈也是值得考虑的一种解法，就比如之前的逆波兰表达式。

栈在一些比较底层的程序应用上常见，比如说解析文件路径，再比如说程序运行的函数调用栈。

#### 3.2 队列题目

先说单调队列。

单调队列是一个视情况而定的队列，它的目的一般是使队列里的元素递增或者递减。单调队列并没有一种固定的实现，**甚至并不固定是先出先进还是先出后进**，根据题目要求来灵活制定pop和append的行为。以今天的题目为例，它就维护了一个名为单调队列，实则为双端队列的数据结构。

这题目要求求滑动窗口中的最大值，那么很明显是要维护一个递减的单调序列，每次要实际求的是最大值。对应到具体的单调队列上，append元素之前就要保证之前的所有元素都比自己大，所以append的行为就是从队列右端一个一个取值和要加入的元素进行比较，直到前面的元素都比自己大为止；pop元素就是要在窗口滑出最大值的时候再pop。

再说大小顶堆/优先级队列。

它和单调队列不一样，单调队列的目的是保证每次pop元素的时候一定pop出最大/最小的那个，而优先级队列则是真的要对元素全部排序。堆对应的是完全二叉树，大顶堆对应的是根节点是最大值，队列就是降序排列；小顶堆对应的根节点是最小值，队列就是升序排序。

最后是python里小顶堆对应的库`heapq`的用法。

- 建立堆：heap = [] 就使用列表就可以
- 将一个队列加入堆/变成小顶堆：heappush(heap, array)/heapify(heap)
- 弹出元素：heappop(heap)
- 获取堆中前num个的最大值/最小值：nlargest(num, heap)/nsmallest(num, heap)
- 合并两个有序数组：merge(sorted(array1), sorted(array2))
- 先加入num元素，再弹出堆顶元素：heapqpushpop(heap, num)
- 先弹出堆顶元素，再加入num元素：heapqreplace(heap, num)

代码随想录算法训练营第十三天 | LeetCode239 滑动窗口最大值、LeetCode347 前K个高频元素

今日任务：

1. LeetCode20 有效的括号
2. LeetCode1047 删除字符串中的所有相邻重复项
3. LeetCode150 逆波兰表达式求值



资料来源：

1. [代码随想录 | LeetCode20 有效的括号](https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | LeetCode1047 删除字符串中的所有相邻重复项](https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html#%E6%80%9D%E8%B7%AF)
3. [代码随想录 | LeetCode150 逆波兰表达式求值](https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC)

### 1 LeetCode20 有效的括号

:::info{title="题目"}
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
 

示例 1：
```
输入：s = "()"
输出：true
```
示例 2：
```
输入：s = "()[]{}"
输出：true
```
示例 3：
```
输入：s = "(]"
输出：false
```

提示：

- 1 <= s.length <= 104
- s 仅由括号 '()[]{}' 组成
:::

直接将读取到的左括号入栈，右括号直接和栈内的左括号匹配即可。

``` python
# 我的代码
from collections import deque


class Solution:
    def isValid(self, s: str) -> bool:
        stack = deque()
        for i in s:
            if i in ['(', '[', '{']:
                stack.append(i)
            if i in [')', ']', '}']:
                if len(stack) == 0:
                    return False
                if stack.pop() + i not in ['()', '{}', '[]']:
                    return False
        if len(stack) == 0:
            return True
        else:
            return False
```       

入栈的时候可以直接入当前元素的右括号，来减少之后的匹配时间。

### 2 LeetCode1047 删除字符串中所有相邻重复项

:::info{title="题目"}
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

 

示例：
```
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
```

提示：

- 1 <= S.length <= 20000
- S 仅由小写英文字母组成。
:::

遍历字符串，并且入栈。入栈前先检查栈顶元素是否相同，相同的话栈顶元素直接出栈。最后检查栈内是否还有元素，有的话一个一个取出来再反向一下就可以了。

``` python
from collections import deque

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = deque()
        for i in s:
            if len(stack) != 0:
                j = stack.pop()
                if i == j:
                    continue
                else:
                    stack.append(j)
                    stack.append(i)
            else:
                stack.append(i)
        return_list = [""] * len(stack)
        for a in range(len(return_list) - 1, -1, -1):
            return_list[a] = stack.pop()
        return "".join(return_list)
```   

### 3 LeetCode150 逆波兰表达式求值

:::info{title="题目"}
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

- 有效的算符为 '+'、'-'、'*' 和 '/' 。
- 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
 

示例 1：
```
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
```
示例 2：
```
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
```
示例 3：
```
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
```

提示：

- 1 <= tokens.length <= 104
- tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数
 

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

- 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
:::

凡是数字就入栈，凡是运算符就取出栈顶的两个元素进行运算。注意python特性。

![image.png](https://www.misaka19327.cc/static/img/e27c1360f2b6d5ea96fabb7b0d76eb47.image.png)

``` python
from collections import deque
from typing import List

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = deque()
        for i in tokens:
            if i not in ['+', '-', '*', '/']:
                stack.append(int(i))
            else:
                b = stack.pop()
                a = stack.pop()
                if i == '+':
                    stack.append(a + b)
                elif i == '-':
                    stack.append(a - b)
                elif i == '*':
                    stack.append(a * b)
                else:
                    stack.append(int(a / b))
        return stack.pop()
```

代码随想录算法训练营第十一天 | LeetCode20 有效的括号、LeetCode1047 删除字符串中的所有相邻重复项、LeetCode150 逆波兰表达式求值

本文内容：

1. 常见网络设备/概念：路由器、交换机、集线器、网关、网桥
2. 虚拟机网络的3（+1）种连接方式：桥接、NAT、仅主机、镜像
3. UDP广播、多播说明



### 1 常见网络设备

先贴个图在这

![image.png](https://www.misaka19327.cc/static/img/5f464838383027e19826475a1d866a0e.image.png)

#### 1.1 集线器（Hub）

集线器工作在七层模型中的物理层，它的作用是对接收到的信号进行同步整形放大，再将其转发到所有端口，以扩大网络的传输距离。一些集线器会将接收到的弱信号重新生成，一些集线器会整理信号的时序以提供所有端口的同步通信。

> 中继：将接收到的衰减到不完整的信号进行整理，重新生成完整的信号再进行传输。

> 中继器（Repeater）：专门用于中继的设备。

举例来说，假设集线器有8个端口，并且这8个端口连接了8个计算机。如果计算机a向计算机c发送数据，那么数据会先到达集线器，集线器会将数据广播到所有端口，所有的计算机都会接收数据并且判断是否是发给自己的数据，如果是则接收，如果不是则丢弃。

因为集线器的这种特性，它通常位于网络的中心，因此也被称为hub。

#### 1.2 交换机（Switch）

交换机是集线器的升级版本，它工作在链路层。它可以对接收到的数据进行解析并且重新生成，经过内部处理后转发到目的端口，具备自动寻址能力和交换能力。

> 在这里所说的交换机，并不是广义上的交换机，而是特指工作在链路层的交换机（或者说桥接设备）。广义上说，所有具备交换功能（即信号从设备入口到设备出口的转发）的设备都能被称为交换机。

> 桥接：按我个人理解，只要具备了对接收到的数据进行解析，根据解析到的MAC地址将其转发到指定的端口上的能力的，都算是桥接。至于连通两个网络之类的，是桥接能力的一种应用。比如说两个路由器分别连接了若干个计算机，再用一个交换机连接两个路由器，那么这个交换机就能连通由这两个路由器构建的网络。

交换机的工作过程如下：假设交换机连接了8个计算机，并且计算机a想要给计算机c发送信息。交换机内部维护了一个地址对照表，当计算机a第一次向计算机c发送信息时，交换机还不知道计算机c具体连接到哪个端口上，因此会将这条信息进行广播。计算机c的网卡收到消息会进行回应，交换机接收到回应后，修改地址对照表，将计算机c的网卡MAC地址和端口存储起来。下一次计算机a再向计算机c发送信息时，交换机就能够通过地址对照表，准确的将这条信息转发给连接着计算机c的端口。

交换机的转发速度非常快，但是也有缺点：交换机之间不能存在回路，并且因此交换机之间只能由一条网线连接，使得信息集中在一条链路上，不能均衡负载。

#### 1.3 路由器（Router）

> 路由：任何网络中选取路径的程序。

路由器是网络中进行网间连接的关键设备，它工作在网络层。它为每一个流经它的数据报找到最佳传输路径，并且有效的将其送到目的地。它一方面可以跨越不同的网络类型，另一方面可以将整个互连网络抽象为分割的逻辑上独立的网络单位。它可以：

1. IP 数据报的转发，包括数据报的寻径和传送
2. 子网隔离，抑制广播风暴
3. 维护路由表，并与其它路由器交换路由信息，这是 IP 报文转发的基础
4. IP 数据报的差错处理及简单的拥塞控制
5. 实现对 IP 数据报的过滤和记帐

#### 1.4 网桥（Bridge）

网桥是不同网络之间沟通的设备，它工作在链路层。它比交换机接口要少，功能和交换机差不多，但是它能够沟通不同的网络类型。如今的交换机大多也具备这个功能，甚至兼容了好几个网络协议的操作系统自己也可以是网桥。

#### 1.5 网关（Gateway）

顾名思义，网关是一个网络对外连接的出口，它是网络层的概念。假设一个地址为`192.168.1.2/24`的计算机想要ping`192.168.2.2/24`的计算机，那么它必须经过网关。因为要ping的目标明显不在自己这个网段里，只能去其他的子网中寻找，所以只能发给网关，由网关再转发给要ping的目标。一般情况下网关就是路由器的ip。

#### 1.6 冲突域

冲突域是物理层的概念，它所指的是物理上在一根网线上的所有设备，或者说同一物理网段上的所有节点的集合，或者说以太网上竞争同一带宽的节点集合，这三个概念都对。冲突域代表了冲突在其中发生并且传播的区域，这个区域被认为是共享的。

举例来说，假设一个Hub上连接了若干计算机，那么如果一个计算机向另一个计算机发送了消息，那么在发送消息这个极短的时间内，别的计算机就不能再发送消息，如果发送就会产生冲突（一根线不能同时传输多个消息），这个冲突会发生的区域即为冲突域。冲突域的本质是单一带宽资源的占用。冲突域的本质也决定了Hub和Repeater不能划分冲突域，而Switch，Router和Bridge都可以划分冲突域。

#### 1.7 广播域

广播域是网络层的概念，它所指的是所有能够接收相同广播消息的设备集合。Hub，Repater，Switch，Bridge都不能划分广播域，Router可以。VLAN（Vritual Local
Area Network）也可以划分广播域，倒不如说VLAN的目的就是为了划分广播域。

### 2 虚拟机网络的3（+1）种连接方式

![image.png](https://www.misaka19327.cc/static/img/94df6365fa490666587bd0f41588aa30.image.png)

图中的三个网络设备是VMware设定的三个虚拟交换机，另外还有插在宿主机上的两张虚拟网卡。

![image.png](https://www.misaka19327.cc/static/img/bf5b9d8731d242f07f944b0dc52a480e.image.png)

#### 2.1 桥接连接

在这种模式下，宿主机的网卡会与一个虚拟网桥连接，虚拟网桥的另一端是一个虚拟交换机，交换机连接所有虚拟机的网卡。因为交换机和网桥不能分割广播域，所以宿主机和几个虚拟机之间都能进行广播，而且互相都能收得到。

因为宿主机网卡和虚拟机网卡相当于是连在同一个交换机上，所以虚拟机网卡要求必须和宿主机网卡在同一网段中，子网掩码、DNS和网关一致才可以。因为在同一网段下，所以虚拟网桥会转发宿主机网卡收到的广播、多播消息，以及目标为虚拟机网段（192.168.1.1到192.168.1.30，其网段为192.168.1.0/27，广播地址为192.168.1.31）的单播，因此虚拟机网卡也能接收到宿主机连接的路由器的DHCP信息和路由更新。

![image.png](https://www.misaka19327.cc/static/img/015186a64b20b5358894bbbb2527da9e.image.png)

另外，如果宿主机所在的网段ip数量较少，就不太适合桥接模式。

如果要使用桥接模式，最好强制指定桥接模式使用的网卡，否则它可能会使用其他的不联网的网卡。

![image.png](https://www.misaka19327.cc/static/img/3228a8f18fc22393563723e47187e8b8.image.png)

#### 2.2 NAT（Network Address Translation）模式

NAT模式下，除了VMnet8虚拟交换机连接所有虚拟机网卡不变，宿主机网卡连接在一个虚拟的NAT路由器设备上，这个虚拟的NAT路由器设备和一个虚拟的DHCP服务器一起连接在VMnet8上，同时VMnet8上还会有一个接口，接的是**宿主机的虚拟网卡**Ethernet adapter VMware Network Adapter VMnet8。

> NAT（Network Address Translation）：网络地址转换，是1994年提出的一种在ip资源不够的情况下的解决方法，它需要一个安装了NAT软件的路由器。当NAT路由器下的设备想要向外界发送请求时，NAT路由器会收到这个请求，并且将其起始ip地址和端口映射为NAT路由器自己的ip和可用的端口。等到外界回复这个请求时，NAT路由器再将其目的ip地址和端口映射为原本的设备的ip地址和端口。
> 
> NAT确实能够很好的避免占用ip资源的问题，并且同时提升了安全性（不向外部暴露内部设备地址），但是也不是没有缺点，比如说可能不能兼容一些软件的自定义协议等。

> DHCP：动态主机配置协议（Dynamic Host Configuration Protocol），它可以为同一子网下的设备自动分配ip和配置子网掩码，网关和DNS。

![image.png](https://www.misaka19327.cc/static/img/9689396bde3b67c144833134c21d5abe.image.png)

这种情况下，虚拟机能够通过NAT路由器设备上网，只要宿主机能够上网，虚拟机也就能上网；通过宿主机的虚拟网卡和宿主机通信（只能通信），对外隐藏了虚拟机的ip信息。宿主机接收到的广播，多播消息将不会被转发到虚拟机上（NAT路由器设备分割广播域）。如果宿主机的虚拟网卡被禁用，不会影响虚拟机上网，虚拟机也能发消息到宿主机上，只是宿主机和其他外部设备不能主动通过NAT路由器访问虚拟机。

#### 1.3 仅主机模式（Host Only）

仅主机模式下，除了VMnet1虚拟交换机连接所有虚拟机网卡和虚拟DHCP服务器不变，去掉了NAT设备，由宿主机的虚拟网卡Ethernet adapter VMware Network Adapter VMnet1与VMnet1直连。这种情况下，虚拟机和外部网络隔离开，成为了一个独立的网络，这只是保证宿主机和虚拟机之间的互相通信，默认是不联网的，想要联网的话，需要另外设置宿主机的网卡，使其共享网络给宿主机的虚拟网卡（光共享也不行，还得另外设置DHCP）。

![image.png](https://www.misaka19327.cc/static/img/92596f2a5be9db0fa011e88c967f7e70.image.png)

共享网络设置位置：

![image.png](https://www.misaka19327.cc/static/img/9c7c6bf0393ef7e1dbf57b890672c8d9.image.png)

#### 1.4 配置方法

配置kali虚拟机网卡信息都是通过修改`/etc/network/interfaces`文件来完成的，寻求帮助可以`man interfaces`，当然其实也可以选择图形化界面配置：

![image.png](https://www.misaka19327.cc/static/img/17a30f845fad7cbb5a60f70d4520ee4f.image.png)

配置完成后可以尝试ping宿主机和`ping www.baidu.com`试试，有结果就配置完成了。

### 3 UDP广播 多播分析

正常情况下应该是这样的（已关闭防火墙，并且确保三个主机能够互相ping通）：

1. NAT模式下

- [x] Linux192.168.11.255发送广播，Windows端绑定Ethernet adapter VMware Network Adapter VMnet8来进行接收。
- [ ] Linux192.168.11.225发送广播，Linux端绑定eth0网卡来进行接收。
- [x] Linux192.168.11.225发送广播，Linux端绑定0.0.0.0来进行接收。

组播也是一个情况，原本应该接收到的eth0网卡，并没有显示出数据，虽然抓包工具已经抓到了eth0网卡上的包。

![](https://www.misaka19327.cc/static/img/f8b2c2d37fd922a7451dbffcabdedf03.image.png)

2. 桥接模式下

- [ ] Linux192.168.234.255发送广播，Windows端绑定自身实体网卡/0.0.0.0来进行接收。
- [ ] Linux192.168.11.225发送广播，Linux端绑定eth0网卡来进行接收。
- [x] Linux192.168.11.225发送广播，Linux端绑定0.0.0.0来进行接收。

组播也是一个情况，原本eth0就收不到了，现在Windows端也收不到（但是单播收得到），确实有点没理解。绑定0.0.0.0表示接收所有网卡的某个特定端口的所有信息，但是Linux系统里除了loopback网卡就是eth0网卡，总不能是通过环回网卡发过来的吧。桥接模式的Windows端更是和所有虚拟机就处于一个子网下，更没能理解为什么收不到。

常见网络设备/概念 && 虚拟机网络三种连接方式说明 && UDP广播 多播

今日任务：

1. 栈与队列理论基础
2. LeetCode232 用栈实现队列
3. LeetCode225 用队列实现栈



> 今日心情：开始女娲补天（）

资料来源：

1. [Python deque用法介绍](https://blog.csdn.net/weixin_43790276/article/details/107749745)
2. [代码随想录 | 栈与队列理论基础](https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html)
3. [代码随想录 | LeetCode232 用栈实现队列](https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html#%E6%80%9D%E8%B7%AF)
4. [代码随想录 | LeetCode225 用队列实现栈](https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

### 1 栈与队列理论基础

python中常用的类似栈与队列的数据结构为deque（`from collections import deque`）双端队列。

- 如果要作为栈使用，那么可用的api有入栈（`append`）、出栈（`pop`）。
- 如果要作为队列使用，那么可用的api有入队（`append`）、出队（`popleft`）。
- 作为双端队列来说，`appendleft`也是有的。
- 它还支持使用可迭代对象（字符串、列表灯）一次添加多个元素（`extend`，`extendleft`）。
- 它可以在初始化时通过指定`maxlen`属性来指定双端队列的长度（`deque(maxlen=5)`）。
- 它还支持指定索引查询（`index`）、计数元素个数（`count`）、指定元素删除（`remove`）、清空（`clear`）、复制（`copy`）、反转（`reverse`）和指定次数进行轮转（`rotate`）。

### 2 LeetCode232 用栈实现队列

:::info{title="题目"}
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
 

示例 1：
```
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
```

提示：

- 1 <= x <= 9
- 最多调用 100 次 push、pop、peek 和 empty
- 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
:::

如果是硬模拟的话，那一个栈主要存元素，另一个栈用于在取出头元素时，从存元素的栈中倒腾出元素。这样的话`push`和`empty`就简单了，直接看那一个栈就行；`pop`和`peek`需要倒两次元素。

``` python
# 我的代码
from collections import deque

class MyQueue:

    def __init__(self):
        self.stack1 = deque()
        self.stack2 = deque()
        # 可用操作：压栈append 出栈pop 求长度len 判断是否全部为空

    # 进入队尾
    def push(self, x: int) -> None:
        self.stack1.append(x)


    # 出队
    def pop(self) -> int:
        while len(self.stack1) != 1:
            self.stack2.append(self.stack1.pop())
        result = self.stack1.pop()
        while len(self.stack2) != 0:
            self.stack1.append(self.stack2.pop())
        return result


    # 查看队列首个元素
    def peek(self) -> int:
        while len(self.stack1) != 1:
            self.stack2.append(self.stack1.pop())
        result = self.stack1.pop()
        self.stack1.append(result)
        while len(self.stack2) != 0:
            self.stack1.append(self.stack2.pop())
        return result


    # 队列是否为空
    def empty(self) -> bool:
        if len(self.stack1) == 0:
            return True
        return False
```

正常模拟方法可以看成将两个栈底对底拼起来来模拟一个队列的所有行为。

![679ef34cf7939965f5042ebec86f1f2.jpg](https://www.misaka19327.cc/static/img/776fc1656d87c481bc24496d89504c19.679ef34cf7939965f5042ebec86f1f2.jpg)

:::tip{title="提示"}
一定要注意转移元素只有在out栈为空时才能进行。
:::

``` python
from collections import deque

class MyQueue:

    def __init__(self):
        self.stack_in = deque()
        self.stack_out = deque()
        # 可用操作：压栈append 出栈pop 求长度len 判断是否全部为空

    # 进入队尾
    def push(self, x: int) -> None:
        self.stack_in.append(x)

    # 出队
    def pop(self, out: bool = True) -> int:
        if len(self.stack_out) == 0:
            while len(self.stack_in) != 0:
                self.stack_out.append(self.stack_in.pop())
        if out:
            return self.stack_out.pop()
        else:
            num = self.stack_out.pop()
            self.stack_out.append(num)
            return num

    # 查看队列首个元素
    def peek(self) -> int:
        # 这里提醒我了 可以对pop进行抽象 用默认值来设置函数参数
        return self.pop(False)

    # 队列是否为空
    def empty(self) -> bool:
        if len(self.stack_in) == 0 and len(self.stack_out) == 0:
            return True
        return False
```  

### 3 LeetCode225 用队列实现栈

:::info{title="题目"}
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 

注意：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
 

示例：
```
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
```

提示：

- 1 <= x <= 9
- 最多调用100 次 push、pop、top 和 empty
- 每次调用 pop 和 top 都保证栈不为空
:::

任务文档提醒我了，队列可以只用一个，没这一句的话我还真的会用两个队列去写。入栈和判空不说了，主要是出栈。出栈的原理就是队列的轮转，出队的元素可以再入队回到队尾，将队列中的除了最后一个元素的其他元素进行轮转，下一个要出队的元素就是要出栈的元素了。

``` python
from collections import deque


class MyStack:

    def __init__(self):
        self.queue = deque()
        # 队列允许的操作：入队append 出队popleft 求队列长度

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

    def pop(self, out: bool = True) -> int:
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())
        if out is True:
            return self.queue.popleft()
        num = self.queue.popleft()
        self.queue.append(num)
        return num

    def top(self) -> int:
        return self.pop(False)

    def empty(self) -> bool:
        if len(self.queue) == 0:
            return True
        return False
```