浏览器前进后退功能的简单实现(浏览器前进和后退的快捷键)
笔者最近在学习《数据结构与算法之美》，正好借着这个机会边练习边记录一下自己学习的知识点。不啰嗦，直接开始。
假设我们依次浏览了页面 A、页面 B、页面 C 和 页面D，当我们在页面 D 点击浏览器的后退按钮时，浏览器会返回放上一次浏览的页面 C，此时再点击前进按钮则会返回到页面 D。这就是浏览器的前进和后退功能，让我们能够随意的返回前一个页面和后一个页面，那么这个功能是如何实现的呢？这里我们先按下不表，先看看栈这种数据结构。
一、什么是栈
栈也是线性数据结构
栈是一种操作受限的线性表，只允许在一端对数据进行操作。
正因为只能在一端进行操作，也造就了栈具有的后进先出的特点，也即后加入的数据，先被移除出去。就像是餐厅叠在一起的盘子，新洗好的盘子每次放都会放在最上面，取时也会从最上面取。
二、栈的简单实现
栈有两种实现方式，使用数组实现的栈叫顺序栈，使用链表实现则叫链式栈。栈添加数据操作叫入栈，取出数据的操作叫出栈。
2.1 顺序栈实现思路及代码
使用数组实现栈，因为只能在一端进行操作，这里我们选择在数组的后端进行操作。因为后端加入和移除数据都不会进行数据搬移的操作，也更好保持数据在数组中的有序性。入栈只需要将 size++ ，出栈 size-- 即可。可能有人会问，数组大小是固定的，当数组满了在入栈怎么办？有两个简单的处理方式，一个是使用动态扩容的数组，二是数组满了再入栈提示入栈失败即可。
ok，下面是具体的实现代码：
/** * @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 链式栈实现思路及代码
链表实现栈思路也很简单，入栈只需要将新数据插入到链表头部，出栈也移除链表头部的数据即可，无需考虑扩容的问题。
下面是具体实现代码：
/** * @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，此时就无法进行前进操作了，也因此需要对前进栈里的数据进行清空。这样就实现了一个简单的前进后退功能。
下面是用链式栈实现的具体代码：
/** * @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()); } } 复制代码四、总结
栈是一种受限的线性数据结构，只能在一端进行操作，也造成了后进先出的特点（重点，复习三遍）。
栈的两种类型，顺序栈和链式栈。
受限并不意味不易使用，相反特殊的场景更能发挥栈的威力，除了浏览器的前进后退之外，还有括号匹配、表达式求值或者是迷宫问题等等，这就需要我们能将具体的问题的特点抽象出来了。
作者：小许写写写
链接：https://juejin.cn/post/7032537071285714957