程序员的进阶课-架构师之路(4)-栈
一、栈的定义
【百度百科】栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(push),删除则称为退栈(pop)。栈也称为后进先出表。
由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(lifo, last in first out)的原理运作。栈也称为后进先出表。
二、栈的示意图
三、栈的实现方式
栈可以用顺序存储,也可以用链式存储,分别称为顺序栈和链栈。
四、java中栈的实现举例
1.利用栈实现字符串逆序
@test public void teststringreversal(){ stack stack=new java.util.stack(); string str="hello world!"; char[] chars = str.tochararray(); for (char c : chars) { stack.push(c); } while (!stack.isempty()) { system.out.print(stack.pop()); } }
2.用栈实现括号匹配
假设表达式中只允许两种括号:()、{};
正确表达顺序为:()或{}或({})或{({}{})}的形式;如{(}或(})或({)}的表达形式均不对。
算法的设计思想:
1)出现左括弧则进栈;
2)出现右括弧则首先检测栈是否为空;
- 若栈空则表明此右括弧多余,表达式不匹配。
- 否则和栈顶数据比较,若匹配则栈顶出栈。
- 否则表明表达式不匹配;
3)最后若栈空,则表明匹配成功;否则表明不匹配。
/** * 此题还可以引申至配对字符符匹配问题,如单引号,双引号匹配问题。 */ public class expstackmatching { public boolean matching(string expression) { if (expression == null || expression == "") { system.out.println("输入表达式为空或没有输入表达式"); } stack<character> stack = new java.util.stack<character>(); for (int index = 0; index < expression.length(); index++) { switch (expression.charat(index)) { case '(': stack.push(expression.charat(index)); break; case '{': stack.push(expression.charat(index)); break; case ')': if (!stack.empty() && stack.peek() == '(') { stack.pop(); } break; case '}': if (!stack.empty() && stack.peek() == '{') { stack.pop(); } } } if (stack.empty()) return true; return false; } public static void main(string[] args) { string expression = "{((1+3)+2+4)+9*7}"; expstackmatching oj = new expstackmatching(); boolean flag = oj.matching(expression); if (flag) { system.out.println("匹配成功!"); } else { system.out.println(" 匹配失败 "); } } }
五、栈的字节码解析
六、我们使用过的栈
- struts2的valuestack(值栈)
- 使用栈实现浏览器的前进和后退
七、栈的总结
栈是一个概念上的工具,具体能实现什么功能可以由我们去想象。栈通过提供限制性的访问方法push()和pop(),使得程序不容易出错。
对于栈的实现,我们稍微分析就知道,数据入栈和出栈的时间复杂度都为o(1),也就是说栈操作所耗的时间不依赖栈中数据项的个数,因此操作时间很短。而且需要注意的是栈不需要比较和移动操作,我们不要画蛇添足。
我的微信公众号:架构真经(id:gentoo666),分享java干货,高并发编程,热门技术教程,微服务及分布式技术,架构设计,区块链技术,人工智能,大数据,java面试题,以及前沿热门资讯等。每日更新哦!
参考文章
上一篇: 二月二吃猪头肉是什么意思