- 栈里面的元素在内存中是连续分布的么？
答：不连续，python中collections.deque双向队列，用双向链表实现，而链表在内存中非连续分布。
deque的pop和apend时间复杂度O(1),而list的pop和insert时间复杂度O(n)
deque支持从两端添加和删除元素，所以既可以用作队列，也可以用作栈。
-
用栈实现队列
输入栈，输出栈，用List表示
pop时，输出栈有值，直接弹出；输出栈为空，把输入栈所有值加入输出栈，再从输出栈弹出 -
用队列实现栈
双队列deque实现，
一个队列为主，另一个队列为辅
pop时，把主队列的除队尾的元素都加入辅助队列；把主队列和辅助队列交换，此时辅助队列中只有最后一个进入的元素，弹出辅助队列元素
括号匹配
用栈，匹配左括号时，右括号先入栈，只需要比较当前元素与栈顶是否相等， 当遍历完字符串且stack为空，括号完全匹配。
括号不匹配的3中情况：
- 左括号多余
- 无多余，但括号类型不匹配
- 右括号多余
字符串去重
逆波兰表达式逆波兰表达式
队列经典题目 滑动窗口最大值滑动窗口最大值
用deque双头队列实现单调队列，即递增或递减的队列，pop和push不同场景不同写法
求前K个高频元素
python中借用库函数heapq，实现小顶堆，用小顶堆来实现优先级队列
求前k大，用小顶堆
求前K小，用大顶堆
- 先用dict实现数字与频次的映射
- 用小顶堆对频次排序
- 倒序输出小顶堆
