数据结构笔记（线性结构->堆栈）

前缀表达式 -+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、回溯算法(? 老鼠走迷宫?