基本数据结构
线性结构（linear structure）
- 有序数据项的集合
- 每个数据项都有唯一的前驱和后继（第一个和最后一个除外）
根据数据项增减的方式构成了数据结构
- 栈(Stack)–仅在表尾进行插入和删除操作的线性表
- 队列(Queue)–只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作
- 双端队列(Deque)–限定插入和删除操作在表的两端进行的线性表
- 列表(List)–
栈
进行操作的一端为栈顶，另一端为栈底
栈的特点：后进先出LIFO
栈通过python的实现可以借助list的数据类型
栈的应用
括号匹配–基本思路
括号匹配与之前图灵机的模型有些相似；
- 括号匹配可以用用于爬虫HTML数据的爬取；另外该方法也可通过正则表达式实现。
十进制与二进制的转换
十进制转换二进制是余数的连续求取，并将求得的余数倒过来书写。通过栈后进先出的特性可以实现。
同时由此可以进行十进制到其他进制的转换。当转换的进制为十一禁进制以上时，可以使用数组来保存其中的字母
digits = "0123456789ABC"
表达式转换
根据表达式操作符的的位置分为中缀、前缀和后缀，距离操作数最近的操作符先执行
-
中缀表达式转换为前缀和后缀表达式
将表达式转换为全括号形式，将内部每个运算符移到对应的左括号或右括号处边可以转换为前缀、后缀表达式 -
中缀转后缀算法
从左到右扫描过程中，采用栈来暂存为处理的操作符，当遇到一个新的操作符，就需要跟栈顶的操作符比较下优先级，再行处理。
算法流程
从左到右扫描
- 当遇到操作数，直接输出至列表末尾
- 当遇到左括号压入栈顶
- 当遇到右括号，反复弹出栈顶加入至输出列表末尾，直到碰到左括号
- 当遇到操作符，与栈顶其他操作符比较。栈顶操作符高于或等于它，则将输出栈顶的操作符直到优先级低于它
后缀表达式的求值
后缀表达式的操作符在操作数的后面，因此要暂存操作数,直到碰到操作符才进行运算(从这可以利用栈的特性)
在实际运算时，先弹出的时右操作数然后才是左操作数，对于‘-’和‘/’要注意两个操作数的位置
算法流程
-
创建空栈用于暂存操作数
-
从左到右扫面单词列表
- 如果是操作数，压入栈顶
- 如果是操作符，从栈顶弹出两个操作数，进行计算。（注意操作数的位置）
-
最后扫描结束后，表达式的值被存在栈顶（如果表达式正确，则栈中仅有最后的结果一个元素）