前缀表达式 -+abc/de
中缀表达式 a+bc-d/e
后缀表达式 abc*+de/-
堆栈（stack）:具有一定操作约束的线性表，只在一端（栈顶：Top）做插入、删除
插入数据：入栈（push）
删除数据：出栈（pop）
后入先出：Last In First Out（LIFO）
堆栈操作：
1、Stack CreateStack(int MaxSize)：生成空堆栈，最大长度为MaxSize
2、int IsFull(Stack S,int MaxSize)：判断堆栈S是否已满
3、void Push(Stack S,ElementType item)：将元素item压入堆栈
4、int isEmpty(Stack S)：判断堆栈是否为空
5、ElementType Pop(Stack S)：删除并返回栈顶元素
堆栈的链式存储实现
实际就是一个单链表，叫做链栈，栈顶指针Top应该在链表的头部（尾部则Pop操作无法完成）
数组大小固定，链表不固定
中缀表达式求值
解决方法：中缀表达式通过堆栈转化为后缀表达式，求值 （T(N) = O(N)）
转化方法：
1、运算数：直接输出
2、左括号：压入堆栈
3、右括号：将栈顶的运算符弹出并输出，直到遇到左括号（左括号出栈，不操作）
4、运算符：
1、优先级大于栈顶运算符时、压栈
2、优先级小于栈顶运算符时，将栈顶运算符弹出并输出，并对新的栈顶运算符做相同比较直到大于栈顶运算符优先级，然后将新运算符压栈
5、各运算符操作完毕，将堆栈中的剩余运算符一并输出
例：
3+2*((8+12)/10)-(100/5)
3 2 8 12 + 10 / * + 100 5 / -
-13
堆栈应用：
1、函数调用及递归实现
2、深度优先搜索(?
3、回溯算法(? 老鼠走迷宫?
网友评论