当前位置:   article > 正文

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

请使用一个栈 实现 浏览器

640?wx_fmt=jpeg

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

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

前言

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

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

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

目录:

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

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

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

顺序栈的实现代码:

  1. from typing import Optional
  2. class ArrayStack:
  3. def __init__(self, nums):
  4. # 初始化数组
  5. self._data = list()
  6. # 数组的大小
  7. self._nums = nums
  8. # 数组元素个数
  9. self._count = 0
  10. def push(self, data) -> bool:
  11. '''
  12. 入栈
  13. :param data:
  14. :return:
  15. '''
  16. if (self._count + 1) == self._nums:
  17. # 栈已经满了
  18. return False
  19. self._data.append(data)
  20. self._count += 1
  21. return True
  22. def pop(self) -> Optional[int]:
  23. '''
  24. 出栈
  25. :return:
  26. '''
  27. if self._count:
  28. value = self._data[self._count - 1]
  29. self._data.pop(self._count - 1)
  30. self._count -= 1
  31. return value
  32. def __repr__(self) -> str:
  33. '''
  34. 打印栈
  35. :return:
  36. '''
  37. nums = reversed(self._data)
  38. return " ".join("[{}]".format(num) for num in nums)
  39. if __name__ == '__main__':
  40. stack = ArrayStack(10)
  41. for i in range(15):
  42. stack.push(i)
  43. # 输出:[8] [7] [6] [5] [4] [3] [2] [1] [0]
  44. print(stack)
  45. for _ in range(5):
  46. stack.pop()
  47. # 输出:[3] [2] [1] [0]
  48. print(stack)

链式栈的实现代码:

  1. from typing import Optional
  2. # 链表结点类
  3. class Node:
  4. def __init__(self, data: int, next=None):
  5. self._data = data
  6. self._next = next
  7. class LinkedStack:
  8. """
  9. 链表实现的栈
  10. """
  11. def __init__(self):
  12. self._top = None
  13. def push(self, value: int):
  14. '''
  15. 入栈,将新结点放在链表首部
  16. :param value:
  17. :return:
  18. '''
  19. new_top = Node(value)
  20. new_top._next = self._top
  21. self._top = new_top
  22. def pop(self) -> Optional[int]:
  23. if self._top:
  24. value = self._top._data
  25. self._top = self._top._next
  26. return value
  27. def __repr__(self) -> str:
  28. '''
  29. 打印栈元素
  30. :return:
  31. '''
  32. current = self._top
  33. nums = []
  34. while current:
  35. nums.append(current._data)
  36. current = current._next
  37. return " ".join("[{}]".format(num) for num in nums)
  38. if __name__ == '__main__':
  39. stack = LinkedStack()
  40. # 入栈
  41. for i in range(9):
  42. stack.push(i)
  43. # 输出:入栈结果: [8] [7] [6] [5] [4] [3] [2] [1] [0]
  44. print('入栈结果: ', stack)
  45. # 出栈
  46. for _ in range(3):
  47. stack.pop()
  48. # 输出:出栈结果: [5] [4] [3] [2] [1] [0]
  49. print('出栈结果: ', stack)

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

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

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

栈在函数调用中的应用

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

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

下面是一个例子:

  1. def add(x, y):
  2. sum = x + y
  3. return sum
  4. def main():
  5. a = 1
  6. ret = 0
  7. res = 0
  8. ret = add(3, 5)
  9. res = a + ret
  10. print('%d', res)

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

640?wx_fmt=png
栈在表达式求值中的应用

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

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

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

640?wx_fmt=png
栈在括号匹配中的应用

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

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

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

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

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

实现代码如下所示:

  1. from Stack.linked_stack import LinkedStack
  2. import copy
  3. class NewLinkedStack(LinkedStack):
  4. def is_empty(self):
  5. return not self._top
  6. class Browser():
  7. def __init__(self):
  8. # forward_stack 保存打开浏览器或者前进时候的页面
  9. self.forward_stack = NewLinkedStack()
  10. # back_stack 保存后退时候从 forward_stack 弹出的页面
  11. self.back_stack = NewLinkedStack()
  12. def can_forward(self):
  13. if self.back_stack.is_empty():
  14. return False
  15. return True
  16. def can_back(self):
  17. if self.forward_stack.is_empty():
  18. return False
  19. return True
  20. def open(self, url):
  21. print('Open new url {}'.format(url))
  22. self.forward_stack.push(url)
  23. def back(self):
  24. if self.forward_stack.is_empty():
  25. return
  26. # 点击后退按钮,从 forward_stack 中弹出当前页面,并保存到 back_stack 中
  27. top = self.forward_stack.pop()
  28. self.back_stack.push(top)
  29. print('back to {}'.format(top))
  30. def forward(self):
  31. if self.back_stack.is_empty():
  32. return
  33. # 点击前进按钮,从 back_stack 中弹出,然后保存到 forward_stack 中
  34. top = self.back_stack.pop()
  35. self.forward_stack.push(top)
  36. print('forward to {}'.format(top))
  37. def __repr__(self):
  38. copy_forward_stack = copy.deepcopy(self.forward_stack)
  39. url_list = list()
  40. while not copy_forward_stack.is_empty():
  41. url_list.append(copy_forward_stack.pop())
  42. return " ".join("{}".format(url) for url in url_list)
  43. if __name__ == '__main__':
  44. browser = Browser()
  45. browser.open('a')
  46. browser.open('b')
  47. browser.open('c')
  48. print('open the browser: {}'.format(browser))
  49. if browser.can_back():
  50. browser.back()
  51. if browser.can_forward():
  52. browser.forward()
  53. browser.back()
  54. browser.back()
  55. browser.back()
  56. print('browser: {}'.format(browser))

输出结果:

  1. Open new url a
  2. Open new url b
  3. Open new url c
  4. open the browser: c b a
  5. back to c
  6. forward to c
  7. back to c
  8. back to b
  9. back to a
  10. browser:
总结

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

欢迎关注我的微信公众号--算法猿的成长,或者扫描下方的二维码,大家一起交流,学习和进步!

640?wx_fmt=png

如果觉得不错,在看、转发就是对小编的一个支持!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/花生_TL007/article/detail/536818
推荐阅读
相关标签
  

闽ICP备14008679号