写在前面
在面试过程中被问到:在写代码或者项目开发过程中,栈在什么场景出现过?
作者只回答了:二叉树的后续遍历中用到了。go defer居然没有回答上,还有函数调用、递归也没有回答上,太弱了!!!今天总结一下。
栈的使用场景
函数调用栈
在编程语言中,函数调用通常通过栈来实现。每次函数调用时,会将函数的参数、局部变量以及返回地址等信息压入栈中,在函数执行完毕后,再将这些信息从栈中弹出,控制流返回到调用点。
表达式求值
在编译器和解释器中,栈可用于表达式的求值,特别是涉及到中缀表达式转换为后缀表达式(逆波兰表达式)的过程中,以及后缀表达式的计算过程中。
内存管理
在操作系统中,栈被用于管理程序的内存空间。每个线程通常都有自己的栈空间,用于存储局部变量、函数调用信息以及线程执行时的状态等。
递归算法
递归算法通常使用栈来存储递归调用的上下文信息,以便在递归结束时能够正确返回。例如,深度优先搜索(DFS)算法中常用到递归实现,这时候栈可以用来存储遍历路径。
浏览器历史记录
浏览器的“后退”和“前进”功能通常使用栈来管理浏览历史记录。每次浏览器访问一个新页面时,会将该页面的地址压入栈中,当用户点击“后退”按钮时,则从栈中弹出上一个页面的地址。
撤销操作
在文本编辑器和图形编辑器等应用中,通常使用栈来实现撤销(undo)操作。每次用户执行操作时,会将操作的状态信息保存在栈中,当用户执行撤销操作时,则从栈中弹出最近的操作状态。
算法实现
栈在算法中有着广泛的应用,例如,深度优先搜索、括号匹配、迷宫求解、后序遍历二叉树非递归算法等算法都可以通过栈来实现。
网络协议
在网络协议中,栈被广泛应用于网络数据的传输和处理。TCP/IP协议栈是一个典型的例子,它将网络层、传输层、应用层等不同的协议通过栈的形式依次封装,完成数据的传输和处理。数据包从应用层一直传输到网络层,以栈的形式不断压入和弹出,确保数据的准确传递和处理。
go defer
o语言的defer语法就是栈实现的,先定义的defer后调用