浏览器前进与后退的秘密——栈 (栈的理解与实现)

这篇具有很好参考价值的文章主要介绍了浏览器前进与后退的秘密——栈 (栈的理解与实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


浏览器的前进、后退功能,我想你肯定很熟悉吧?当你依次访问完一串页面 a->b->c 之,数据结构,算法

🐱‍🐉作者简介:大家好,我是黑洞晓威,一名大二学生,希望和大家一起进步。
👿本文收录于 算法,本专栏是针对大学生、初学算法的人准备,解析常见的数据结构与算法,同时备战蓝桥杯。

前言:浏览器与栈的纠缠

浏览器的前进、后退功能,我想你肯定很熟悉吧?

当你依次访问完一串页面a-b-c之后,点击浏览器的后退按钮,就可以查看之前浏览过的页面b和a。当你后退到页面a,点击前进按钮,就可以重新查看页面b和c。但是,如果你后退到页面b后,点击了新的页面d,那就无法再通过前进、后退功能查看页面c了。

假设你是浏览器的开发工程师,你会如何实现这个功能呢?

这就要用到我们今天要讲的“栈”这种数据结构。带着这个问题,我们来学习今天的内容。

如何理解“栈”?

关于“栈”,我有一个非常贴切的例子,就是一摞叠在一起的盘子。我们平时放盘子的时候,都是从下往上一个一个放;取的时候,我们也是从上往下一个一个地依次取,不能从中间任意抽出。 后进者先出,先进者后出,这就是典型的“栈”结构。

浏览器的前进、后退功能,我想你肯定很熟悉吧?当你依次访问完一串页面 a->b->c 之,数据结构,算法

从栈的操作特性上来看, 栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。

我第一次接触这种数据结构的时候,就对它存在的意义产生了很大的疑惑。因为我觉得,相比数组和链表,栈带给我的只有限制,并没有任何优势。那我直接使用数组或者链表不就好了吗?为什么还要用这个“操作受限”的“栈”呢?

事实上,从功能上来说,数组或链表确实可以替代栈,但你要知道,特定的数据结构是对特定场景的抽象,而且,数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,这时我们就应该首选“栈”这种数据结构

如何实现一个“栈”?

从刚才栈的定义里,我们可以看出,栈主要包含两个操作,入栈和出栈,也就是在栈顶插入一个数据和从栈顶删除一个数据。理解了栈的定义之后,我们来看一看如何用代码实现一个栈。

实际上,栈既可以用数组来实现,也可以用链表来实现。用数组实现的栈,我们叫作 顺序栈,用链表实现的栈,我们叫作 链式栈

基于数组的顺序栈

我这里实现一个基于数组的顺序栈。

// 基于数组实现的顺序栈
public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           //栈的大小

  // 初始化数组,申请一个大小为n的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了,直接返回false,入栈失败。
    if (count == n) return false;
    // 将item放到下标为count的位置,并且count加一
    items[count] = item;
    ++count;
    return true;
  }

  // 出栈操作
  public String pop() {
    // 栈为空,则直接返回null
    if (count == 0) return null;
    // 返回下标为count-1的数组元素,并且栈中元素个数count减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

基于链表的链式栈

基于链表实现的链式栈的代码:

/*
 * 用链表作为栈的底层
 */
public class SingleLinkedListStack {
//  用链表作为栈的底层
	public SingleLinkedList<E> list;
	public SingleLinkedListStack() {
	             list = new SingleLinkedList();
}
	@Override
	public void push(E e) {
		// TODO Auto-generated method stub
		list.addFirst(e);
	}

	@Override
	public E pop() {
		// TODO Auto-generated method stub
		return (E) list.removeFirst();
	}

	@Override
	public E peek() {
		// TODO Auto-generated method stub
		return  list.getfirst();
	}

	@Override
	public int getSize() {
		// TODO Auto-generated method stub
		return list.getSize();
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return list.isEmpty();
	}
	@Override
	public String toString() {
		
		  StringBuilder sb=new StringBuilder(); sb.append("stack ");
		  sb.append("push:>");
		  for(int i=0;i<list.getSize();i++) {
			  sb.append(list.get(i));
			  sb.append("->");
		  }
		  sb.append("null");
		return sb.toString();
	}
	
}

了解了定义和基本操作,那它的操作的时间、空间复杂度是多少呢?

不管是顺序栈还是链式栈,我们存储数据只需要一个大小为n的数组就够了。在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是O(1)。

注意,这里存储数据需要一个大小为n的数组,并不是说空间复杂度就是O(n)。因为,这n个空间是必须的,无法省掉。所以我们说空间复杂度的时候,是指除了原本的数据存储空间外,算法运行还需要额外的存储空间。

空间复杂度分析是不是很简单?时间复杂度也不难。不管是顺序栈还是链式栈,入栈、出栈只涉及栈顶个别数据的操作,所以时间复杂度都是O(1)。

解答开篇

好了,我想现在你已经完全理解了栈的概念。我们再回来看看开篇的思考题,如何实现浏览器的前进、后退功能?其实,用两个栈就可以非常完美地解决这个问题。

我们使用两个栈,X和Y,我们把首次浏览的页面依次压入栈X,当点击后退按钮时,再依次从栈X中出栈,并将出栈的数据依次放入栈Y。当我们点击前进按钮时,我们依次从栈Y中取出数据,放入栈X中。当栈X中没有数据时,那就说明没有页面可以继续后退浏览了。当栈Y中没有数据,那就说明没有页面可以点击前进按钮浏览了。

比如你顺序查看了a,b,c三个页面,我们就依次把a,b,c压入栈,这个时候,两个栈的数据就是这个样子:

浏览器的前进、后退功能,我想你肯定很熟悉吧?当你依次访问完一串页面 a->b->c 之,数据结构,算法

当你通过浏览器的后退按钮,从页面c后退到页面a之后,我们就依次把c和b从栈X中弹出,并且依次放入到栈Y。这个时候,两个栈的数据就是这个样子:

浏览器的前进、后退功能,我想你肯定很熟悉吧?当你依次访问完一串页面 a->b->c 之,数据结构,算法

这个时候你又想看页面b,于是你又点击前进按钮回到b页面,我们就把b再从栈Y中出栈,放入栈X中。此时两个栈的数据是这个样子:

浏览器的前进、后退功能,我想你肯定很熟悉吧?当你依次访问完一串页面 a->b->c 之,数据结构,算法

这个时候,你通过页面b又跳转到新的页面d了,页面c就无法再通过前进、后退按钮重复查看了,所以需要清空栈Y。此时两个栈的数据这个样子:

浏览器的前进、后退功能,我想你肯定很熟悉吧?当你依次访问完一串页面 a->b->c 之,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-778839.html

到了这里,关于浏览器前进与后退的秘密——栈 (栈的理解与实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 前端高频面试题 js中堆和栈的区别和浏览器的垃圾回收机制

    栈(stack) :是栈内存的简称,栈是自动分配相对固定大小的内存空间,并由系统自动释放,栈数据结构遵循FILO(first in last out)先进后出的原则,较为经典的就是乒乓球盒结构,先放进去的乒乓球只能最后取出来。 堆(heap) :是堆内存的简称,堆是动态分配内存,内存大小不固

    2024年02月11日
    浏览(40)
  • Linux 实现鼠标侧边键实现代码与网页的前进、后退

    之前一直是使用windows进行开发,最近转到linux后使用VsCode编写代码。 但是不像在win环境下,使用鼠标侧边键可以实现代码的前向、后向跳转。浏览网页时也不行(使用 Alt + Left 可以后退)。 修改键盘映射实在没有那么方便,所以要想点儿招解决这个问题。 经过一番查找,

    2024年02月11日
    浏览(45)
  • 对浏览器垃圾回收机制的理解

    1、垃圾回收的概念      javaScript代码运行的时候,需要分配内存空间来存储变量和值。变量不再参与的时候,就需要系统收回被占用的内存空间,这就是垃圾回收 🌈 回收机制:      ● js具有自动垃圾回收机制,会定期对那些不再使用的变量、对象占用的内存进行释放

    2024年02月14日
    浏览(45)
  • Qt 实现简易的视频播放器,功能选择视频,播放,暂停,前进,后退,进度条拖拉,视频时长显示

    1.效果图 2.代码实现 2.1 .pro文件 2.2 .h文件 2.3 .cpp文件

    2024年04月12日
    浏览(41)
  • 什么是无头浏览器?如何使用Golang实现无头浏览器截图?

    在Web开发中,有时需要对网页进行截图,以便进行页面预览、测试等操作。 而使用无头浏览器来实现截图功能,可以避免手动操作的繁琐和不稳定性。 这篇文章将介绍: 使用Golang进行无头浏览器的截图,轻松实现页面预览、测试和模拟用户操作。 这篇文章发完,有朋友在朋

    2024年02月05日
    浏览(54)
  • VSCode前进后退(按钮、快捷键)

    一、后退前进按钮 顶部显示,方便调试 文件- 首选项 - 设置-commandcenter-勾选 Window: Title Bar Style-custom 二、后退前进快捷键 后退        【Ctrl】【Alt】【-】  前进        【Ctrl】【Shift】【-】 文件- 首选项 - Keyboard Shotcuts - 搜索【navigateBack】【navigateForward】

    2024年04月28日
    浏览(36)
  • 基于selenium实现多个脚本只打开一次浏览器(重复使用浏览器)

    本文思路来源【Selenium】控制当前已经打开的 chrome浏览器窗口(高级版)_是小菜欸的博客-CSDN博客 selenium 自动打开Chrome浏览器且重复使用已打开的Chrome实例_飞扬的箭的博客-CSDN博客 但是这一篇文章的方式对于我来说有一个缺点,即每一次都需要新创建一个浏览器,或者需要

    2024年02月16日
    浏览(36)
  • C# 实现浏览器控件设置

    2024年02月10日
    浏览(38)
  • 基于QWebEngine实现无头浏览器

    无头浏览器( Headless Browser )是一种没有图形用户界面(GUI)的浏览器。它通过在内存中渲染页面,然后将结果发送回请求它的用户或程序来实现对网页的访问,而不会在屏幕上显示网页。这种方式使得无头浏览器不仅适用于网络爬虫和测试等自动化任务,而且还能够更安全

    2024年02月09日
    浏览(49)
  • 前端实现浏览器自定义滚动条

    最近有个项目,产品觉得浏览器默认滚动条太丑了。想美化一下,比如自定义颜色,加上圆角,宽高都要更改一下。我查了资料和文档总结了一下 写法,特此记录以便之后使用。 scrollbar-width scrollbar-width 属性允许开发者在元素显示滚动条时设置滚动条的最大宽度。 语法: 取值

    2024年04月10日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包