一、栈
1.1 概述
Java为什么要有集合类: 临时存储数据。
链表的本质: 对象间通过持有和引用关系互相关联起来。
线性表: 普通线性表, 操作受限线性表(某些操作受到限制 –> 某一个线性表它的增删改操作受到限制) –> 栈 & 队列
1.1.1 线性表的概念
（1）线性表：n个数据元素的有序序列。
①首先，线性表中元素的个数是有限的。
②其次，线性表中元素是有序的。
（2）那这个”序”指的是什么呢？
①除表头和表尾元素外，其它元素都有唯一前驱和唯一后继，其唯一前驱或唯一后继确定了该元素在线性表中的位置。
②因此，线性表中，每个数据元素都有一个确定的位序，这个确定的位序我们称之为索引。 表头元素有唯一后继，无前驱，表尾元素有唯一前驱，无后继。
1.1.2 栈的概念
栈是一种”操作受限”的线性表，体现在只能在一端插入和删除数据，符合FILO的特性。
FILO: 先进后出,
LIFO: 后进先出
1.1.3 栈的应用
线性表和哈希表在以后工作中会最常用。
栈在实际工作中不常用
应用场景：
1.函数调用栈
2.反序字符串: 实现reNumber(str)方法,反转字符串(附代码) 。
public class DemoStack1 {
public static void main(String[] args) {
String str = "123456789";
String reStr = reStr(str);
System.out.println(reStr);
}
// 栈先进后出
public static String reStr(String str){
MyArrayStack<Character> stack = new MyArrayStack<>();
for (int i = 0; i < str.length(); i++) {
stack.push(str.charAt(i));
}
StringBuffer buffer = new StringBuffer();
// 1 2 3 4 5 6 7 8 9
while (!stack.isEmpty()){
Character pop = stack.pop();
buffer.append(pop);
}
ret<p style="color:transparent">本文来源gao!%daima.com搞$代*!码网1</p>urn buffer.toString();
}
}
3.括号匹配问题: 实现judgeBracket(str)方法来判断括号匹配 （附代码）。
public class DemoStack2 {
public static void main(String[] args) {
String str = "public class) DemoStack2 {public static void main(String[] args) {}}";
boolean bool = judgeBracket(str);
System.out.println(bool);
}
public static boolean judgeBracket(String str){
MyArrayStack<Character> stack = new MyArrayStack<>();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
// 判断c 是left括号, 然后入栈
if (c == '{'){
stack.push('}');
} else if (c == '['){
stack.push(']');
}else if (c == '('){
stack.push(')');
} else if (c == '}' || c == ')' || c == ']'){
Character pop = stack.pop();
if (c != pop){// 不匹配
return false;
}
}
}
return stack.isEmpty();
}
}
4.编译器利用栈实现表达式求值
5.浏览器的前进后退功能
6. 利用栈实现 DFS: depth-first-search 深度优先遍历(树 图)
编译器利用栈实现表达式求值
中缀表达式: 2 + 3 * 2 给人看的 , 运算符放到中间
前缀表达式: + 2 * 3 2 运算符放到之前
后缀表达式: 2 3 2 * + 运算符放到后面
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：Java数据结构学习之栈和队列
转载请注明原文链接：Java数据结构学习之栈和队列
