栈主要考察单调栈，队列主要考察优先队列(堆)。
栈和队列(ArrayDeque)
数据结构
ArrayDeque类是双端队列Deque接口的实现类。
Deque的含义是"double ended queue"，即双端队列，它既可以当作栈使用，性能优于Stack，也可以当作队列使用，性能优于LinkedList。
ArrayDeque和LinkedList是Deque的两个通用实现。
具有以下特征：
- ArrayDeque是采用数组方式实现的双端队列。
- ArrayDeque的出队入队是通过头尾指针循环，利用数组实现的。
- ArrayDeque容量不足时是会扩容的，每次扩容容量增加一倍。
- ArrayDeque可以直接作为栈使用。当用作栈时，性能优于Stack，当用于队列时，性能优于LinkedList。
- 非线程安全队列，无同步策略，不支持多线程安全访问。
- 具有fail-fast特性，不能存储null值，支持双向迭代器遍历。
类图
成员变量
transient Object[] elements;
存储元素的数组
transient int head;
队列头位置
transient int tail;
队列尾位置
private static final int MIN_INITIAL_CAPACITY = 8;
一个新创建的队列的最小容量
ArrayDeque从名字看出底层是通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，要求数组必须是循环的，即循环数组。也就是数组的任何一点都可能被看做起点或者终点。另外，该容器不允许存放null元素。底层实现是数组+双指针。
构造函数
- public ArrayDeque(Collection<? extends E> c)：将现有集合元素C加入队列进行构造
- public ArrayDeque(int numElements)：创建一个指定大小的ArrayDeque
- public ArrayDeque()：无参构造方法，创建一个容量为16的ArrayDeque
方法
单调栈O(n)
题目引入
先讲解LeetCode1475. 商品折扣后的最终价格
解法一：暴力法
遍历整个数组，再遍历每个数字的右边所有的数，找到第一个小于或等于当前元素值的元素，减掉即可。
class Solution {
public int[] finalPrices(int[] prices) {
// 题目最终转化为：找到右边第一个比其小的数
for (int i = 0; i < prices.length; i ++) {
for (int j = i + 1; j < prices.length; j ++) {
if (prices[j] <= prices[i]) {
prices[i] -= prices[j];
break;
}
}
}
return prices;
}
}
很明显上述代码的时间复杂度是O(n2)，空间复杂度是O(n)。
现在有一个极限数据：[1, 2, 3, 4, ....., 9999999, 0]，那么这个暴力法将会超时。
我们能不能想出一种时间复杂度为O(n)级别的算法呢？
单调栈的定义
单调栈算法是一种借助"栈"实现的算法，特征为栈内元素按照某种规则(一般为数字大小)单调。
- 单调递增栈：栈中元素从栈底到栈顶是递增的；
- 单调递减栈：栈中元素从栈底到栈顶是递减的；
单调栈是一种算法，不是数据结构。
☆单调栈的应用场景
对于数组中的某个元素，在数组中找到它左侧(或右侧)离它最近的一个比它大(或者比它小)的数字。
单调栈的模板
// 枚举每一个元素
for (int i = 0; i < n; i ++) {
// 每当一个元素即将入栈时，判断一下栈中单调性是否是存在的
// 如果单调性被破坏,当前元素入栈之前更新答案
while (栈不空 && 单调性不存在) {
// 对于单调性不存在的情况，我们需要不断的弹栈
记录此时的答案(更新答案)
stack.pop()
}
// 如果单调性没被破坏，当前元素直接入栈
// 实际存放的是下标,不是元素值
stack.push(i);
}
解法二：单调栈
class Solution {
public int[] finalPrices(int[] prices) {
// 单调递增栈,栈中存放的是索引下标
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < prices.length; i ++) {
while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
prices[stack.peek()] -= prices[i];
stack.pop();
}
stack.push(i);
}
return prices;
}
}
时间复杂度分析：由于每个元素都最多入栈、出栈各一次。
总时间复杂度：O(n + n) = O(2n) ≈ O(n)
开辟一个数组用于返回结果，空间复杂度：O(n)
单调栈的特点：时空复杂度O(n)。
相关题目
LeetCode1475. 商品折扣后的最终价格单调递增栈LeetCode739. 每日温度单调递减栈LeetCode42. 接雨水单调递减栈- LeetCode84. 柱状图中最大的矩形