专栏首页算法猿的成长如何用栈实现浏览器的前进和后退?

如何用栈实现浏览器的前进和后退?

2019 年第 79 篇文章,总第 103 篇文章

数据结构与算法系列的第四篇文章,前三篇文章:

  1. 数据结构算法入门--一文了解什么是复杂度
  2. 一文了解数组
  3. 数据结构算法入门--链表

前言

浏览器的前进和后退功能怎么用栈来实现呢?

这里先介绍一下栈的定义和实现,并介绍它的一些常用的应用,最后再简单实现一个简单的浏览器前进和后退的操作。

栈是一种“操作受限”的线性表只允许在一端插入和删除数据,特点就是后进先出、先进后出

目录:

  • 栈的实现
  • 栈在函数调用中的应用
  • 栈在表达式求值中的应用
  • 栈在括号匹配中的应用
  • 利用栈实现浏览器的前进和后退功能

栈的实现

栈既可以通过数组实现,也可以通过链表实现。数组实现的栈,称为顺序栈;链表实现的栈,称为链式栈

这里用 Python 分别实现这两种栈。

顺序栈的实现代码:

from typing import Optional

class ArrayStack:    def __init__(self, nums):        # 初始化数组        self._data = list()        # 数组的大小        self._nums = nums        # 数组元素个数        self._count = 0
    def push(self, data) -> bool:        '''        入栈        :param data:        :return:        '''        if (self._count + 1) == self._nums:            # 栈已经满了            return False
        self._data.append(data)        self._count += 1        return True
    def pop(self) -> Optional[int]:        '''        出栈        :return:        '''        if self._count:            value = self._data[self._count - 1]            self._data.pop(self._count - 1)            self._count -= 1            return value
    def __repr__(self) -> str:        '''        打印栈        :return:        '''        nums = reversed(self._data)
        return " ".join("[{}]".format(num) for num in nums)

if __name__ == '__main__':    stack = ArrayStack(10)
    for i in range(15):        stack.push(i)    # 输出:[8] [7] [6] [5] [4] [3] [2] [1] [0]    print(stack)
    for _ in range(5):        stack.pop()    # 输出:[3] [2] [1] [0]    print(stack)

链式栈的实现代码:

from typing import Optional

# 链表结点类class Node:    def __init__(self, data: int, next=None):        self._data = data        self._next = next

class LinkedStack:    """    链表实现的栈    """
    def __init__(self):        self._top = None
    def push(self, value: int):        '''        入栈,将新结点放在链表首部        :param value:        :return:        '''        new_top = Node(value)        new_top._next = self._top        self._top = new_top
    def pop(self) -> Optional[int]:        if self._top:            value = self._top._data            self._top = self._top._next            return value
    def __repr__(self) -> str:        '''        打印栈元素        :return:        '''        current = self._top        nums = []        while current:            nums.append(current._data)            current = current._next        return " ".join("[{}]".format(num) for num in nums)
if __name__ == '__main__':    stack = LinkedStack()    # 入栈    for i in range(9):        stack.push(i)    # 输出:入栈结果:  [8] [7] [6] [5] [4] [3] [2] [1] [0]    print('入栈结果: ', stack)    # 出栈    for _ in range(3):        stack.pop()    # 输出:出栈结果:  [5] [4] [3] [2] [1] [0]    print('出栈结果: ', stack)

看完上述实现代码,这里思考下栈的操作的时间和空间复杂度分别是多少呢?

对于空间复杂度,入栈和出栈都只需要一两个临时变量存储空间,所以空间复杂度是 O(1)

时间复杂度,入栈和出栈也只是涉及到栈顶的数据的操作,因此时间复杂度是 O(1)

栈在函数调用中的应用

栈的一个比较经典的应用就是函数调用栈

操作系统给每个线程分配了一块独立的内存空间,它被组织为“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个栈帧入栈,当被调用的函数执行完成,返回之后,将这个函数对应的栈帧出栈

下面是一个例子:

def add(x, y):    sum = x + y    return sum
def main():    a = 1    ret = 0    res = 0    ret = add(3, 5)    res = a + ret    print('%d', res)

这段代码中,main() 函数调用了 add() 函数,获取计算结果,并且和变量 a 相加,得到最终结果 res ,然后打印。这段代码中的函数调用栈情况如下所示,它显示的是在调用 add() 函数并执行相加时的情况。

栈在表达式求值中的应用

栈的另一个常用场景就是实现表达式求值,编译器实现表达式求值的方法是通过两个栈来实现。一个保存操作数,一个保存运算符。其实现思路如下:

  1. 从左到右遍历表达式,遇到数字,就压入操作数栈
  2. 遇到运算符,就和运算符栈的栈顶元素进行比较,如果比栈顶元素的优先级高,就压入栈如果比栈顶元素的优先级低或者是相同优先级,就取出栈顶的运算符,然后从操作数栈的栈顶取 2 个操作数,进行计算后将计算结果放入操作数栈,接着继续比较运算符和当前运算符栈的栈顶元素。

这里给出一个例子,如何计算表达式 3+5*8-6,如下图所示:

栈在括号匹配中的应用

栈的第三个应用是可以检查表达式中的括号是否匹配。

通过栈来检查括号匹配问题的方法思路如下:

  1. 从左到右扫描表达式,遇到左括号,压入栈中;
  2. 如果扫描到右括号,从栈顶取出一个左括号,如果可以匹配,继续扫描表达式;但如果不能匹配,或者栈为空,说明表达式是非法的格式;
  3. 扫描完毕后,栈说空,说明表达式是合法格式;否则,说明还有未匹配的左括号,表达式是非法格式。

利用栈实现浏览器的前进和后退功能

最后一个应用是实现浏览器的前进和后退功能,这里采用两个栈来解决。

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

实现代码如下所示:

from Stack.linked_stack import LinkedStackimport copy

class NewLinkedStack(LinkedStack):    def is_empty(self):        return not self._top

class Browser():    def __init__(self):        # forward_stack 保存打开浏览器或者前进时候的页面        self.forward_stack = NewLinkedStack()        # back_stack 保存后退时候从 forward_stack 弹出的页面        self.back_stack = NewLinkedStack()
    def can_forward(self):        if self.back_stack.is_empty():            return False        return True
    def can_back(self):        if self.forward_stack.is_empty():            return False        return True
    def open(self, url):        print('Open new url {}'.format(url))        self.forward_stack.push(url)
    def back(self):        if self.forward_stack.is_empty():            return        # 点击后退按钮,从 forward_stack 中弹出当前页面,并保存到 back_stack 中        top = self.forward_stack.pop()        self.back_stack.push(top)        print('back to {}'.format(top))
    def forward(self):        if self.back_stack.is_empty():            return        # 点击前进按钮,从 back_stack 中弹出,然后保存到 forward_stack 中        top = self.back_stack.pop()        self.forward_stack.push(top)        print('forward to {}'.format(top))
    def __repr__(self):        copy_forward_stack = copy.deepcopy(self.forward_stack)        url_list = list()        while not copy_forward_stack.is_empty():            url_list.append(copy_forward_stack.pop())        return " ".join("{}".format(url) for url in url_list)

if __name__ == '__main__':    browser = Browser()    browser.open('a')    browser.open('b')    browser.open('c')    print('open the browser: {}'.format(browser))    if browser.can_back():        browser.back()
    if browser.can_forward():        browser.forward()
    browser.back()    browser.back()    browser.back()    print('browser: {}'.format(browser))

输出结果:

Open new url aOpen new url bOpen new url copen the browser: c b aback to cforward to cback to cback to bback to abrowser:

总结

本文先介绍了如何实现一个栈,然后介绍了栈的几个应用,包括函数调用、表达式求值、括号匹配、浏览器前进和后退的实现等。

本文分享自微信公众号 - 算法猿的成长(AI_Developer),作者:kbsc13

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python基础入门_5面向对象基础

    第五篇主要介绍 Python 的面向对象基础知识,也就是类的介绍,包括类方法和属性、构造方法、方法重写、继承等,最后给出两道简单的练习题。

    材ccc
  • [GAN学习系列3]采用深度学习和 TensorFlow 实现图片修复(中)

    上一篇文章--[GAN学习系列3]采用深度学习和 TensorFlow 实现图片修复(上)中,我们先介绍了对于图像修复的背景,需要利用什么信息来对缺失的区域进行...

    材ccc
  • [GAN学习系列3]采用深度学习和 TensorFlow 实现图片修复(下)

    http://bamos.github.io/2016/08/09/deep-completion/

    材ccc
  • 一个Python3和Python2的range差异

    Python 3 中执行100000000 in range(100000001)会比Python 2快的非常多。

    用户1416054
  • 【实战小项目】python开发自动化运维工具--批量操作主机

    有很多开源自动化运维工具都很好用如ansible/salt stack等,完全不用重复造轮子。只不过,很多运维同学学习Python之后,苦于没小项目训练,本篇演...

    用户1432189
  • Prioritized Experience Replay (DQN)——让DQN变得更会学习

    1.前言2.算法2.1 SumTree有效抽样2.2 Memory类2.3 更新方法对比结果

    CristianoC
  • 深度强化学习之DQN实战

    今天我们会将我们上一篇文章讲解的DQN的理论进行实战,实战的背景目前仍然是探险者上天堂游戏,不过在下一次开始我们会使用OpenAI gym的环境库,玩任何我们想...

    CristianoC
  • Python|520表白神器

    众所周知,5月20日为“520”情人节,这一天也是即将到来,大家都希望与自己的男神女神过一个浪漫的情人节。但是还有很多像小编这样的单身狗,不知道如何向自己的男神...

    算法与编程之美
  • 我的tkinter学习笔记4

    用户6367961
  • 箱线图(BoxPlot) App

    由于公司的Execl版本(v2010)偏低,没有画箱线图的功能,故我用python写了一小段程序,可以用来画箱线图。绘图库使用的还是matplotlib。

    用户6021899

扫码关注云+社区

领取腾讯云代金券