栈

栈是一种操作被限制的线性表，操作只有两种：入栈、出栈。只能在栈顶进行操作。
栈只能后进先出，先进后出。

如何实现“栈”

栈可以用数组实现，也可以用链表实现。 用数组实现的栈叫顺序栈，链表实现的栈叫链式栈。

时空复杂度

不能动态扩容的栈：
时间复杂度:O(1)
空间复杂度:O(1)
平均时间复杂度:O(1)

可以动态扩容的栈：
最好时间复杂度:O(1)，最坏时间复杂度:O(1)
空间复杂度:O(1)
平均时间复杂度:O(1)

栈的应用

栈在函数调用中的应用：在操作系统中，程序运行的时候，每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用的函数执行完成，返回之后，再将这个函数对应的栈帧出栈。