栈与队列
栈与队列
  栈定义
    栈是限定仅在表尾进行插入和删除操作的线性表
      允许插入和删除的一端成为栈顶（top），
另一端称为栈底（bottom）
      不含任何数据元素的栈称为空栈
      先进后出（Last In First Out）线性表，LIFO 结构
  队列定义
    队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
      先进先出（First In First Out）线性表，FIFO结构
      允许插入的一端成称为队尾，
允许删除的一端称为队头
  232.用栈实现队列
    题意
      请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（`push`、`pop`、`peek`、`empty`）：
      实现 `MyQueue` 类：
        - `void push(int x)` 将元素 x 推到队列的末尾
        - `int pop()` 从队列的开头移除并返回元素
        - `int peek()` 返回队列开头的元素
        - `boolean empty()` 如果队列为空，返回 `true` ；否则，返回 `false`
    思路
      需要先用 slice 实现栈的数据结构
      用两个栈实现队列，一个输入栈，一个输出栈
      fillStackOut
        如果输出栈为空，把输入栈的数据全部导入到输出栈
      push
        向输入栈添加元素
      pop
        先 fillStackOut()，再弹出输出栈的第一个元素
      Peak
        先 fillStackOut()，再查看输出栈的栈顶元素
      empty
        检查两个栈是否同时为空
return q.stackIn.Empty() && q.stackOut.Empty()
  225.用队列实现栈
    题意
      使用队列实现栈的下列操作：
        push(x) -- 元素 x 入栈
        pop() -- 移除栈顶元素
        top() -- 获取栈顶元素
        empty() -- 返回栈是否为空
      注意:
        你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
        你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
        你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
    思路
      用一个队列实现栈
      MoveWithoutLast()
        将队列中除最后一个元素外的其余所有元素，一个一个移到队尾
        for range len(s.queue) - 1 {
first := s.queue[0]
// 把第一个元素移到queue末尾
s.queue = append(s.queue, first)
s.queue = s.queue[1:] // 移除第一个元素
}
      push
        直接添加元素到队尾
      pop
        MoveWithoutLast()，再读取并删除栈顶元素
      top
        MoveWithoutLast()，读取栈顶元素并放到队尾
      empty
        stack.empty()
  20. 有效的括号
    题意
      给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串 `s` ，判断字符串是否有效。
      有效字符串需满足：
        1. 左括号必须用相同类型的右括号闭合。
        2. 左括号必须以正确的顺序闭合。
        3. 每个右括号都有一个对应的相同类型的左括号。
    思路
      map中存入左右括号对应关系
遇到左括号，将它存入栈中
      遇到右括号时，在map中查对应左括号
与栈顶元素匹配
        匹配
          弹出栈顶元素，继续下一轮匹配
        不匹配
          括号无效，return false
      匹配完毕
        栈中无元素
          所有括号都匹配，return true
        栈中还有元素
          说明有括号不匹配，return false
  1047. 删除字符串中的所有相邻重复项
    题意
      给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
      在 S 上反复执行重复项删除操作，直到无法继续删除。
      在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
      示例：
        输入："abbaca"
        输出："ca"
        解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
      提示：
        1 <= S.length <= 20000
        S 仅由小写英文字母组成。
    思路
      用栈来实现
        遍历字符串
          栈不空且与栈顶元素相等
            弹出栈顶元素
          否则（栈空或与栈顶元素不等）
            把元素放入栈
      可以用字符串（[]byte）来模拟栈
        字符串尾部是栈入口
        字符串头部是栈底部
        这样遍历完之后不必反转字符串
  150. 逆波兰表达式求值
    逆波兰表达式
      逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
      - 平常使用的算式则是一种中缀表达式，如 `( 1 + 2 ) * ( 3 + 4 )` 。
      - 该算式的逆波兰表达式写法为 `( ( 1 2 + ) ( 3 4 + ) * )` 。
      逆波兰表达式主要有以下两个优点：
        - 去掉括号后表达式无歧义，上式即便写成 `1 2 + 3 4 + * `也可以依据次序计算出正确结果。
        - 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
    题意
      给你一个字符串数组 `tokens` ，表示一个根据 [逆波兰表示法](https://baike.baidu.com/item/逆波兰式/128437) 表示的算术表达式。
      请你计算该表达式。返回一个表示表达式值的整数。
      注意：
        - 有效的算符为 `'+'`、`'-'`、`'*'` 和 `'/'` 。
        - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
        - 两个整数之间的除法总是 **向零截断** 。
        - 表达式中不含除零运算。
        - 输入是一个根据逆波兰表示法表示的算术表达式。
        - 答案及所有中间计算结果可以用 **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]` 内的一个整数
    思路--栈
      遍历 tokens 读到数字就放入栈中，读到运算符就弹出栈顶的2个元素做运算。
      需要注意相减和相除时的元素顺序
      判断元素是否是运算符
        用哈希表存运算符
          初始化时用 "+": {},
          对map中元素赋值时用 set["+"] = struct{}{}
        一旦读到运算符，从栈中取值做运算
        否则（读到数字），把数字放入栈中
      或判断元素是否是数字
        使用库函数 strconv.Atoi(token) ，判断元素是否是数字
  239. 滑动窗口最大值
    题意
      给你一个整数数组 `nums`，有一个大小为 `k` 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 `k` 个数字。滑动窗口每次只向右移动一位。
      返回 *滑动窗口中的最大值* 。
    思路--单调队列（仅适用与本题）
      队列没有必要维护窗口里的所有元素，只需要 维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。
      单调队列
        push(value)
          如果push的元素value大于队列入口元素，那么就将入口的元素弹出，直到要push的元素小于等于队列入口元素为止，保证了队列单调递减
          func (m *MyQueue) Push(val int) {
for !m.Empty() && val > m.Back() {
m.queue = m.queue[:len(m.queue)-1]
}
m.queue = append(m.queue, val)
}
        pop(value)
          如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
          func (m *MyQueue) Pop(val int) {
if !m.Empty() && val == m.Front() {
m.queue = m.queue[1:]
}
}
      主函数
        func maxSlidingWindow(nums []int, k int) []int {
queue := NewMyQueue()
length := len(nums)
res := make([]int, 0)
// 先将前k个元素放入队列
for i := 0; i < k; i++ {
queue.Push(nums[i])
}
// 记录前k个元素的最大值
res = append(res, queue.Front())
for i := k; i < length; i++ {
// 滑动窗口移除最前面的元素
queue.Pop(nums[i-k])
// 滑动窗口添加最后面的元素
queue.Push(nums[i])
// 记录最大值
res = append(res, queue.Front())
}
return res
}
  347. 前 K 个高频元素
    题意
      给你一个整数数组 `nums` 和一个整数 `k` ，请你返回其中出现频率前 `k` 高的元素。你可以按 **任意顺序** 返回答案。
      **示例 1：**
        **输入：**nums = [1,1,1,2,2,3], k = 2
        **输出：**[1,2]
      **示例 2：**
        **输入：**nums = [1], k = 1
        **输出：**[1]
      **示例 3：**
        **输入：**nums = [1,2,1,2,1,2,3,1,3,2], k = 2
        **输出：**[1,2]
      **提示：**
        - `1 <= nums.length <= 105`
        - `k` 的取值范围是 `[1, 数组中不相同的元素的个数]`
        - 题目数据保证答案唯一，换句话说，数组中前 `k` 个高频元素的集合是唯一的
    思路
      先用 map 统计元素出现次数
        // 统计元素出现次数
for _, v := range nums {
map_num[v]++
}
      再用切片统计出现过的元素
        // 统计出现过的元素（去重）
for k, _ := range map_num {
ans = append(ans, k)
}
      最后将该切片根据元素出现的次数排序
        // 根据出现频率排序元素
sort.Slice(ans, func(i, j int) bool {
return map_num[ans[i]] > map_num[ans[j]]
})
return ans[:k]