赞
踩
2019 年第 79 篇文章,总第 103 篇文章
数据结构与算法系列的第四篇文章,前三篇文章:
浏览器的前进和后退功能怎么用栈来实现呢?
这里先介绍一下栈的定义和实现,并介绍它的一些常用的应用,最后再简单实现一个简单的浏览器前进和后退的操作。
栈是一种“操作受限”的线性表,只允许在一端插入和删除数据,特点就是后进先出、先进后出。
目录:
栈既可以通过数组实现,也可以通过链表实现。数组实现的栈,称为顺序栈;链表实现的栈,称为链式栈。
这里用 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()
函数并执行相加时的情况。
栈的另一个常用场景就是实现表达式求值,编译器实现表达式求值的方法是通过两个栈来实现。一个保存操作数,一个保存运算符。其实现思路如下:
这里给出一个例子,如何计算表达式 3+5*8-6
,如下图所示:
栈的第三个应用是可以检查表达式中的括号是否匹配。
通过栈来检查括号匹配问题的方法思路如下:
最后一个应用是实现浏览器的前进和后退功能,这里采用两个栈来解决。
我们使用两个栈,X 和 Y,我们把首次浏览的页面依次压入栈 X,当点击后退按钮时,再依次从栈 X 中出栈,并将出栈的数据依次放入栈 Y。当我们点击前进按钮时,我们依次从栈 Y 中取出数据,放入栈 X 中。当栈 X 中没有数据时,那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据,那就说明没有页面可以点击前进按钮浏览了。
实现代码如下所示:
- from Stack.linked_stack import LinkedStack
- import 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 a
- Open new url b
- Open new url c
- open the browser: c b a
- back to c
- forward to c
- back to c
- back to b
- back to a
- browser:
本文先介绍了如何实现一个栈,然后介绍了栈的几个应用,包括函数调用、表达式求值、括号匹配、浏览器前进和后退的实现等。
欢迎关注我的微信公众号--算法猿的成长,或者扫描下方的二维码,大家一起交流,学习和进步!
如果觉得不错,在看、转发就是对小编的一个支持!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。