栈
日常业务中的确很少用到栈这个数据结构。但是实际上,代码中无处不是栈,为什么?因为函数调用就是通过栈来实现的。
首先我们来看看栈是怎样一种结构。维基百科上这样定义:
In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations:
push, which adds an element to the collection, and
pop, which removes the most recently added element that was not yet removed.
The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out).
也就是说,栈有这样的特性:
- 栈有两个操作,一个是push,即把数据压入该数据结构;另一个是pop,即从该数据结构中弹出一个数据
- 每次执行pop操作时,得到的总是该数据结构中最后进入的一个数据。
举个例子,如果我们按照下述步骤进行操作,那么会是这样的:
push 1
。栈中的数据是1
,没有数据返回。push 2
。栈中的数据是1, 2
,没有数据返回。push 3
。栈中的数据是1, 2, 3
,没有数据返回。pop
。栈中的数据是1, 2
,返回的数据是3。pop
。栈中的数据是1
,返回的数据是2。
栈的实际使用
上面我们说到,栈的一个典型应用就是函数调用。我们来看看函数调用是怎么通过栈来实现的。有以下代码:
def inner(foo):
print("进入inner函数")
print("离开inner函数")
def outter(bar):
print("进入outter函数")
inner(bar)
print("离开outter函数")
if __name__ == "__main__":
outter("hey")
我们来看看调用结果:
$ python stack.py
进入outter函数
进入inner函数
离开inner函数
离开outter函数
一个典型的函数调用过程,就是把函数调用之后要执行的指令的地址压入栈中(例如此处outter中调用inner之后的地址),然后将要 调用的函数压入栈中,随后将(部分)参数压入栈中,然后把要执行的指令的地址改为所调用的函数的地址,当这个函数执行完成之后, 便会找到此前所保存的返回地址,再接着执行原本函数中的代码。
总结
这一篇中我们首先介绍了栈的基本属性,然后模拟了一个栈的执行,接着我们了解了栈这个数据结构在实际编程中的应用,那就是函数调用。
参考资料:
更多文章
本站热门
- socks5 协议详解
- zerotier简明教程
- 搞定面试中的系统设计题
- frp 源码阅读与分析(一):流程和概念
- 用peewee代替SQLAlchemy
- Golang(Go语言)中实现典型的fork调用
- DNSCrypt简明教程
- 一个Gunicorn worker数量引发的血案
- Golang validator使用教程
- Docker组件介绍(二):shim, docker-init和docker-proxy
- Docker组件介绍(一):runc和containerd
- 使用Go语言实现一个异步任务框架
- 协程(coroutine)简介 - 什么是协程?
- SQLAlchemy简明教程
- Golang的template(模板引擎)简明教程