Queue And Stack

仅说明思路 code in my GitHub repository: click here

整篇博客中我忘记了需要维护内部的size变量，在此进行补充说明

基本实现

队列和栈就是操作受限的数据结构，其底层可以用 LinkedList 也可以用 ArrayList。

如果用 LinkedList 的话很简单，因为LinkedList本身就已经是Deque的实现了，所以直接调 LinkedList 的 API 就行了。

• 队列: FIFO
  push() -> LinkedList.addFirst()
pop() -> LinkedList.RemoveFirst()
• 堆: LIFO
  offer() -> LinkedList.addFirst()
poll() -> Linkedlist.removeLast()
add/remove 同理，只是失败抛出异常

---

如果用 ArrayList 实现Stack的话，仍然也很简单。
因为只涉及单边的操作，直接用ArrayList.add()/remove( size() -1 ) 即可

而如要用数组实现(简单的)Queue，则需要用到环形数组的技巧。
即，当在数组头部进行操作时，ArrayList自己的实现中会进行高消耗的数据搬移，为了优化这一点,ArrayQueue的底层不使用Arraylist，而是手动维护 数组的head和tail索引, 经过一段时间的使用后，索引会达到数组边界，此时则重新更新到开头的起始位置。

我个人将head索引作为ElementIndex，tail作为PositionIndex.
这意味着head指向的位置都是已经存在元素的，而tail指向的位置始终是空的，下一个元素要插入的位置
具体的代码实现只要注意维护上述这一规则即可. 当然，这不是固定的，你可以将head作为positionIndex之类的，或者你对head和tail的初始化设为其他则之后的实现细节也会和我的版本略有不同，但这都是细节问题，核心的思路还是: head + tail

具体的计算就是对数组.length 做取余操作 : tail = (tail + 1) % array.length
或者就是简单的 自增操作 加上一个条件判断: tail++; if(tail == data.length) tail = 0;

补充

若不对ArrayQueue进行动态扩容的话，则该队列的实现是一种循环队列

队列拓展 - 双端队列Deque

双端队列即不受限制的队列，可以在头尾进行add/remove操作，利用其本身特性也能模拟stack。

由于LinkedList本身就是Deque的实现了，所以本段内容讲的是用数组实现的Deque

ArrayDeque

思路不变，还是环形数组，实现上多了一些细节要注意。
其实由于数据结构是和ArrayQueue是一样的，所以一部分的代码的实现也是与ArrayQueue是一致的，

一些需要注意的点在于新添加的Api，这些Api的实现其实就是原Api的镜像
例如实现原本不支持尾部删除，我们要先找到新的tail，此时要注意tail是向数组头部前进的，所以是 tail = (tail -1) % array.length 或者 tail--; if(tail == 0) tail = data.length-1
还有就是其他是镜像的小细节就不赘述了，因为核心思路仍就是 head + tail ,其一为Element，其一为Position

其实用数组实现的Queue或者Deque都还是更抽象的数据结构，我们其实经过上述的实现后发现其底层就是环形数组。

补充1 环形数组中数据搬移或index更新中，使用&运算优化mod操作

当环形数组需要扩容的时候，数组需要reIndex
这是因为有时候last 会在顺序上排到 head的前面，在数据搬移时就要处理这种情况
一种直接的做法就是取模运算 newData[i] = data[(first + i) % data.length];

还有一种使用位运算替换取余运算以提高效率的做法，
该做法本身也是Hashmap内部优化取模操作的做法,或者说这一做法是一种非常常见的对于取余操作的优化方案

该优化方案需要规定被取余数需要是2的整数次幂， 即当b为2的整数次幂时， a % b 可以优化为 a & (b - 1) ,这次的&是二进制数据的与运算

一个Cap可以手动转为2的整数次幂后再赋值为数组的length，该函数本身就不赘述了

补充2 同样使用环形数组作为底层数据结构的RingBuffer

RingBuffer是底层使用ArrayDeque的一种应用，其就是开辟一个数组，然后对其buffer数据进行读取或写入。
同样是为了防止高消耗的数据搬移工作，所以手动维护了bufferData的起始与终止的位置，其分别又作为读操作的开端与写操作的开端

由于数据的写和读操作本身就是SystemArrayCopy实现好了的，所以实现RingBuffer主要的工作是判断index边界的问题，这一点在代码中也进行较为详细的说明了，这里也不赘述了

队列拓展 - 优先级队列

优先级队列将队列中的元素进行了排序，动态地保持了元素的有序性，从而使出队的元素一定是极值元素

说到排序，则就会联想到自平衡的二叉树:红黑树，但java的优先级队列的底层数据结构是二叉堆，这是因为在优先级队列中，我们不需要在队列中进行查询操作，而只有高频的插入与删除。同时，二叉堆的算法实现也很简单。所以选择了二叉堆用于优先级队列的数据结构。

二叉堆在逻辑上可以视作树，但在形式上二叉堆是一个数组。这一点在Github仓库中的代码已经进行说明了，这里不再赘述。这里主要说明其自平衡的算法实现。

当添加一个元素时，直接添加到数组的尾部，然后不断进行比较与swap操作，直至元素达到合适的位置，这一过程一般简称为swim(向上游)

当删除一个元素时，所要删除的其实是固定的第一个作为极值的元素，具体操作是先取出极值元素存储到局部变量用于返回，然后将头尾swap，这样删除的操作就是直接删除数组的尾部了，
接着将新的头元素不断与左右子元素中大的那一个做swap操作，直至新的头元素到了合适的位置，一般将这一过程简称为sink(被swap的节点不断下沉)

队列拓展 - 单调队列

之前介绍的队列，在JDK中都有自己的实现，而单调队列没有。

目标： 在一个queue中 以O(1)的时间复杂度返回其中的极值(min / max)。

实现：在维护一个dataQueue用于保存数据之外，单独维护一个Max/Min Queue
在push时，若当前要push的值比其更满足条件则删除极值Queue中的值，直至不再满足极值条件或极值Queue为空
在poll时，检查当前poll的值是不是极值，若是则同步更新极值Queue即可。 取极值时，直接返回极值Queue中的首个元素即可。

补充，单调队列仿佛和优先级队列的定位重复了，其都是返回队列中的极值元素。
但其区别为：优先级队列直接在内部的数据结构中，对队列中的元素进行了排序，而单调队列保持了元素的入队顺序。优先级队列有jdk的默认实现，其有一定可靠性，很多时候没有要保存元素入队顺序的需求，所以大部分情况下都会使用有间隙队列，而单调队列的使用往往是配合一些其他工具完成一些滑动窗口的问题。

栈拓展 - 单调栈

同样的，当操作一个Stack时，也想做一个拓展的api，完成以O(1)的时间复杂度返回其中的极值(min / max)。

实现也是与队列相类似，在维护一个dataStack用于保存数据之外，单独维护一个Max/Min Stack.
push和pop的逻辑也完全一致，这里不赘述了。

栈拓展 - 频率栈

力扣第 895 题「最大频率栈」要求我们实现一个特殊的数据结构

• 从栈中删除并返回 出现频率最高的元素，如果有多个元素符合条件，则按照栈的规则，后入先出

分析:

1. 每次pop时，需要知道频率最高的元素是什么
2. 如果频率最高的元素有多个，还得知道哪个是最近push进来的元素是哪个

为了实现上述难点，我们要做到以下几点：

1. 肯定要有一个变量 maxFreq 记录当前栈中最高的频率是多少。
2. 我们得知道一个频率 freq 对应的元素有哪些，且这些元素要有时间顺序。
3. 随着 pop 的调用，每个 val 对应的频率会变化，所以还得维持一个映射记录每个 val 对应的 freq。

综上可以得出如下数据结构

class FreqStack {
    int maxFreq;
    HashMap<Integer, Stack<Integer>> freqToVars;
    HashMap<Integer, Integer> valToFreq;
}

具体的实现搞清楚逻辑后就能轻松实现了，
push时 先查该val的freq，然后++ , 接着再存储然后更新各种数据
poll时，根据维护的maxFreq中取值，然后再更新数据，具体看代码，有一些数据更新的细节需要注意

其实该数据结构的实现有点类似于 LRU 缓存淘汰算法的镜像版本。
LRUCache执行删除逻辑时，删除的是频率最低，同频则最先入cache的元素
而最大栈pop的时候是删除 频率最高，同频则最后入栈的元素