技术好文共享:程序员的进阶课

简介: 技术好文共享:程序员的进阶课

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。


本文链接:


一、栈的定义


【百度百科】栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。


栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。栈也称为后进先出表。


由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。栈也称为后进先出表。


二、栈的示意图


三、栈的实现方式


栈可以用顺序存储,也可以用链式存储,分别称为顺序栈和链栈。


四、Java中栈的实现举例


1.利用栈实现字符串逆序


@Test


public void testStringReversal(){


Stack stack=new java.util.Stack();


String //代码效果参考:http://www.lyjsj.net.cn/wx/art_24009.html

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("输入表达式为空或没有输入表达式");


//代码效果参考:http://www.lyjsj.net.cn/wx/art_24007.html

}

Stack stack = new java.util.Stack();


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)+97}";


ExpStackMatching oj = new ExpStackMatching();


boolean flag = oj.matching(expression);


if (flag) {


System.out.println("匹配成功!");


} else {


System.out.println(" 匹配失败 ");


}


}


}


五、栈的字节码解析


六、我们使用过的栈


Struts2的ValueStack(值栈)


使用栈实现浏览器的前进和后退


七、栈的总结


栈是一个概念上的工具,具体能实现什么功能可以由我们去想象。栈通过提供限制性的访问方法push()和pop(),使得程序不容易出错。


对于栈的实现,我们稍微分析就知道,数据入栈和出栈的时间复杂度都为O(1),也就是说栈操作所耗的时间不依赖栈中数据项的个数,因此操作时间很短。而且需要注意的是栈不需要比较和移动操作,我们不要画蛇添足。


参考文章

相关文章
|
人工智能 分布式计算 Java
【C++初阶】前言——C++的发展简述及学习方法分享
之前我们一直分享C语言和使用C语言完成数据结构的初阶的文章,今天我们正式进入C++的学习,这篇文章主要是给大家带来的是C++的由来、以及和C语言的区别、更主要的是和大家分享自己的学习方法,给一些我的建议。
|
2月前
|
机器学习/深度学习 人工智能 Kubernetes
技术探索之旅:从基础到进阶的心得体会
本文记录了作者在技术领域的学习和实践过程中积累的经验与感悟。文章涵盖了从基础知识的学习、项目实践,到新技术的探索与应用,最终总结出几点对未来技术发展的思考。希望这些分享能够启发更多的技术爱好者,共同进步。
|
7月前
|
算法 Swift 开发者
【Swift开发专栏】Swift开发者的进阶之路:从新手到专家
【4月更文挑战第30天】本文介绍了Swift开发者从基础到专家的成长路径,包括掌握语言基础如语法、数据结构、错误处理和内存管理;深入学习Apple框架如UIKit、Core Data和CloudKit;关注性能优化、架构设计及网络与安全编程;以及持续学习新技术,参与开源项目,建立专业网络。通过不断学习和实践,开发者可逐步成为Swift专家。
190 0
|
4月前
|
运维 网络协议 API
入门网络,少不了这份详细的网络基础学习指南!
入门网络,少不了这份详细的网络基础学习指南!
|
7月前
|
IDE 测试技术 Go
【字节跳动青训营】后端笔记整理-3 | Go语言工程实践之测试
用于验证已经修改或新增功能后,软件的既有功能是否受到影响。
130 2
|
7月前
|
前端开发 程序员 开发工具
2024年最全0基础程序员如何快速进阶成为编程老司机?_码农速成(2),字节跳动面试攻略
2024年最全0基础程序员如何快速进阶成为编程老司机?_码农速成(2),字节跳动面试攻略
2024年最全0基础程序员如何快速进阶成为编程老司机?_码农速成(2),字节跳动面试攻略
|
存储 运维 算法
嵌入式进阶从小白到大神学习全攻略(学习路线+课程+学习书籍+练习项目)
嵌入式进阶从小白到大神学习全攻略(学习路线+课程+学习书籍+练习项目)
|
架构师 Java 中间件
阿里内部从初级程序员到架构师学习路线+配套学习资源
阿里巴巴终于公开了从初级程序员到架构师的学习路线图,这里相对应的基本上就是从P5到P8的晋升体系!今天老师将会带着大家从初级程序员开始一点点分享整个晋升体系!
|
前端开发 JavaScript IDE
程序员成长第二篇:如何快速入门
程序员成长第二篇:如何快速入门
133 0
|
程序员 测试技术 开发工具
程序员成长第十篇:从阅读代码开始
程序员成长第十篇:从阅读代码开始
200 0