一 什么是栈(stack)?
只允许在一端插入或删除的线性结构。先进后出,类似拿盘子一样,先放上去的盘子后被拿走,后放上去的盘子先被拿走(Last in First out),即后进来的数据先出栈。
栈可以用数组/链表实现,数组/链表长度即是栈的大小,分别叫顺序栈、链栈。
在顺序栈中,栈底即为数组头部元素,栈顶即为数组尾部元素。
二 栈的常用操作
1.入栈:stack.push()
2.出栈:stack.pop()
3.判断栈是否为空:stack.is_empty()
4.查看栈顶元素:stack.get_top()
1 | class Stack: |
三 栈与递归
递归:调用函数自己。
函数每往下递归一次,就会把运算结果放到栈中保存,直到程序执行到边界条件(递归出口),然后会把保存在栈中的元素按照后进先出的顺序一个个返回,最终得到结果。
以斐波那契数列为例:
1 | def fib(days): |
在上式,只有当fib(days)分解到了fib(0)和fib(1)才会退出,一层一层返回运算的值。
在上个fib里,有大量的重复计算单元,可以考虑用一个记忆的字典记住,来减少重复计算
优化的fib数列
1 | record = {} |