通过栈实现浏览器的前进后退
- 思路就是利用俩个栈,分别记录前进和后退的网页
- 具体实现,准备俩个栈A,B,当浏览器浏览三个网页时,a,b,c,栈一次压入a,b,c,当点击后退c从Az栈出栈进入B栈,点前进时,c从B出栈进入A栈
为什么栈可以实现上述操作呢
1. 因为他有一个特性,先进后出;比如羽毛球筒,放羽毛球,先放进去的球最后才能拿出;同理,先浏览的网页就压入到栈底,最后浏览的网页在栈顶,这样我们后退就会看到刚刚浏览的网页了
2. 说到这里,栈其实和数组很像,而且数组比栈更灵活,按为什么不用数组呢?其实栈其实完全可以用数组取代,但是数组过于灵活,所以用栈做一些限制,防止一些不可控的事情发生
3. 举一个实际例子看出栈入栈,比如说 入栈1 ,2;然后出栈 2,下图是对于栈变化的过程
下面是用代码实现基于数组的栈
import java.util.Arrays;
/**
* 数组实现栈
* @param <T>
*/
//这里使用泛型是为了扩展性,以为这里使用了泛型,但你实际使用时必定会传入实际的类型,比如Integer,那么编译时就会变成Integer,而且也不会要为每一种类型写一遍实现,很方便
class Mystack1<T> {
//实现栈的数组
private Object[] stack;
//数组大小
private int size;
Mystack1() {
stack = new Object[10];//初始容量为10
}
//判断是否为空
public boolean isEmpty() {
return size == 0;
}
//返回栈顶元素
public T peek() {
T t = null;
if (size > 0)
t = (T) stack[size - 1];
return t;
}
public void push(T t) {
expandCapacity(size + 1);
stack[size] = t;
size++;
}
//出栈
public T pop() {
T t = peek();
if (size > 0) {
stack[size - 1] = null;
size--;
}
return t;
}
//扩大容量 这里其实不建议扩容,因为涉及到拷贝之前的数据,还需要重新计算地址,建议初始化时就预估大小
public void expandCapacity(int size) {
int len = stack.length;
if (size > len) {
size = size * 3 / 2 + 1;//每次扩大50%
stack = Arrays.copyOf(stack, size);
}
}
}
public class ArrayStack {
public static void main(String[] args) {
Mystack1<String> stack = new Mystack1<>();
System.out.println(stack.peek());
System.out.println(stack.isEmpty());
stack.push("java");
stack.push("is");
stack.push("beautiful");
stack.push("language");
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
System.out.println(stack.peek());
}
}
栈还有一种比较高级的用法叫递归
1. 不知道你是否听过斐波那契数列,他的每一次结果都是上俩次的和,F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)比如这样一个数列:1、1、2、3、5、8、13、21、34、……;
实际上呢就是不断吧每次计算的需要的条件压入栈中,直到知道最初的结果;比如f(1) = 1,f(2)=2,之后通过这俩个值依次计算出栈中对应的结果得到最终结果,看一下代码;
2.递归就是自己调自己,可以看下下面的实例去理解递归和栈
//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
//
// 注意:给定 n 是一个正整数。
//
// 示例 1:
//
// 输入: 2
//输出: 2
//解释: 有两种方法可以爬到楼顶。
//1. 1 阶 + 1 阶
//2. 2 阶
//
// 示例 2:
//
// 输入: 3
//输出: 3
//解释: 有三种方法可以爬到楼顶。
//1. 1 阶 + 1 阶 + 1 阶
//2. 1 阶 + 2 阶
//3. 2 阶 + 1 阶
//
public static int climbStairs(int n) {
if (n <= 1)
return 1;
if (n < 3)
return n;
//每一次将要计算的公式压入栈中,因为不知道上一次的结果;除非知道上一次计算的结果,比如f(3) = f(2)-f(1)
//这样的代码理解简单,容易写,但是栈时很耗费内存的,内存有限,如果设计栈或者计算量很大很容易内存溢出
//这里就是把每次的结果都压入到栈里。可以结合jvm的去想
return climbStairs(n - 1) + climbStairs(n - 2);
}
版权声明:本文内容来自第三方投稿或授权转载,原文地址:https://blog.51cto.com/u_12550160/2863323,作者:小傻孩丶,版权归原作者所有。本网站转在其作品的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如因作品内容、版权等问题需要同本网站联系,请发邮件至ctyunbbs@chinatelecom.cn沟通。