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

文章目录

    • 前言:浏览器与栈的纠缠
    • 如何理解“栈”?
    • 如何实现一个“栈”?
      • 基于数组的顺序栈
      • 基于链表的链式栈
    • 解答开篇

在这里插入图片描述

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

前言:浏览器与栈的纠缠

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

当你依次访问完一串页面a-b-c之后,点击浏览器的后退按钮,就可以查看之前浏览过的页面b和a。当你后退到页面a,点击前进按钮,就可以重新查看页面b和c。但是,如果你后退到页面b后,点击了新的页面d,那就无法再通过前进、后退功能查看页面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压入栈,这个时候,两个栈的数据就是这个样子:

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/1100.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

每日算法题

题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 作为篮球队教练&#xff0c;你需要从以下名单中选出 11 号位至 55 号位各一名球员&#xff0c;组成球队的首发阵容。 每位球员担任 11 号位至 55 号位时的评分如下…

CCF-CSP真题《202212-3 JPEG 解码》思路+python,c++满分题解

想查看其他题的真题及题解的同学可以前往查看&#xff1a;CCF-CSP真题附题解大全 试题编号&#xff1a;202212-3试题名称&#xff1a;JPEG 解码时间限制&#xff1a;1.0s内存限制&#xff1a;512.0MB问题描述&#xff1a; 问题背景 四年一度的世界杯即将画上尾声。在本…

STM32 OTA应用开发——通过串口/RS485实现OTA升级(方式2)

STM32 OTA应用开发——通过串口/RS485实现OTA升级&#xff08;方式2&#xff09; 目录STM32 OTA应用开发——通过串口/RS485实现OTA升级&#xff08;方式2&#xff09;前言1 环境搭建2 功能描述3 程序编写3.1 BootLoader部分3.2 APP的制作4 修改工程中的内存配置4.1 Bootloader…

面试阿里测开岗失败后,被面试官在朋友圈吐槽了......

前一阵子有个徒弟向我诉苦&#xff0c;说自己在参加某大厂测试面试的时候被面试官怼得哑口无言&#xff0c;场面让他一度十分尴尬印象最深的就是下面几个问题&#xff1a;根据你以前的工作经验和学习到的测试技术&#xff0c;说说你对质量保证的理解&#xff1f;非关系型数据库…

HashMap扩容为什么每次都是之前的2倍

一. 背景介绍HashMap的底层是通过数组链表红黑树的数据结构来存放数据的。我们知道&#xff0c;当新添加元素的key值出现了hash碰撞&#xff0c;就会在同一个bucket中形成链表或者红黑树。当键值对的数量超过阈值时就会扩容&#xff0c;将以前处于同一个链表或者红黑树上的元素…

持续集成 在 Linux 上搭建 Jenkins,自动构建接口测试

本篇把从 0 开始搭建 Jenkins 的过程分享给大家&#xff0c;希望对小伙伴们有所帮助。 文章目录 在 Linux 上安装 Jenkins在 Linux 上安装 Git在 Linux 上安装 Python在 Linux 上安装 Allure配置 Jenkinsjenkins 赋能 - 使用邮箱发送测试报告jenkins 赋能 - 优化测试报告内容…

C语言刷题(6)(猜名次)——“C”

各位CSDN的uu们你们好呀&#xff0c;今天&#xff0c;小雅兰还是在复习噢&#xff0c;今天来给大家介绍一个有意思的题目 题目名称&#xff1a; 猜名次 题目内容&#xff1a; 5位运动员参加了10米台跳水比赛&#xff0c;有人让他们预测比赛结果&#xff1a; A选…

测试管理之路 —— 如何优化测试计划以提高测试覆盖率

&#x1f60f;作者简介&#xff1a;博主是一位测试管理者&#xff0c;同时也是一名对外企业兼职讲师。 &#x1f4e1;主页地址&#xff1a;&#x1f30e;【Austin_zhai】&#x1f30f; &#x1f646;目的与景愿&#xff1a;旨在于能帮助更多的测试行业人员提升软硬技能&#xf…

Github的使用

Github Date: March 8, 2023 Sum: Github的使用 Github 了解开源相关的概念 1. 什么是开源 2. 什么是开源许可协议 开源并不意味着完全没有限制&#xff0c;为了限制使用者的使用范围和保护作者的权利&#xff0c;每个开源项目都应该遵守开源许可协议&#xff08; Open Sou…

node多版本控制

前言 最近在折腾Python&#xff0c;并将node升级至v18.14.2。突然发现一个旧项目无法运行&#xff0c;也无法打包&#xff0c;里面的node-sass报错&#xff0c;显然这是因为node版本过高导致的。 将node版本降低至以前的v14.16.0&#xff0c;果然立马就能正常运行。 存在不同…

mysql-日志备份

1.binlog 用于数据恢复&#xff0c; 用于数据复制。 mysql> show variables like %log_bin%; -------------------------------------------------------------- | Variable_name | Value | ----------------------------------…

前端代码复用学习笔记:整洁架构与清晰架构

基础代码的复用往往比较简单&#xff0c;但是业务代码的复用通常是困难的&#xff0c;如果没有特殊的手段去治理项目会逐渐发展为难以维护的巨石应用&#xff0c;按照维基百科记载&#xff0c;代码的复用形式主要有三种&#xff0c;程序库&#xff0c;应用框架&#xff0c;设计…

【无标题】 6UVPX 总线架构的高性能实时信号处理

VPX630 是一款基于 6U VPX 总线架构的高速信号处理平台&#xff0c;该平台采用一片 Xilinx 的 Kintex UltraScale 系列 FPGA&#xff08;XCKU115&#xff09;作为主处理器&#xff0c;完成复杂的数据采集、回放以及实时信号处理算法。 采用一片带有 ARM内核的高性能嵌入式处理…

GeoServer发布一张纯图片作为地图教程

从事GIS行业的小伙伴们可能会有这样的需求,就是客户给了一张纯图片。可能是一张手工绘图,也可能是一张影像图片,总归来说就是png,jpeg格式的纯图片,现在需要把这张图片加载到我们的地图上,该如何做呢?本文带你从0开始操作一遍。 首先我先准备好测试数据,是一张jpg格式…

LeetCode刷题——贪心法(C/C++)

这里写目录标题[中等]买卖股票的最佳时机 II[中等]移掉k位数字[中等]跳跃游戏[中等]跳跃游戏 II[中等]加油站[中等]划分字母区间[中等]无重叠区间[中等]用最少数量的箭引爆气球[中等]买卖股票的最佳时机 II 原题链接题解 最简单的思路&#xff0c;效率不高&#xff0c;只要明天…

基于 pytorch 的手写 transformer + tokenizer

先放出 transformer 的整体结构图,以便复习,接下来就一个模块一个模块的实现它。 1. Embedding Embedding 部分主要由两部分组成,即 Input Embedding 和 Positional Encoding,位置编码记录了每一个词出现的位置。通过加入位置编码可以提高模型的准确率,因为同一个词出现在…

Web3中文|政策影响下的新加坡Web3步伐喜忧参半

如果说“亚洲四小龙”是新加坡曾经的荣耀&#xff0c;那么当时代进入21世纪的第二个十年&#xff0c;用新加坡经济协会&#xff08;SEE&#xff09;副主席、新加坡新跃社科大学教授李国权的话来说&#xff0c;新加坡现在的“荣耀”是全球金融的主要“节点”或区块链行业发展的关…

单片机能运行操作系统吗?

先直接上答案&#xff1a;可以&#xff01;但是操作系统不是刚需&#xff0c;上操作系统比较占用单片机的资源&#xff0c;比如占用比较多的FLASH和RAM&#xff0c;间接增加了硬件成本&#xff0c;哪怕成本增加1毛钱&#xff0c;对于上量的产品&#xff0c;分分钟是一个工程师的…

【ChatGPT】论文阅读神器 SciSpace 注册与测试

【ChatGPT】论文阅读神器 SciSpace 注册与测试1. 【SciSpace】网址与用户注册1.1 官网地址&#xff1a;[【SciSpace官网】https://typeset.io](https://typeset.io)1.2 官网注册2. 【SciSpace】实战解说2.1 导入论文2.2 论文分析2.3 中文分析2.4 论文分析进阶2.5 公式表格分析3…

没有关系的话,那就去建立关系吧

今天给大家分享一道链表的好题--链表的深度拷贝&#xff0c;学会这道题&#xff0c;你的链表就可以达到优秀的水平了。力扣 先来理解一下题目意思&#xff0c;即建立一个新的单向链表&#xff0c;里面每个结点的值与对应的原链表相同&#xff0c;并且random指针也要指向新链表中…
最新文章