一、栈 （Stack）
定义：栈是限定在表尾进行插入和删除操作的线性表。
- 栈的插入操作，叫作进栈，也叫压栈、入栈。
- 栈的删除操作，叫作出栈，也叫弹栈。
- 后出先进的方式处理集合
1.常用API：
- Count : 返回元素个数；
- Push() : 入栈的方法；
- Pop() : 出栈的方法，并在该队列中删除该元素；
如果在调用Dequeue()方法时，队列中没有元素，就会抛出异常 - Peek() : 读取一个元素，但不删除它。
2.栈的应用——递归
- 斐波那契数列——兔子繁殖问题
数学函数定义：
- 递归定义——把一个直接调用自己或通过一系列调用语句间接调用自己的函数，称作递归函数。
3.栈的应用——四则运算表达式求值
-
后缀（逆波兰）表示法定义——一种不需要括号的后缀表达法
例：9+(3-1)×3+10÷2，后缀表达：9 3 1 - 3 * + 10 2 / +
(1) 初始化一个空栈；
(2) 后缀表达式，前三个都是数字，9、3、1进栈；
(3) 第四个是 - ，1作为减数，3作为被减数，运算3-1 = 2 ，将2进栈；
(4) 接着是数字 3 进栈；
(5) 后面是 * ，意味着3，2出栈并相乘，得到6进栈；
(6) 接着是 + ，6、9出栈相加，得到15，15进栈；
(7) 接着是10、2进栈；
(8) 后面是 / ，10、2出栈相除，得到5并进栈；
(9)最后是 + ，15，5出栈相加，得到20；
-
中缀表达式转后缀——标准的四则运算表达式即为中缀表达式
例如：9+(3-1)×3+10÷2转化为后缀表达式 9 3 1 - 3 * + 10 2 / +
(1) 初始化一个空栈；
(2) 第一个字符是9，输出9，后面是符号 +，进栈；
(3) 第三个是（ ，是左括号，未配对，进栈；
(4) 第四个字符是 3，输出，总表达式为9 3，接着是 -，进栈；
(5) 接下来是 1，输出，总表达式为9 3 1 ，后面符号是 ）。此时需要去匹配此前的 （ ，所以栈顶依次出栈，并输出，直到（ 出栈为止；输出表达式为 9 3 1 - ；
(6) 接着是数字3，输出，总表达式为9 3 1 - 3；紧接着是 × ，因为此时栈顶符号为 + ，优先级低于 ×，所以不输出；*进栈；
(7) 之后是符号 +，此时当前栈顶元素 * 比这个 + 的优先级高，因此栈中元素出栈并输出，总表达式为 9 3 1 - 3 * + 。然后将当符号 + 进栈，
二、队列 （Queue）
定义：只允许在一段进行插入操作，另一端进行删除操作的线性表。
- 队列是一种先进先出的线性表。
- 允许插入的一端叫做队尾，允许删除的一端叫做队头。
1.常用API
- Count : 返回队列中的元素个数；
- Enqueue() : 在队列的尾端添加一个元素；
- Dequeue() : 在队列的头部添加一个元素，并在该队列中删除该元素；
如果在调用Dequeue()方法时，队列中没有元素，就会抛出一个异常； - Peek() : 在队列头部读取一个元素，但不删除它。
2.循环队列
- 队列顺序存储结构。
- 循环队列定义——把队列头尾相接的顺序存储结构称为循环队列。
网友评论