02. 栈、队列和数组

栈、队列和数组

1. 栈和队列的基本概念

• 栈：后进先出（LIFO），只允许在一端（栈顶）插入和删除
• 队列：先进先出（FIFO），一端插入（队尾），一端删除（队头）

2. 存储结构

• 顺序存储结构：用数组实现，空间连续，支持随机访问
• 链式存储结构：用链表实现，空间灵活，插入/删除高效
• 栈的顺序/链式实现，队列的顺序/链式实现（循环队列）

3. 多维数组的存储

• 多维数组在内存中按行优先或列优先线性存储
• 计算元素地址公式

4. 特殊矩阵的压缩存储

• 对称矩阵、三角矩阵、稀疏矩阵等可用一维数组压缩存储
• 节省空间，提高效率

5. 应用

• 栈：表达式求值、递归、括号匹配、函数调用
• 队列：缓冲区、操作系统调度、图的广度优先搜索
• 数组：数据存储、查找、排序、矩阵运算

练习题

1. 简述栈和队列的主要区别。
2. 如何用数组实现循环队列？
3. 多维数组在内存中的存储方式是什么？
4. 举例说明栈和队列的典型应用。
5. 稀疏矩阵如何压缩存储？