这是算法记录的第十天，这篇主要是队列相关
对应leetcode题目为225.239.347
225.用队列实现栈
请你仅使用两个队列实现一个后入先出（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]
思路
两个队列
关键是如何实现栈入操作，使得出栈的是最新入队的
定义两个队列，一个用于表示栈，一个用来中转。对于栈入操作，先把x放到queue2里面，再把queue1里面的全都放到queue2，这样就是以x为首的队列，就是把新的放到旧的前面了，实现了栈的效果；最后交换两个队列，queue1此时就是实现的栈。
一个队列
当要入栈的时候就正常加到队列尾，当要出栈的时候就把除了队尾的其他元素全部重新进入队列，这样原来队尾的就成了队首了，实现了栈的后入先出效果
代码
//两个队列的实现
type MyStack struct {
queue1 []int
queue2 []int
}
func Constructor() MyStack {
return MyStack{}
}
func (s *MyStack) Push(x int) {
s.queue2 = append(s.queue2, x)
s.transfer()
}
func (s *MyStack) transfer() {
for len(s.queue1) != 0 {
s.queue2 = append(s.queue2, s.queue1[0])
s.queue1 = s.queue1[1:]
}
//当queue1空了就交换（queue2变成空的了）
s.queue1, s.queue2 = s.queue2, s.queue1
}
func (s *MyStack) Pop() int {
x := s.queue1[0]
s.queue1 = s.queue1[1:]
return x
}
func (s *MyStack) Top() int {
return s.queue1[0]
}
func (s *MyStack) Empty() bool {
return len(s.queue1) == 0
}
239.滑动窗口最大值
给你一个整数数组 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]
思路
初看
这个题初看还比较简单，咋会是hard勒，直接使用一个队列来表示窗口，先入先出也符合滑动效果，只需要求每次窗口里的最大值保存下来最后返回就完事了。
结果按上面思路嘎嘎一做，leetcode直接超时…居然还有用例窗口大小都2w多，这样一算复杂是O(nxk)，一旦窗口过大跟O(n^2)没多大区别了。
超时O(nxk)
func maxSlidingWindow(nums []int, k int) (result []int) {
var win []int
for _, num := range nums {
if len(win) < k-1 {
win = append(win, num)
//减少if-else嵌套，提高可读性
continue
}
win = append(win, num)
//获取窗口中的最大值，这里赋值不能是0，因为可能有负值导致比较错误
max := win[0]
for _, i := range win {
if i > max {
max = i
}
}
result = append(result, max)
//队列出队
win = win[1:]
}
return result
}
分析
所以问题的关键是如何在O(1)的时间内求出窗口中的最大值，此时如果还是一般的队列这是可能实现的了。所以引入一个单调队列，单调的含义就是从队首到队尾，值是单调的，这里题目要求最大值，所以是单调递减，这样队首就始终是窗口内的最大值，每次只需队首出列就行。
实现
具体是如何实现？
双端操作，不同于一般的队列，要满足要求就需要实现双端都能够操作。
设定入队元素是k，对于入队操作，从队尾开始比较k和队列中元素的大小，如果k大于其中的a，就把a从队尾出队，这样操作后虽然队列会小于目标窗口大小，但关键需要的那个最大值会保留在队首。
这样似乎有些窗口里的元素都没入队，那么如何实现窗口和队列的一起滑动？在单调队列对于出队操作需要传入值，这样每次出队的时候都比较一下当前的窗口左端和队首是否相等，若相等说明当前的最大值已经不在窗口里了，需要移除；若不相等，那么说明那个左端已经就在入队时因为较小移出去了，就无需再操作，此时的最大值也还是在窗口中。
代码
type MonotonicQueue struct {
q []int
}
func (mq *MonotonicQueue) push(n int) {
//移除队列中比n小的值
for len(mq.q) > 0 && n > mq.q[len(mq.q)-1] {
mq.q = mq.q[:len(mq.q)-1]
}
//然后把n添加到队尾
mq.q = append(mq.q, n)
}
func (mq *MonotonicQueue) pop(n int) {
//若n等于当前维护队列的队首的话就出队，否则的话就不操作，因为已经不在里面了
if n == mq.q[0] {
mq.q = mq.q[1:]
}
}
func (mq *MonotonicQueue) max() int {
//队首始终保持的是最大的
return mq.q[0]
}
func maxSlidingWindow(nums []int, k int) (result []int) {
win := MonotonicQueue{}
for i := 0; i < len(nums); i++ {
if i < k-1 {
win.push(nums[i])
continue
}
//移进一个元素
win.push(nums[i])
//返回当前单调队列的最大值，也就是那个滑动窗口内的最大值
result = append(result, win.max())
//移除当前窗口的第一个元素（窗口右移）
win.pop(nums[i-k+1])
}
return result
}
347.前k个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
1 <= nums.length <= 105k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
**进阶：**你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
思路
初见
要达到复杂度低于O(nlogn)，那么就不能使用排序了 由于需要比较出现次数，所以考虑使用hash-map结构，同时保存值和出现次数，但需要比较出现次数，比较复杂；考虑维护一个队列，入队的时候就按照出现次数进行排序了，队首始终是最大的，最后只需前k个出队就行（参考上一个题目思路），关键在于如何设计那个特殊队列
分析
上面的思路基本正确，而那个特殊队列就是优先级队列——表面队列实际是堆，建立小顶堆（顶部的值最小），然后遍历map
- 如果堆元素个数小于k，直接放进堆中
- 如果元素个数大于k了，就把当前的与堆顶的比较出现次数的大小，当前更大就弹出堆顶，插入当前值，否则不变
初次遇到看到上面是非常疑惑的，什么是堆？堆的作用是什么？
堆是一棵完全二叉树，树中的每个节点的值都不小于或大于左右孩子的值（大顶/小顶），意思就是每次入堆的时候就会进行大小比较，会自动保证堆顶是最大/最小的。
代码
// MapEntry 一个元素
type MapEntry struct {
key int
value int
}
// IHeap 优先级队列（小顶堆）
type IHeap []MapEntry
func (h IHeap) Len() int {
return len(h)
}
func (h IHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h IHeap) Less(i, j int) bool {
return h[i].value < h[j].value
}
func (h *IHeap) Pop() interface{} {
old := *h
m := old[old.Len()-1]
*h = old[:old.Len()-1]
return m
}
func (h *IHeap) Push(m interface{}) {
*h = append(*h, m.(MapEntry))
}
func topKFrequent(nums []int, k int) []int {
m := map[int]int{}
for _, num := range nums {
m[num]++
}
h := &IHeap{}
heap.Init(h)
//遍历map，将heap先填满
for key, value := range m {
heap.Push(h, MapEntry{key, value})
if h.Len() > k {
heap.Pop(h)
}
}
res := make([]int, k)
for i := 0; i < k; i++ {
res[k-i-1] = heap.Pop(h).(MapEntry).key
}
return res
}
具体实现上是用了go标准库的heap结构进行初始化、入堆、出堆操作，但需要实现Swap和Less方法。
具体的实现细节还需要进一步理解