当前位置:首页 » 《随便一记》 » 正文

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

5 人参与  2023年03月19日 16:26  分类 : 《随便一记》  评论

点击全文阅读


文章目录

前言:浏览器与栈的纠缠如何理解“栈”?如何实现一个“栈”?基于数组的顺序栈基于链表的链式栈 解答开篇
在这里插入图片描述

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

前言:浏览器与栈的纠缠

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

当你依次访问完一串页面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();}@Overridepublic void push(E e) {// TODO Auto-generated method stublist.addFirst(e);}@Overridepublic E pop() {// TODO Auto-generated method stubreturn (E) list.removeFirst();}@Overridepublic E peek() {// TODO Auto-generated method stubreturn  list.getfirst();}@Overridepublic int getSize() {// TODO Auto-generated method stubreturn list.getSize();}@Overridepublic boolean isEmpty() {// TODO Auto-generated method stubreturn list.isEmpty();}@Overridepublic 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://zhangshiyu.com/post/55895.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1