1、栈是什么

栈是一种特殊的线性数据结构，其只允许在固定的一端进行插入和删除操作。插入和删除的这一端被称为栈顶，而另一端则被称为栈底。栈遵循后进先出的原则，即最后插入的元素会最先被删除。这种特性使得栈在算法设计和问题解决中具有独特的优势。

2、栈的实现方式对比

• 数组实现：将数组的尾部充当栈顶，数据的插入与删除操作变得非常高效。同时数组的结构，使得其CPU高速缓存的命中率较高。唯一的缺陷就是，扩容或缩容会有一定的性能开销。
• 链表实现：采用单链表结构，将链表头部设为栈顶，数据的插入与删除操作同样能高效完成。但链表需要额外的存储空间来保存指针信息，且由于链表的结构，CPU高速缓存的命中率相对较低。此外，链表实现的复杂度相较于数组实现也更高一些。

3、函数栈帧

在函数调用过程中，系统会为每个函数分配一个栈帧。栈帧中存储了函数的局部变量、参数以及返回地址等信息。当函数执行完毕后，其栈帧会被销毁，从而释放占用的栈空间。函数栈帧的分配和销毁过程体现了栈的后进先出原则。

函数栈帧的存在使得函数调用具有嵌套性，即一个函数可以调用另一个函数，而被调用的函数又可以继续调用其他函数。这种嵌套调用关系通过栈来维护，确保了函数调用的正确性和稳定性。

---