栈，又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。


扩展资料：
1、栈(stack)与堆(heap)都是Java用来在Ram中存放数据的地方。与C++不同，Java自动管理栈和堆，程序员不能直接地设置栈或堆。
2、栈的优势是，存取速度比堆要快，仅次于直接位于CPU中的寄存器。但缺点是，存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。
另外，栈数据在多个线程或者多个栈之间是不可以共享的，但是在栈内部多个值相等的变量是可以指向一个地址的，详见第3点。
堆的优势是可以动态地分配内存大小，生存期也不必事先告诉编译器，Java的垃圾收集器会自动收走这些不再使用的数据。但缺点是，由于要在运行时动态分配内存，存取速度较慢。

1、函数执行流程
(调用函数，保存当前的内容，压栈函数并创建栈帧。执行里面的语句)
全局帧中生成foo1、foo2、foo3、main的函数对象。(栈，先进后出，后进先出)。
main函数调用
main 中查找内建函数print压栈，将常量字符串压栈，调用函数，弹出栈顶。
main中全局函数foo1压栈，将常量100,101压栈，调用函数foo1，创建栈帧。Print函数压栈，字符串和变量b、b1压栈，调用函数，弹出栈帧，返回值。
Main中全局查找foo2函数压栈，将常量200压栈，调用foo2，创建栈帧。foo3函数压栈，变量c引用压栈，调用foo3，创建栈帧。foo3完成print函数调用后返回。foo2回复调用，执行print后，返回值。Main中foo2调用结束弹出栈顶，main函数继续执行print函数调用，弹出栈顶，main函数返回。
2、递归：函数直接或者间接调用自身就是递归。
递归需要有边界条件、递归前进段、递归返回段。
递归一定要有边界条件。
当边界不满足的时候递归前进。
当边界条件满足的时候，递归返回。
斐波那契数列：
pre = 0
cur = 1
print(pre,cur,end = ' ')
n=4
for i in range(n-1):
pre,cur = cur ,pre + cur
print(cur,end=' ')
def fib(n):
return 1 if n<2 else fib(n-1)+fib(n-2)
for i in range(5):
print(fib(i),end=' ')
3、递归要求
递归一定要有退出条件，递归调用一定要执行到这个退出条件，没有退出条件的递归调用，就是无限调用。
递归调用的深度不宜过深。
Python中对递归调用的深度做了限制，以保护解释器。
超过递归调用深度，会抛出异常的。
4、递归的性能
循环稍微复杂一些，但是只要不是死循环，可以多次迭代直至算到结果。
改进。左边的fib函数和循环的思想类似。
参数n是边界条件，用n来计数。
上一次的计算结果作为下一次结果的实参。
import datetime
n=35
start = datetime.datetime.now()
def fib(n):
return 1 if n<2 else fib(n-1)+fib(n-1)
for i in range(n):
print(fib(i),end='')
delta = (datetime.datetime.now()-start).total_seconds()
print(delta)
效率比较低。
pre = 0
cur = 1
print(pre,cur,end=' ')
def fib(n,pre=0,cur=1):
pre,cur = cur,pre + cur
print(cur,end=' ')
if n == 2:
return
fib(n-1,pre,cur)
print(fib(5))
#斐波那契数列改进方式
左边的fib函数和循环的思想类似
参数n是边界条件，用n来计数。
上一次的计算结果作为函数的实参。
效率很高
和循环相比，性能相近，所以说递归效率不一定很低。但是深度有限。
5、间接递归
def  foo1()：
foo2()
def  foo2()：
f1oo()
foo1()
是通过别的函数调用了函数本身。
但是，如果构成了循环递归调用时非常危险。
6、递归总结
是一种很自然的表达，符合逻辑思维。
相对运行效率较低，每次调用函数都要开辟栈帧
递归有深度限制，如果递归层次太深，函数反复压栈，栈内存很快就溢出了。
如果有限次数的递归，可以使用递归调用，或者使用循环替代，循环代码稍微复杂,但是只要不是死循环，可以多次迭代直至算出结果。
绝大多数递归，都可以使用循环实现。
即使代码很简单，但是能不用则不用递归。

以前用过C++，知道它里面有一个内联函数这个概念，一般情况用inline关键字修饰，在C++定义类时，那种写中Class定义里面的函数，也被编译器当做内联函数处理。
说了这么多，还没说什么是内联函数。所谓内联函数就是指函数在被调用的地方直接展开，编译器在调用时不用像一般函数那样，参数压栈，返回时参数出栈以及资源释放等，这样提高了程序执行速度。
现在该说Java了，对应Java语言中也有一个关键字final来指明那个函数是内联的，例：
Java代码  
public final void doSomething() {
// to do something
}
该方法在被调用时，会在调用处直接展开使用，从而提高程序执行速度。此外final关键字还有一个作用，防止doSomething方法在子类中被覆盖，如果你希望doSomething是一个最终行为的话，那它应该被设计成final。
内联不一定好，当被指定为内联的方法体很大时，展开的开销可能就已经超过了普通函数调用调用的时间，引入了内联反而降低了性能，因为在选择这个关键字应该慎重些，不过，在以后高版本的JVM中，在处理内联时做出了优化，它会根据方法的规模来确定是否展开调用。
--------------------------------------------------------华丽的分界线-------------------------------------------------------
doug lea写类库是各种优化方法都会想到呀。

什么是栈？

ps:文章来自于网络

当提及“栈”这个概念，很多初学者都会很迷茫。在C语言里，我们有一个内存区域叫做栈区。在单片机里，我们又常常听到一个操作叫做压栈。而在算法中，我们也有一个同名结构叫做栈。

我常常会问自己的学生“栈”这个字的意思到底是什么?大家想到的多是客栈。我们翻翻字典也不难发现，栈的第一个释义是：储存货物或供旅客住宿的房屋。所以客栈的想法并没有错，但是这也未免太过抽象。

我们先来解释一下在计算机领域什么是栈。



栈某种意义上讲，它像是一个开口的盒子，先放进去的东西总是会被后放进去的东西压在下面，那么如果想拿出被压住的东西，必须要先取出顶部的东西，也就是后放进去的东西。换个说法就是先入后出。那它有点像什么呢?想象一下装在盘子里的若干张油饼。



对，他们是摞在一起的。如果想拿下面的油饼是不是要先拿开上面的呢?或许，这就是栈的根源。但是，又和“栈”这个字有什么关系呢?单纯的从释义上看，好似找不出什么关联性。但是当我们打开汉英词典：



对计算机中提及的“栈”的英文愿意是stack!我们一定要记得，是一群说英语的人创造了计算机，也是他们研究了初的算法。那么stack又是什么意思?



注意箭头指向的那一摞书们，和饼们的相处方式是不是很像!堆叠到一起。那个根源出来了，其实栈就是一种将数据依次“堆叠”的一种数据组织方式。

或者到这里，我们恍然大悟，哦，原来是这样!栈还有堆叠的意思。但是，我个人更觉得这是一种初期程序员之间的交流翻译吴缪。暂且放下这个不谈，至少我们明白一件事情，在某些领域，如果一个词汇很生涩，那么，不妨去查找一下他的英文愿意，或许你会有更深入的收获。

我们在来探讨下一个话题——“栈”stack，这种摞大饼大数据组织方式到底有什么用?

比如说，你有一些书，我们通常会这样摆放：



而不是这样：



为什么呢?当然是第二种摆放方式不方便拿其中的某一本书。可是在“栈”(stack)结构里面，“书”就是这样摆放的。那也就是说，“栈”(stack)不适合存放需要随机查找的东西。那它能做什么呢?

首先说说CPU里的“堆栈”。我们可以这样设想：一个CPU等同于一个完全没有记忆力的人，他只知道按照一份很详细的说明文档(也就是程序)来一步一步做某件事情，并且，他永远不会记得之前做过什么。我们在电影里常常会看到这样的情节，失忆症的人常常会随身携带一些本子和照片，然后按顺序把发生的事情记录下来，方便自己查阅。CPU也有这样的需求。

在CPU里，有一种机制叫做“中断”interrupt，就是中途插一嘴的意思。怎么插呢?比方说，你正在玩儿一个单机游戏，在更要通关的时候，外面突然有人敲门。那么是不是要把你的游戏暂停一下?然后再去开门。然后正在你去开门的路上，厨房的煤气报警器响起，是不是要赶紧去厨房看一下是不是误报警?确认是误报警后，我们是先去开门呢?还是继续打游戏呢?对于CPU来说，也会有同样的困惑。对于人，我们或许可以思考一下——哦，开门这件事器比较紧迫，应该先开门。但是对于CPU来说，又如何区分紧迫度呢?这就变成了一个很麻烦的问题。我们回头再想想“栈”，他是如何组织数据的?先入后出。玩游戏是先发生的事情，那么打断他的事情就是更紧迫的事情，开门虽然比游戏紧迫，但是他次于煤气报警，所以，它才是紧迫的事情。不过到现在也应该注意到了。紧迫的事情往往在后产生，又要被优先处理。

在CPU的中断机制里，每当cpu执行的一个任务被打断时，cpu就需要备份当前的处理状态，就像没有记忆的人，总是要记笔记拍照。那么cpu怎么区分优先次序呢?就像你吃盘子里的饼!先拿上面的。而存储数据的过程，就像你向盘子里放饼的过程。

再说说C语言分段里的“栈区”，我们都知道，局部自动变量分配到内存的“栈区”，栈区里的数据组织方式也类似摞饼，每当你调用了一个子函数，那么编译器会将子函数里的局部变量分配到栈区的栈顶位置(与当前函数的空间相邻)，当子函数在再调用另一个函数是，也是会做同样处理。儿关于局部变量的释放，其实本质就是讲栈顶的一块空间的使用权归还回去，看起来就好像客栈一样，来人的时候开房，走人的时候退房。或许这也是stack会被翻译成“栈”的原由。

后在来说“栈”，这种单纯的逻辑结构。它和前两者一样，遵循类似先入后出的数据处理规则。



那这个“盒子“什么时候会用到呢?典型的例子，就是迷宫算法(具体细节可以自己搜索一下)，我们可以用栈来存放已经走过的有效路线。也或者利用栈来模拟局部变量分配，实现将递归算法转换为非递归。也或者利用栈来优化，自己的程序处理逻辑，在实际问题解决中，如果你涉及到了临时保存数据，那么你可以尝试考虑一下使用栈，或许可以让自己的程序在逻辑上变得更加清晰明了。

简单的总结一下：所谓“栈”，其实就是一本 相互堆叠的便签儿。我们可以逐次备份自己要保存的信息，然后在反向依次处理。