文章目录

• 堆栈
• 引入
• 堆栈和线性表的区别

堆栈

定义：一种数据项按序排列的数据结构,只能在一端(称为栈顶(top))对数据项进行插入和删除。堆栈是一种线性结构，也是特殊的一种线性表。

---

引入

堆栈的用途很广，例如函数调用、递归、计算表达式都需要用到堆栈，我们以表达式进行引入

中缀表达式

定义：一个通用的算术或逻辑公式表示方法。运算符在两个运算符之间。

中缀表达式适合人的运算方法，不适用计算机

前缀表达式

定义：前缀表达式是一种没有括号的算术表达式。运算符写在运算数的前面，又称波兰式

后缀表达式

定义：逆波兰式又称后缀表达式。运算符在运算数后面

中缀表达式转前缀表达式

• 前缀表达式是从左往右扫描表达式，入栈也是从右往左
• 运算符不入栈，出栈从左往右

中缀表达式：（A+B)*(C-D)/(E-F*G)  写成带括号的表达式   ((A+B)*(C-D))/(E-(F*G))
前缀表达式： /*+AB-CD-E*FG

	出栈就是将前缀表达式转为中缀表达式

中缀表达式转后缀表达式

• 从左往右进栈
• 运算符不入栈，从右往左出栈

中缀表达式：（A+B)*(C-D)/(E-F*G)  写成带括号的表达式   ((A+B)*(C-D))/(E-(F*G))
后缀表达式：	AB+CD-*EFG*-/

计算机一般用后缀表达式进行表达式运算

---

堆栈和线性表的区别

• 只在一端(栈顶，Top)做插入、删除
• 插入数据：入栈
• 删除数据：出栈
• 先入后出原则

---