程序员的进阶课-架构师之路（4）-栈
版权声明：本文为博主原创文章，遵循 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 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面试题，以及前沿热门资讯等。每日更新哦！
参考文章
赞 (0)