栈
栈：一种遵循后进先出(Last-In-First-Out，LIFO)原则的线性数据结构，在Java中，Stack 是一个类，它继承自 Vector 类，不过实际开发中也常使用实现了 Deque 接口的 LinkedList 类来充当栈的角色，它们都提供了处理栈。
使用Stack
Stack<Integer> stack = new Stack<>();
Character.isDigit(字符名)判断是否是数字
Character.isLetter(字符名)和Character.isAlphabetic(字符名)，前者判断字符是否是字母，后者判断字符是否是字母表中的字符(前者子集，比前者少了看起来像字母或数字与一些特殊格式的字母变体，比如罗马数字、带圈字母、计量单位den)
Character.isUpperCase(字符名)、Character.isLowerCase(字符名)判断是否是大写或小写字符’
!Character.isLetterOrDigit(字符名) && !Character.isWhitespace(字符名)判断字符不是数字、字母、空白符
Stack 基于动态数组实现，数组在内存中是连续存储的，每个元素可以通过索引直接访问。栈遵循后进先出(LIFO)的原则，主要操作有入栈(push)、出栈(pop)、查看栈顶元素(peek)等。
时间复杂度：
入栈操作-push(E item)：
正常情况下，当数组还有剩余空间时，直接将元素添加到数组末尾，时间复杂度为O(1)。当数组空间不足时，需要进行扩容操作，即创建一个更大的新数组，并将原数组中的元素复制到新数组中，这个过程的时间复杂度为O(n)，但扩容操作不是每次入栈都会发生，平均情况下，入栈操作的时间复杂度仍可看作O(1)。
出栈操作-pop()：
正常情况下，直接移除并返回数组的最后一个元素，时间复杂度为O(1)。因为栈顶元素就是数组的最后一个元素，可直接访问和移除。
查看栈顶元素-peek()：
直接返回数组的最后一个元素，不进行移除操作，时间复杂度为O(1)。由于数组的最后一个元素位置固定，可直接访问。
根据索引访问元素-elementAt(int index)：
由于数组支持随机访问，可通过索引直接访问指定位置的元素，时间复杂度为O(1)。例如要访问栈中第 index 个元素，可直接通过数组的索引定位到该元素。
查找指定元素-search(Object o)：
需要从栈顶开始依次遍历数组，查找指定元素第一次出现的位置。最坏情况下要遍历整个数组，时间复杂度为O(n)。因为在遍历过程中，需要逐个比较元素是否与目标元素相等。
删除指定对象-removeElement(Object obj)：
首先需要遍历数组找到该元素，最坏情况下要遍历整个数组，时间复杂度为O(n)。找到元素后，还需要将该元素后面的所有元素向前移动一位，以填补删除元素后的空缺，这个移动操作的时间复杂度也为O(n)，所以总体时间复杂度为O(n)。
Stack相关方法：
入栈：
push(E item)：将指定的元素压入栈顶，并返回该元素。
出栈：
pop()：移除栈顶元素并返回该元素。如果栈为空，会抛出EmptyStackException异常。
查看栈顶元素：
peek()：返回栈顶元素，但不移除它。如果栈为空，会抛出EmptyStackException异常。
判断栈是否为空：
empty()：判断栈是否为空，如果栈中没有元素，返回true；否则返回false。
返回在栈顶的位置：
search(Object o)：返回指定元素在栈中的位置，栈顶元素的位置为 1。如果元素不在栈中，返回 -1。(LinkedList中没有)
查看栈中元素数量：
size()：返回栈中元素数量。
清空栈：
clear()：清空栈，该方法会移除栈中的所有元素，使栈变为空栈
使用LinkedList
LinkedList<Integer> stack = new LinkedList<>();
LinkedList 基于双向链表实现，链表中的节点在内存中是离散存储的，每个节点包含数据以及指向前一个节点和后一个节点的引用。当使用LinkedList实现栈时，遵循后进先出(LIFO)的原则。
时间复杂度：
入栈操作-push(E e) 或 addFirst(E e)：
正常情况下，将元素添加到链表的头部。由于链表可以直接通过头节点引用进行操作，不需要遍历链表，时间复杂度为O(1)。
出栈操作-pop() 或 removeFirst()：
直接移除并返回链表的头部元素，因为可以直接通过头节点引用进行操作，不需要遍历链表，时间复杂度为O(1)。
查看栈顶元素-peek() 或 getFirst()：
直接返回链表的头部元素，不进行移除操作，由于可以直接通过头节点引用访问元素，时间复杂度为O(1)。
根据索引访问元素-get(int index)：
由于链表不支持随机访问，需要从链表的头节点或尾节点开始依次遍历，直到找到第 index 个节点，平均时间复杂度为O(n)。
查找指定元素-indexOf(Object o)：
需要从链表头开始依次遍历链表，查找指定元素第一次出现的位置。最坏情况下要遍历整个链表，时间复杂度为O(n)。
删除指定对象-remove(Object o)：
首先需要遍历链表找到该元素，最坏情况下要遍历整个链表，时间复杂度为O(n)。找到元素后将其从链表中移除，移除操作本身时间复杂度是O(1)，所以总体该方法时间复杂度是O(n)。
LinkedList相关方法：
入栈：
push(E item)：将指定的元素压入栈顶，并返回该元素。
addFirst(E e)：将指定元素插入此列表的开头。虽然它不是专门为栈操作设计的，但同样可以实现入栈的效果。
出栈：
pop()：移除栈顶元素并返回该元素。如果栈为空，会抛出EmptyStackException异常。
removeFirst()：移除并返回此列表的第一个元素。如果列表为空，该方法会抛出NoSuchElementException异常。
查看栈顶元素：
peek()：返回栈顶元素，但不移除它。如果栈为空，会抛出EmptyStackException异常。
getFirst()：返回此列表的第一个元素。如果列表为空，该方法会抛出NoSuchElementException异常。
判断栈是否为空：
isEmpty()：判断栈是否为空，如果栈中没有元素，返回true；否则返回false。
查看栈中元素数量：
size()：返回栈中元素数量。
清空栈：
clear()：清空栈，该方法会移除栈中的所有元素，使栈变为空栈
使用ArrayDeque
ArrayDeque<Integer> stack = new ArrayDeque<>();
ArrayDeque 基于可调整大小的循环数组实现，通过维护头指针和尾指针来高效地支持双端操作。当使用ArrayDeque实现栈时，遵循后进先出(LIFO)的原则。
时间复杂度：
入栈操作-push(E e) 或 addFirst(E e)：
正常情况下，将元素添加到数组的前端（模拟栈顶）。如果数组还有空间，直接在当前头指针位置插入元素，然后更新头指针，时间复杂度为O(1)。当数组空间不足时，需要进行扩容操作，即创建一个更大的新数组，并将原数组中的元素复制到新数组中，这个过程的时间复杂度为O(n)。但扩容操作不是每次入栈都会发生，平均情况下，入栈操作的时间复杂度仍可看作 O(1)。
出栈操作-pop() 或 removeFirst()：
直接移除并返回数组前端（栈顶）的元素，然后更新头指针。由于可以直接通过头指针访问和移除元素，不需要遍历数组，时间复杂度为O(1)。
查看栈顶元素-peek() 或 peekFirst()：
直接返回数组前端（栈顶）的元素，不进行移除操作。通过头指针可以直接访问元素，时间复杂度为O(1)。
根据索引访问元素-get(int index)：
由于 ArrayDeque 是基于数组的，虽然是循环数组，但仍然支持随机访问。可以通过计算索引在循环数组中的实际位置，直接访问指定位置的元素，时间复杂度为O(1)。
查找指定元素-indexOf(Object o)：
需要从数组的前端开始依次遍历数组，查找指定元素第一次出现的位置。最坏情况下要遍历整个数组，时间复杂度为O(n)。
删除指定对象-remove(Object o)：
首先需要遍历数组找到该元素，最坏情况下要遍历整个数组，时间复杂度为O(n)。找到元素后，还需要移动后续元素来填补空缺，这也需要O(n) 的时间复杂度(因为可能需要移动多个元素)，所以总体时间复杂度为O(n)。
ArrayDeque相关方法：
入栈：
push(E item)：将指定的元素压入栈顶，并返回该元素。
addFirst(E e)：将指定元素插入此列表的开头。虽然它不是专门为栈操作设计的，但同样可以实现入栈的效果。
出栈：
pop()：移除栈顶元素并返回该元素。如果栈为空，会抛出EmptyStackException异常。
removeFirst()：移除并返回此列表的第一个元素。如果列表为空，该方法会抛出NoSuchElementException异常。
查看栈顶元素：
peek()：返回栈顶元素，但不移除它。如果栈为空，会抛出EmptyStackException异常。
getFirst()：返回此列表的第一个元素。如果列表为空，该方法会抛出NoSuchElementException异常。
判断栈是否为空：
isEmpty()：判断栈是否为空，如果栈中没有元素，返回true；否则返回false。
查看栈中元素数量：
size()：返回栈中元素数量。
清空栈：
clear()：清空栈，该方法会移除栈中的所有元素，使栈变为空栈想用栈 (LIFO)：就严格使用 push() + pop() + peek()。
想用队列 (FIFO)：就严格使用 offer() (或 add()) + poll() (或 remove()) + peek()。
双端队列高级用法：offerFirst(e) / offerLast(e) pollFirst() / pollLast() peekFirst() / peekLast()
单调栈
单调栈是一种特殊的栈结构，它要求栈中的元素保持单调递增或单调递减的顺序，单调递增栈是指栈内元素从栈底到栈顶是单调递增的，单调递增栈是指栈内元素从栈底到栈顶是单调递减的。当新元素入栈时，如果破坏了栈的单调性，则需要将栈顶元素出栈，直到满足单调性为止。
// 单调递增栈示例
public class MonotonicIncreasingStack {
public static void main(String[] args) {
int[] arr = {3, 1, 4, 2};
// 声明一个基于 ArrayDeque 实现的栈
ArrayDeque<Integer> stack = new ArrayDeque<>();
for (int num : arr) {
// 当栈不为空且栈顶元素大于当前元素时，出栈
while (!stack.isEmpty() && stack.peek() > num) {
stack.pop();
}
// 将当前元素入栈
stack.push(num);
}
}
}
