社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
【百度百科】栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。栈也称为后进先出表。
由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。栈也称为后进先出表。
栈可以用顺序存储,也可以用链式存储,分别称为顺序栈和链栈。
@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()); } }
假设表达式中只允许两种括号:()、{};
正确表达顺序为:()或{}或({})或{({}{})}的形式;如{(}或(})或({)}的表达形式均不对。
算法的设计思想:
/** * 此题还可以引申至配对字符符匹配问题,如单引号,双引号匹配问题。 */ 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(" 匹配失败 "); } } }
栈是一个概念上的工具,具体能实现什么功能可以由我们去想象。栈通过提供限制性的访问方法push()和pop(),使得程序不容易出错。
对于栈的实现,我们稍微分析就知道,数据入栈和出栈的时间复杂度都为O(1),也就是说栈操作所耗的时间不依赖栈中数据项的个数,因此操作时间很短。而且需要注意的是栈不需要比较和移动操作,我们不要画蛇添足。
我的微信公众号:架构真经(id:gentoo666),分享Java干货,高并发编程,热门技术教程,微服务及分布式技术,架构设计,区块链技术,人工智能,大数据,Java面试题,以及前沿热门资讯等。每日更新哦!
参考文章
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!