栈模型
栈是限制插入和删除操作只能在一个位置上进行的表,该位置是表的末端,称为栈的顶(top)。
对栈的基本操作是 push(入栈)和 pop(出栈)
。
栈的实现 (ver.C++)
- 链表 使用一个单向链表,在一个表顶端插入元素来实现 push,删除顶端元素实现 pop
- 数组 较链表实现来说,可能使用数组更为流行。由于使用vector类的back()、push_back()和pop_back()函数,使栈的实现变得更简单
栈的应用
平衡符号
我们的现在使用绝大部分ide,都会对你的代码符号平衡进行检测,但这是如何做到的呢
举个例子, 1. { [ } }
2. { [ ]
3.{ [ ] }
我们很显然能看到
第一种情况 括号不对称
第二种情况 少一个}
第三种情况 正确
我们先创建一个空栈
, 读取你的字符直至文件尾部。如果字符是开放符号 ( { [
,则压入栈中。当遇到封闭符号 ) } ]
,则弹出栈顶,如果弹出的符号并不对应,就会报错(第一种情况)
。当读至文件尾时,栈并不为空,则报错(第二种情况)
,但如果栈是空的,则无错误(第三种情况)
。
后缀表达式(逆波兰记法)使用解析
一般我们使用的高级计算器都会遵循着先乘除后加减的运算规则(除了巨硬),windows的计算器就相当的不敢恭维。他十分忠诚的使用了顺序算术,使得用户体验非常差。
但当你想优化自己的体验时,你会发现先乘除后加减的算法似乎有点麻烦。不要怕,后缀表达式(逆波兰记法)就是解决该算法的优解。
4 + 5 + 6 * 7
是一个中缀表达式,也就是我们通常用的算术表达式。
它的后缀表达式为 4 5 + 6 7 * +
将后缀表达式按顺序 压入栈中,遇到符号时会弹出两个数。
压入 4 ->
压入5 ->
如果遇到了
+ - * /
等符号,将 5 、4依次弹出,执行符号操作,在将结果压入栈中,此处为9,压入栈中 ->压入 6 ->
压入 7 ->
遇到了 * 符号,弹出7、6,执行符号操作 * ,结果为42 ,将42压入栈中->
遇到 + 符号 ,弹出 42 、 9 ,执行符号操作 + ,结果为51 ,将51压入栈中->
至此已经读完表达式,弹出栈中的数值,即为按照运算规则得到的结果。
中缀表达式转后缀表达式 使用解析
后缀表达式的用处在上面已经讲了个大概,那么我们怎么才能将中缀表达式转成后缀表达式呢?
a + b * c + ( d / e + f ) * g
创建一个栈,该栈的用处是存放被挂起的操作符号
按顺序读入表达式
- 读取到 a,输出 a
目前输出结果:a- 读取到 +,将 + 压入栈
目前栈中 :+- 读取到 b,输出 b
目前输出结果:a b- 读取到 * ,因为* 优先级比 + 高,将 * 压入栈中。
目前栈中 :+ *- 读取到 c ,输出c
目前输出结果:a b c- 读取到 + , 因为* 优先级比 + 高,将 * 弹出。栈中剩下 + ,因为两个符号优先级相等,将剩下的 + 弹出,并将 + 压入。
目前栈中 :+ 目前输出结果:a b c * +- 读取到 ( ,它拥有最高优先级,所以 压入栈中
目前栈中 :+ (- 读取到 d ,输出d
目前输出结果:a b c * + d- 读取到 /,虽然栈顶的为 (符号 ,但是只要没读入 )符号 之前,( 符号不会弹出。 所以 /压入栈中
目前栈中 :+ ( /- 读取到 e,输出e
目前输出结果:a b c * + d e- 读取到 + 符号,将 / 弹出,遇到 ( 符号,将 + 压入栈中。
目前栈中 :+ ( + 目前输出结果:a b c * + d e /- 读取到 f,输出 f
目前输出结果:a b c * + d e / f- 现在我们读取到了 ) 符号,弹出栈中符号直到 ( 符号弹出。
注意:() {} [ ]
符号 并不输出
目前栈中 :+ 目前输出结果:a b c * + d e / f +- 读取到 * ,因为* 优先级比 + 高,将 * 压入栈中。
目前栈中 :+ *- 读取到 g ,输出 g
目前输出结果:a b c * + d e / f + g- 至此表达式读取完毕,弹出栈中所有符号
目前输出结果:a b c * + d e / f + g * +
一个中缀表达式就转换成一个后缀表达式了
关于代码实现部分
详见 计算器的c++实现
队列(queue)
关于队列并没有许多知识点。
队列基本操作是
enqueue (入队)
在队的末端插入一个元素dequeue (出队)
删除队头的一个元素
队列的数组实现思路
我们创建一个vector 以及 位置 front(头) 和 back (尾) 储存元素个数 cnt ;
当我们enqueue 一个元素 x 时 使vector[back] = x; back = back + 1; cnt = cnt+1;
同理当我们 dequeue 时, 返回vector[front] = x;front = front+1;cnt = cnt-1
但这种写法有着潜在风险,即会造成越界的情况。
我们可以实现一个循环数组,当 front 或者 back 到达数组尾端时,将其回到开头。
- 本文作者: TangZ
- 本文链接: http://wstzj.github.io/2020/07/14/学习笔记-栈/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!