栈
栈是只在尾部做添加和删除的线性表
栈的顺序结构方式
- 栈的顺序存储结构是使用数组实现的,Stack继承了Vector
- 添加元素时
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
首先判断是否需要扩容
然后将elementCount位置即栈顶指针指向的位置,赋值为obj
然后将elementCount++,即栈顶指针上移一格,指向一格空地址
- 删除一个元素
elementCount--;
elementData[elementCount] = null; /* to let gc do its work */
首先将栈顶指针下移一格
然后将指针所指向的位置置空
- Vector和ArrayList的区别
Vector是jdk1.0版的顺序表,当时考虑到要在很多场景使用,添加了大量的同步锁,是线程安全的
但是后来发现,这些线程同步锁很多都用不到
ArrayList是jdk1.2版本的,是去掉了同步锁的Vector
栈的链式结构方式
栈在计算机中的应用
- 链表的倒序
将链表存放到链式结构的栈中,进行入栈操作
s = first;//将链表头结点入栈
stack.top = s;
first = first.next();
- 逆波兰表达式-->中缀表达式-->后缀表达式-->计算方式
9+(3-1)X3+10/2
标准四则运算表达式是中缀表达式
- （输出）9 3 1 | （入栈） + ( - )
- （输出）9 3 1 - 3 | （入栈） + X
- （输出）9 3 1 - 3 X +10 2 | （入栈）+ /
- （输出）9 3 1 - 3 X + 10 2 / + <-- 后缀表达式
- 计算机中首先将中缀表达式转换成后缀表达式
转换方法:数字输出,符号入栈,括号匹配出栈,优先级高入栈,优先级低将栈内符号出栈, - 计算后缀表达式
数字入栈,符号就取两个数字出栈计算后再入栈
9 3 1 | 3-1=2
9 2 3 | 2X3 = 6
9 6 | 9+6 = 15
15 10 2 | 10/2 = 5
15 5 | 15+5 = 20
递归的思想
- 程序调用自身
- 递归的边界条件,在满足边界条件之前,递归前进,满足边界条件之后,递归返回
- 将大型复杂问题分解成与原问题相似的规模小的问题
阶乘
- 前进段:n! = n*(n-1)!
- 边界条件1!=1
- 返回段:无
public Long jc (int n){
if (n<=1){
return 1;
}else {
return n*jc(n-1);
}
}
斐波那契数列
1 1 2 3 5 8
除前两项外,其他项等于前两项之和
- 前进段: f(n) = f(n-2)+f(n-1)
- 边界值:n<=1 n = 1
- 返回段:无
public int fibonaaci(int n){
if (n<=1){
return 1;
}else {
return fibonaaci(n-2)+fibonaaci(n-1);
}
}
汉诺塔
将问题简化成两块砖(n1,n2),3根柱子(start,middle,end)
先将n2移动到middle,再将n1移动到end,再将n2移动到end
- 前进段: f(n-1,1,3,2)//将前面n-1个数据从第一根柱子通过第3根柱子移到第2根柱子
f(1,1,2,3)//第n个数据从第一根柱子通过第2根柱子移到第3根柱子
f(n-1,2,1,3)//前n-1个从第二根柱子通过第1根柱子移到第3根柱子 - 边界值:f(1,1,2,3) = 1--->3
- 返回段:无
public void hannoi(int n,int start,int middle,int end){
if (n<=1){
System.out.println(start+"--->"+end);
}else {
hannoi(n-1,start,end,middle);
System.out.println(start+"--->"+end);
hannoi(n-1,middle,start,end);
}
}
