揭秘浏览器的前进和后退功能是如何实现的！
还是想告诉朋友们：
我们学习任何东西，不要为了学而学，一定是知道为什么学，不然没有任何的意义！
我想这个功能大家都用过吧！浏览器的前进与后退。
那有没有想过，这样一个功能背后到底是如何实现的呢？带着这个问题阅读下文吧，文章结尾有实现的代码！
当你依次访问一串页面a->b->c之后，点击浏览器的后退按钮，就可以查看之前浏览过的页面b和c。
你是否能联想到栈这个数据结构呢？
栈
栈的特性是先进后出。
栈既可以用数组实现，称为顺序栈。
也可以用链表实现，称为链式栈。
不管是顺序栈还是链式栈，存储数据只需要一个大小为n的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是O(1)。
注意：这里存储数据需要一个大小为n的数组，并不是说空间复杂度就是O(n)。因为这n个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要的额外的存储空间。
不管是顺序栈还是链式栈，入栈出栈只涉及个别数据的操作，所以时间复杂度是O(1)。
但是基于数组实现的栈是一个固定大小的栈，所以无法动态进行扩容，尽管链式栈的大小不受限，但是需要存储next指针，内存消耗相对较多。
基于数组的动态扩容的栈，当空间不够时，我们需要重新申请一块更大的内存，将原来数组中的数据拷贝过去！
浏览器的前进与后退功能思路
我们来分析一下浏览器的前进与后退功能：
- 访问了一个网页a之后，将网址a入栈A。
- 再访问网页b，将网址b入栈A。
- 再访问网页c，将网址c入栈A。
- 后退：将栈A的栈顶c入栈B，再访问栈A的栈顶b。
- 前进：弹出栈B的栈顶c，并将c压入栈A，并访问栈A的栈顶c。
所以我们需要维护两个栈实现浏览器的前进与后退功能。
如下图：
维护两个栈实现浏览器的前进与后退功能
我使用curl 来模拟请求，便于理解全过程！
通过数组栈实现此功能。
- click请求模拟用户点击的网页，传入一个url。
- back请求模拟用户点击回退
- forward请求模拟用户点击前进
返回的值包括，正在访问的页面，栈A中的数据，栈B中的数据。
非常的直观，便于理解全过程。
实现代码：
package stack
import "errors"
type ArrayStack struct {
Urls []string
Size int
}
var emptyStack = errors.New("empty stack, can not pop")
func NewArrayStack() *ArrayStack {
return &ArrayStack{Urls: make([]string, 0)}
}
func (as *ArrayStack) Pop() (error, string) {
if as.Size == 0 {
return emptyStack, ""
}
length := as.Size
pop := as.Urls[length-1]
as.Urls = as.Urls[:length-1]
as.Size--
return nil, pop
}
func (as *ArrayStack) Push(s string) {
as.Urls = append(as.Urls, s)
as.Size++
}
func (as *ArrayStack) Top() string {
if as.Size == 0 {
return ""
}
return as.Urls[as.Size-1]
}
func (as *ArrayStack) Length() int {
return as.Size
}package main
import (
"log"
"mystack/stack"
"sync"
"github.com/gin-gonic/gin"
)
type Browser struct {
mu sync.Mutex
arrayStackA *stack.ArrayStack
arrayStackB *stack.ArrayStack
}
var browser = new(Browser)
func main() {
browser.arrayStackA = stack.NewArrayStack()
browser.arrayStackB = stack.NewArrayStack()
r := gin.Default()
r.POST("/click", click)
r.GET("/back", back)
r.GET("/forward", forward)
if err := r.Run(":8080"); err != nil {
log.Fatal(err)
}
}
func click(c *gin.Context) {
browser.mu.Lock()
defer browser.mu.Unlock()
click := c.PostForm("url")
if click != browser.arrayStackA.Top() {
browser.arrayStackA.Push(click)
}
c.IndentedJSON(200, gin.H{
"你正在访问": browser.arrayStackA.Top(),
"栈A:": browser.arrayStackA.Urls,
"栈B": browser.arrayStackB.Urls,
})
}
func back(c *gin.Context) {
browser.mu.Lock()
defer browser.mu.Unlock()
_, url := browser.arrayStackA.Pop()
browser.arrayStackB.Push(url)
c.IndentedJSON(200, gin.H{
"你正在访问": browser.arrayStackA.Top(),
"栈A": browser.arrayStackA.Urls,
"栈B": browser.arrayStackB.Urls,
})
}
func forward(c *gin.Context) {
browser.mu.Lock()
defer browser.mu.Unlock()
_, url := browser.arrayStackB.Pop()
browser.arrayStackA.Push(url)
c.IndentedJSON(200, gin.H{
"你正在访问": browser.arrayStackA.Top(),
"栈A": browser.arrayStackA.Urls,
"栈B": browser.arrayStackB.Urls,
})
}
