1. 栈
1. 概念
2. 栈的使⽤
Stack<E> name = new Stack<>();<E> 是一个类型参数，表示栈中存储的元素类型。
必须判空：在调用
pop()或peek()之前，必须使用isEmpty()方法检查栈是否为空。避免异常：判空可以避免
EmptyStackException，提高代码的健壮性。最佳实践：始终在操作栈之前检查栈的状态，确保程序能够正确处理边界情况。
3. 栈的底层实现
（1）数组实现
java.util.Stack：这是Java提供的一个栈类，其底层是基于数组实现的。它继承自Vector类，而Vector是一个动态数组。Stack是线程安全的特点：
数组实现的栈在扩容时需要复制数组，效率较低。
但数组实现的栈在访问元素时速度较快，因为数组是连续存储的。
出栈和入栈的时间复杂度都为O(1)
java.util.ArrayDeque：基于数组实现的双端队列，也可以用作栈。线程不安全
（2）链表实现
自定义栈：可以使用
java.util.LinkedList来实现栈1. 单链表
- 1.1 头插和头删
通过调用
LinkedList的addFirst()和removeFirst()方法，可以模拟栈的push和pop操作。链表实现的栈不需要扩容，出栈和入栈的时间复杂度为O(1)。
1.2 尾插和尾删
通过调用
LinkedList的addLast()和removeLast()方法，可以模拟栈的push和pop操作。链表实现的栈不需要扩容，入栈的时间复杂度为O(1),出栈的时间复杂度为O(n),因为需要遍历完整个链表。
2. 双链表
-
不需要扩容，不管从哪边出栈和入栈时间复杂度都为O(1)。
使用数组模拟实现栈
2. 队列
1 概念
2. 队列的使用
import java.util.Queue;
import java.util.LinkedList;
Queue<E> queue1 = new LinkedList<>();//基于双链表实现
import java.util.Queue;
import java.util.ArrayDeque;
Queue<E> queue2 = new ArrayDeque<>();//基于动态数组实现
| 操作类型 | 方法 | 功能 | 队列为空/满时的行为 | 中文解释 |
|---|---|---|---|---|
| 插入 | add(E e) |
添加元素到队列尾部 | 队列已满时抛出异常 | 强制添加，可能抛异常 |
| 插入 | offer(E e) |
添加元素到队列尾部 | 队列已满时返回 false |
安全添加，不抛异常 |
| 移除 | remove() |
移除并返回队头元素 | 队列为空时抛出异常 | 强制移除，可能抛异常 |
| 移除 | poll() |
移除并返回队头元素 | 队列为空时返回 null |
安全移除，不抛异常 |
| 检查 | element() |
返回队头元素（不移除） | 队列为空时抛出异常 | 强制获取，可能抛异常 |
| 检查 | peek() |
返回队头元素（不移除） | 队列为空时返回 null |
安全获取，不抛异常 |
队列的模拟实现（基于双链表）
3. 循环队列
1. 数组下标循环的小技巧
%)，可以确保数组下标在超出数组长度时循环回到起始位置，从而实现 循环访问。
array.length 的数组，当前下标为 index，需要向后移动 offset 个位置。由于数组是循环的，当 index + offset 超出数组长度时，通过取模运算将其映射回数组的有效范围内。
array.length 的数组，当前下标为 index，需要向前移动 offset 个位置。由于数组是循环的，当 index - offset 小于 0 时，通过取模运算将其映射回数组的有效范围内。
2. 如何区分空与满
1. 通过添加 size 属性记录
初始状态：
front和rear都指向 0。
size初始化为 0。队列空：
size == 0。队列满：
size == capacity。入队操作：
检查队列是否已满。
如果未满，将元素放入
rear位置，并移动rear指针。增加
size。出队操作：
检查队列是否为空。
如果不为空，取出
front位置的元素，并移动front指针。减少
size。
2. 使⽤标记
初始状态：
front和rear都指向 0。
isFull设置为false，表示队列为空。入队操作：
检查
rear是否与front重合：
如果重合且
isFull为true，表示队列已满，无法入队。如果重合但
isFull为false，表示队列为空，可以入队。如果
rear与front不重合，正常入队并移动rear。如果
rear移动后与front重合，设置isFull = true。出队操作：
移动
front指针。设置
isFull = false（因为出队后队列不可能满）。判断队列空和满：
队列空：
front == rear且isFull == false。队列满：
front == rear且isFull == true。
3. 保留⼀个位置
初始状态：
front和rear都指向 0。队列中保留一个空位，因此实际可用容量为
capacity - 1。队列空：
front == rear。队列满：
(rear + 1) % capacity == front。入队操作：
检查队列是否已满。
如果未满，将元素放入
rear位置，并移动rear指针。出队操作：
检查队列是否为空。
如果不为空，取出
front位置的元素，并移动front指针。
3. 代码示例
4. 双端队列
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现例题分析
1. 栈
