浏览器前进后退功能的简单实现 浏览器前进后退功能的简单实现

发表于

浏览器前进后退功能的简单实现

这是我参与11月更文挑战的第4天，活动详情查看：2021最后一次更文挑战

笔者最近在学习《数据结构与算法之美》，正好借着这个机会边练习边记录一下自己学习的知识点。不啰嗦，直接开始。

假设我们依次浏览了页面 A、页面 B、页面 C 和 页面D，当我们在页面 D 点击浏览器的后退按钮时，浏览器会返回放上一次浏览的页面 C，此时再点击前进按钮则会返回到页面 D。这就是浏览器的前进和后退功能，让我们能够随意的返回前一个页面和后一个页面，那么这个功能是如何实现的呢？这里我们先按下不表，先看看栈这种数据结构。

一、什么是栈

  • 栈也是线性数据结构
  • 栈是一种操作受限的线性表，只允许在一端对数据进行操作。
  • 正因为只能在一端进行操作，也造就了栈具有的后进先出的特点，也即后加入的数据，先被移除出去。就像是餐厅叠在一起的盘子，新洗好的盘子每次放都会放在最上面，取时也会从最上面取。

二、栈的简单实现

栈有两种实现方式，使用数组实现的栈叫顺序栈，使用链表实现则叫链式栈。栈添加数据操作叫入栈，取出数据的操作叫出栈。

2.1 顺序栈实现思路及代码

使用数组实现栈，因为只能在一端进行操作，这里我们选择在数组的后端进行操作。因为后端加入和移除数据都不会进行数据搬移的操作，也更好保持数据在数组中的有序性。入栈只需要将 size++ ，出栈 size– 即可。可能有人会问，数组大小是固定的，当数组满了在入栈怎么办？有两个简单的处理方式，一个是使用动态扩容的数组，二是数组满了再入栈提示入栈失败即可。

ok，下面是具体的实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
java复制代码/**
 * @author xuls
 * @date 2021/11/17 20:30
 * 数组实现栈
 */
public class ArrayStack <T>{
	private Object[] dataArray;
	private int size;

	public ArrayStack(int capacity) {
		dataArray = new Object[capacity];
		size = 0;
	}

    //入栈
	public boolean push(T data){
		if (size == dataArray.length){
			//数组满了，入栈失败
			return false;
		}
		//也可以写 dataArray[size++] = data;
		dataArray[size] = data;
		size ++ ;
		return true;
	}

    //出栈
	public T pop(){
		if (isEmpty()){
			throw  new IndexOutOfBoundsException("stack is Empty");
		}
		//也可以写成 dataArray[size--]
		Object result = dataArray[size - 1];
		size--;
		return (T) result;
	}

	public boolean isEmpty(){
		return size == 0;
	}
}

2.2 链式栈实现思路及代码

链表实现栈思路也很简单，入栈只需要将新数据插入到链表头部，出栈也移除链表头部的数据即可，无需考虑扩容的问题。

下面是具体实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
java复制代码/**
 * @author xuls
 * @date 2021/11/17 20:47
 * 链表实现栈
 */
public class LinkedListStack <T>{
	private Node<T> headNode;
	private int size;

	public LinkedListStack() {
		size = 0;
	}

    //入栈
	public void push(T data){
		Node<T> tNode = new Node<>(data, null);
		if (headNode != null){
			tNode.next = headNode;
		}
		this.headNode = tNode;
		size ++ ;
	}

    //出栈
	public T pop(){
		if (isEmpty()){
			throw new  IndexOutOfBoundsException("stack is empty");
		}
		T data = headNode.data;
		headNode = headNode.next;
		size--;
		return data;
	}

	public boolean isEmpty(){
		return size == 0;
	}

	public void clear(){
		headNode = null;
		size=0;
	}

	private static class Node<T>{
		private T data;
		private Node<T> next;

		public Node(T data, Node<T> next) {
			this.data = data;
			this.next = next;
		}
	}
}

三、浏览器前进后退简单实现

有了上面对栈这种数据结构的介绍，你可能已经想到了如何去实现一个简单的浏览器前进后退功能了。没错，我们可以使用两个栈，一个是前进栈，一个是后退栈。

例如，还是依次访问页面 A、页面 B、页面 C 和页面 D。

当我们从页面 A 到页面 B 时，就将页面 A 的网址在后退栈入栈，页面 B 到页面 C 时，将页面 B 的网址在后退栈入栈。页面 C 到页面 D 也是如此。

好了，这时如果从页面 D 回退到页面 C ，只需要将页面 D 在前进栈入栈，后退栈进行出栈就能拿到页面 C 的访问地址。从页面 C 前进到页面 D，也是一样将页面 C 的网址在后退栈入栈，同时前进栈进行出栈操作就能拿到页面 D 的网址了。

但如果返回到页面 C 时，再打开一个新的页面 E，此时就无法进行前进操作了，也因此需要对前进栈里的数据进行清空。这样就实现了一个简单的前进后退功能。

未命名文件 (1).png

下面是用链式栈实现的具体代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
java复制代码/**
 * @author xuls
 * @date 2021/11/17 21:21
 */
public class CustomBrowser {
	private String currentUrl;
	private LinkedListStack<String> backStack;
	private LinkedListStack<String> forwardStack;

	public CustomBrowser() {
		backStack = new LinkedListStack<>();
		forwardStack = new LinkedListStack<>();
	}

	public void open(String url){
		if (this.currentUrl != null){
			backStack.push(this.currentUrl);
            //打开新页面时，需要清空前进栈的内容
			forwardStack.clear();
		}
		this.currentUrl = url;
		System.out.println("open "+currentUrl);
	}

	public void back(){
		if (!backStack.isEmpty()){
			forwardStack.push(this.currentUrl);
			this.currentUrl = backStack.pop();
			System.out.println("back " + this.currentUrl);
		}
	}

	public void forward(){
		if (!forwardStack.isEmpty()){
			backStack.push(this.currentUrl);
			this.currentUrl = forwardStack.pop();
			System.out.println("forward "+ this.currentUrl);
		}
	}

	public String getCurrentUrl(){
		return currentUrl;
	}

	public static void main(String[] args) {
		CustomBrowser browser = new CustomBrowser();
		browser.open("http://www.baidu1.com");
		browser.open("http://www.baidu2.com");
		browser.open("http://www.baidu3.com");
		browser.back();
		browser.back();
		browser.forward();
		browser.open("http://www.qq.com");
		browser.forward();
		browser.back();
		browser.back();
		browser.back();
		browser.back();
		browser.back();
		browser.back();
		System.out.println(browser.getCurrentUrl());
	}
}

四、总结

  • 栈是一种受限的线性数据结构，只能在一端进行操作，也造成了后进先出的特点（重点，复习三遍）。
  • 栈的两种类型，顺序栈和链式栈。
  • 受限并不意味不易使用，相反特殊的场景更能发挥栈的威力，除了浏览器的前进后退之外，还有括号匹配、表达式求值或者是迷宫问题等等，这就需要我们能将具体的问题的特点抽象出来了。

传送门：

如何实现单链表

如何实现动态扩容数组

XDM ，天冷了除了保暖也要多运动哦，动动小手点赞评论吧！

catdan.gif

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%