3.1 栈3.1.1 栈的定义栈Stack是一种只允许在一端进行插入和删除操作的线性表。允许操作的一端称为栈顶另一端称为栈底。栈遵循后进先出LIFOLast In First Out。3.1.2 栈的基本操作操作含义push入栈将元素放入栈顶pop出栈移除并返回栈顶元素peek获取栈顶元素但不删除isEmpty判断栈是否为空size获取栈中元素数量3.1.3 栈的顺序存储使用数组保存栈元素并通过栈顶下标管理入栈、出栈操作。class ArrayStack { private final int[] data; private int top -1; public ArrayStack(int capacity) { data new int[capacity]; } public boolean isEmpty() { return top -1; } public boolean isFull() { return top data.length - 1; } public void push(int value) { if (isFull()) { throw new IllegalStateException(栈已满); } data[top] value; } public int pop() { if (isEmpty()) { throw new IllegalStateException(栈为空); } return data[top--]; } public int peek() { if (isEmpty()) { throw new IllegalStateException(栈为空); } return data[top]; } }其中top -1表示栈为空。入栈前先将top加一。出栈时先读取栈顶元素再将top减一。3.1.4 栈的链式存储链栈使用链表结点保存元素通常在链表头部进行入栈和出栈。特点不需要预先固定数组容量。入栈和出栈通常为 (O(1))。需要额外存储指针。仍可能受到可用内存限制。3.1.5 栈的应用函数调用与递归。括号匹配。- 表达式求值。 - 深度优先搜索。 - 撤销操作。 - 浏览器历史记录中的部分回退机制。本节总结栈的核心是后进先出。入栈和出栈通常都可以在 (O(1)) 时间内完成常用于需要逆序处理或保存执行状态的场景。3.2 队列3.2.1 队列的定义队列Queue是一种只允许在一端插入、另一端删除的线性表。队尾插入元素的一端。队头删除元素的一端。队列遵循先进先出FIFOFirst In First Out。3.2.2 队列的基本操作操作含义offer/enqueue入队poll/dequeue出队peek查看队头元素isEmpty判断队列是否为空size获取队列元素数量具体返回值和异常行为取决于所使用的队列实现。3.2.3 队列的顺序存储普通顺序队列可以使用数组保存元素并维护队头、队尾位置。若仅使用不断递增的数组下标出队后前面的空间可能无法直接复用容易造成假溢出。3.2.4 循环队列循环队列将数组的首尾逻辑连接使队列能够循环使用数组空间。若数组长度为capacity常用的下标更新方法为rear (rear 1) % capacity; front (front 1) % capacity;取模操作可以让下标到达数组末尾后重新回到开头。一种常见实现方式是预留一个空位置队列为空front rear队列为满(rear 1) % capacity front此时实际可存储的最大元素数为 capacity - 1。3.2.5 队列的链式存储链队列通过链表存储元素通常设置队头指针和队尾指针。入队在队尾添加结点。- 出队删除队头结点。 - 空队列时需要同时维护队头和队尾指针。在实现正确的情况下链队列的入队和出队通常都可以在 (O(1)) 时间内完成。3.2.6 队列的应用操作系统任务调度。打印任务排队。- 广度优先搜索。 - 消息队列。 - 缓冲区管理。 - 按到达顺序处理请求。本节总结队列遵循先进先出。循环队列用于复用数组空间链队列通过指针连接结点两者都可以高效实现入队和出队。3.3 栈与队列的比较比较项目栈队列访问原则后进先出先进先出插入位置栈顶队尾删除位置栈顶队头主要操作入栈、出栈入队、出队常见实现数组、链表循环数组、链表常见应用递归、表达式求值、括号匹配任务调度、层序遍历、消息处理本节总结栈和队列都属于受限线性表区别在于插入和删除的位置不同因此形成了不同的数据处理顺序。3.4 双端队列3.4.1 定义双端队列Deque允许在队列的两端进行插入和删除操作。常见操作包括队头插入。- 队尾插入。 - 队头删除。 - 队尾删除。3.4.2 Java 中的双端队列Java 中常用Deque接口表示双端队列ArrayDeque是常见实现类。import java.util.ArrayDeque; import java.util.Deque; public class DequeDemo { public static void main(String[] args) { DequeInteger deque new ArrayDeque(); deque.offerFirst(10); deque.offerLast(20); System.out.println(deque.peekFirst()); System.out.println(deque.peekLast()); deque.pollFirst(); deque.pollLast(); } }常用方法方法含义offerFirst(e)在队头插入offerLast(e)在队尾插入pollFirst()删除并返回队头元素pollLast()删除并返回队尾元素peekFirst()查看队头元素peekLast()查看队尾元素ArrayDeque不允许存储null元素。3.4.3 双端队列的应用实现栈和队列。滑动窗口问题。双向调度。需要在两端灵活操作的数据处理场景。本节总结双端队列兼具两端插入和删除的能力。在 Java 中Deque是接口ArrayDeque是常用实现类。3.5 栈在表达式求值中的应用3.5.1 常见表达式形式表达式类型特点示例中缀表达式运算符位于操作数之间A B前缀表达式运算符位于操作数之前 A B后缀表达式运算符位于操作数之后A B 3.5.2 运算符优先级常见运算符优先级从高到低括号中的表达式。乘法、除法、取余。加法、减法。同一优先级下的运算通常按照运算符结合性处理。具体表达式还需要考虑括号、单目运算符等规则。3.5.3 后缀表达式求值后缀表达式可以借助栈计算。基本步骤从左向右扫描表达式。遇到操作数时将操作数入栈。遇到二元运算符时先弹出右操作数再弹出左操作数。执行运算并将结果重新入栈。扫描结束后栈顶元素为结果。例如3 4 2 *-计算过程3入栈。4入栈。遇到计算3 4 7。7入栈。2入栈。遇到*计算7 * 2 14。最终结果14本节总结栈可以保存尚未完成运算的操作数和运算符。后缀表达式求值时二元运算符需要先取右操作数再取左操作数。3.6 数组与特殊矩阵的存储3.6.1 数组的基本概念1.数组由相同类型的元素组成元素通过下标访问。2.在顺序存储的情况下数组元素通常占据连续的存储空间。3.二维数组可以看作由多个一维数组组成的逻辑结构其实际存储顺序由具体语言和实现决定。3.6.2 特殊矩阵特殊矩阵是具有特定规律的矩阵例如对称矩阵。上三角矩阵。下三角矩阵。对角矩阵。当矩阵中的大量元素具有固定值或可由其他元素推导时可以只存储必要的数据以节省空间。3.6.3 对称矩阵对称矩阵满足a{i,j}a{j,i}因此主对角线两侧的元素可以相互对应只存储其中一侧及主对角线元素即可恢复整个矩阵。3.6.4 稀疏矩阵稀疏矩阵是非零元素数量远少于矩阵元素总数的矩阵。常见存储方式三元组表保存行号、列号和值。十字链表通过链表组织非零元素及其行列关系。压缩稀疏行或列存储常用于科学计算和数值分析。三元组的基本结构行号列号元素值(i)(j)(a_{ij})仅保存非零元素及其位置可以减少稀疏矩阵的存储开销。本节总结数组支持按下标访问特殊矩阵可以利用数学规律压缩存储稀疏矩阵则通过只保存非零元素减少空间占用。第三章重点知识汇总知识点核心内容栈后进先出主要操作是入栈和出栈队列先进先出主要操作是入队和出队循环队列利用取模操作循环使用数组空间链队列通过链表连接元素维护队头和队尾双端队列支持在队头、队尾插入和删除表达式求值使用栈管理操作数及运算过程数组使用下标访问元素对称矩阵利用 (a{ij}a{ji}) 压缩存储稀疏矩阵重点存储非零元素及其位置信息