微信网站制作平台,网站建设是一次性给钱还是什么,高级搜索引擎技巧,广告联盟app下载赚钱2019 年第 79 篇文章#xff0c;总第 103 篇文章数据结构与算法系列的第四篇文章#xff0c;前三篇文章#xff1a;前言浏览器的前进和后退功能怎么用栈来实现呢#xff1f;这里先介绍一下栈的定义和实现#xff0c;并介绍它的一些常用的应用#xff0c;最后再简单实现一… 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, nextNone): 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() 函数并执行相加时的情况。栈在表达式求值中的应用栈的另一个常用场景就是实现表达式求值编译器实现表达式求值的方法是通过两个栈来实现。一个保存操作数一个保存运算符。其实现思路如下从左到右遍历表达式遇到数字就压入操作数栈遇到运算符就和运算符栈的栈顶元素进行比较如果比栈顶元素的优先级高就压入栈如果比栈顶元素的优先级低或者是相同优先级就取出栈顶的运算符然后从操作数栈的栈顶取 2 个操作数进行计算后将计算结果放入操作数栈接着继续比较运算符和当前运算符栈的栈顶元素。这里给出一个例子如何计算表达式 35*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:总结本文先介绍了如何实现一个栈然后介绍了栈的几个应用包括函数调用、表达式求值、括号匹配、浏览器前进和后退的实现等。欢迎关注我的微信公众号--算法猿的成长或者扫描下方的二维码大家一起交流学习和进步如果觉得不错在看、转发就是对小编的一个支持
