admin管理员组文章数量:1567554
如何实现浏览器的前进和后退功能？
1、栈：后进者先出，先进者后出。栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。：不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。
2、顺序栈的动态扩容
3、栈的应用
※ 调用函数： 操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
int main() {
int a = 1;
int ret = 0;
int res = 0;
ret = add(3, 5);
res = a + ret;
printf("%d", res);
reuturn 0;
}
int add(int x, int y) {
int sum = 0;
sum = x + y;
return sum;
}
※ 表达式求值：3+5*8-6
编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。
① 如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；
② 如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
※ 括号的匹配
我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。
当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。
\quad
① 如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。
\quad
② 如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。
当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。
class Solution:
def isValid(self, s: str) -> bool:
stack = [] # 设置一个列表，把该列表当做栈来使用即可
dic = {')':'(', '}':'{', ']':'['} #使用字典存储括号,并且右括号为key,左括号为value
for char in s:
if char in dic.values(): #左括号就入栈
stack.append(char)
elif char in dic.keys(): #有右括号的话就进行比较，
if stack==[] or dic[char] != stack.pop():
return False
else:
return False #不再字典中的输入直接输出错误
return stack ==[]
4、利用栈实现浏览器的前进和后退功能
我们使用两个栈，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：
版权声明：本文标题：如何实现浏览器的前进和后退功能？ 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dianzi/1725797714a1043182.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论