数据结构:栈与队列的应用及矩阵压缩存储
介绍数据结构中栈与队列的典型应用。栈可用于括号匹配、表达式求值(含中缀转前后缀及计算)、递归过程模拟;队列适用于树的层次遍历与图的广度优先搜索。此外涵盖了一维二维数组存储结构,以及对称、三角、带状、稀疏等矩阵的压缩存储原理。

介绍数据结构中栈与队列的典型应用。栈可用于括号匹配、表达式求值(含中缀转前后缀及计算)、递归过程模拟;队列适用于树的层次遍历与图的广度优先搜索。此外涵盖了一维二维数组存储结构,以及对称、三角、带状、稀疏等矩阵的压缩存储原理。

在代码编写中,若括号不匹配编译器会报错。最后出现的左括号最先被匹配(最里层被外层包裹),符合后进先出(LIFO)性质,可用栈解决。
遵循规则:
遍历字符串,根据字符类型执行入栈或出栈操作,最终判断栈是否为空且无匹配错误。
利用栈的 LIFO 特性可有效检测括号是否成对出现。
操作数为数字,运算符为 +、-、*、/。数学家提出不用括号的表示法,即前缀表达式(波兰表达式)和后缀表达式(逆波兰表达式)。
使用'左优先原则'保证运算顺序唯一。观察运算符优先级和结合性进行转换。
遇到操作数入栈,遇到运算符弹出两个操作数计算后将结果压栈,重复直至得到最终结果。
表达式:AB+CD*E/-F+
步骤 | 栈内容(从底到顶)
---|---
1.A|[A]
2.B|[A,B]
3.+|[A+B]
4.C|[A+B,C]
5.D|[A+B,C,D]
6.*|[A+B,C*D]
7.E|[A+B,C*D,E]
8./|[A+B,(C*D)/E]
9.-|[(A+B)-((C*D)/E)]
10.F|[(A+B)-((C*D)/E),F]
11.+|[((A+B)-((C*D)/E))+F]
转为前缀表达式采用'右优先原则',逻辑与后缀相反。
从右向左扫描,操作数入栈,遇运算符弹栈计算。示例如下:
| 步骤 | 元素 | 栈(从底到顶) | 说明 |
|---|---|---|---|
| 1 | 1 | [1] | 入栈 |
| 2 | 1 | [1,1] | 入栈 |
| 3 | + | [2] | 1+1=2 |
| ... | ... | ... | ... |
后缀和前缀表达式消除了括号依赖,便于计算机处理。
包含括号的中缀表达式转后缀时,需处理括号优先级。
正常无括号形式与加括号形式处理逻辑一致,括号作为界限符控制入栈时机。
通过双栈法或单栈法可实现中缀转后缀并计算。
A 调用 B,B 调用 C,C 结束返回 B,B 结束返回 A。最后调用的函数最先结束,符合后进先出特性。
递归即函数自己调用自己。
递归调用时参数 n 依次减小至 1,返回时依次相乘。
典型递归案例,需注意效率优化。
系统栈自动管理递归调用过程。
先进先出(FIFO):
先进先出(FIFO):
用于进程调度等场景。
涉及线性代数知识。
连续内存空间存储。
分为行优先和列优先两种映射方式。
按常规方式存储。
上下三角区数据重复,只存一个三角区以节约空间。
上三角或下三角区为同一元素,可省略空间。
非零元素集中在对角线附近,其余为 0,可省略大量空间。
有效数据少,按位置排列存储,节约空间。
针对特殊矩阵采用压缩存储可显著降低空间复杂度。

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online