具有后进先出特点的数据结构

栈和栈帧

栈（Stack）：

栈是计算机科学里最重要且最基础的数据结构之一，它按照FILO（FirstInLastOut，后进先出）的原则存储数据。

栈的主要特点包括：

栈顶和栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。

压栈（入栈）：栈的插入操作，即将新元素添加到栈顶。

弹栈（出栈）：栈的删除操作，即从栈顶移除元素。

从技术上说，栈是CPU寄存器里的某个指针（如x86/x64平台的ESP寄存器/RSP寄存器，以及ARM平台的SP寄存器）所指向的一片内存区域。

操作栈的最常见指令是PUSH（压栈）和POP（弹栈）。

PUSH指令：对栈指针寄存器的值进行减法运算（通常是减去4或8，取决于系统位数），然后将操作数写入栈指针所指向的内存中。

POP指令：从栈指针指向的内存中读取数据，通常将其写入其他寄存器中，然后将栈指针的数值加上4或8。

栈在进程中的作用包括：

暂时保存函数内的局部变量。

调用函数时传递参数。

保存函数返回的地址。

栈帧（StackFrame）：

栈帧也叫过程活动记录，是编译器用来实现过程/函数调用的一种数据结构。

栈帧是利用EBP（栈帧指针）寄存器访问局部变量、参数、函数返回地址等的手段。

每一次函数的调用，都会在调用栈上维护一个独立的栈帧。

每个独立的栈帧一般包括：

函数的返回地址和参数：用于在函数调用结束后返回正确的位置，并传递必要的参数。

临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量，用于在函数执行过程中存储数据。

函数调用的上下文：保存函数调用时的环境信息，以便在函数返回后能够恢复到正确的执行状态。

栈是从高地址向低地址延伸的，一个函数的栈帧用EBP和ESP这两个寄存器来划定范围。

EBP指向当前栈帧的底部（即栈帧的起始位置），而ESP始终指向栈帧的顶部（即当前栈顶的位置）。

在函数调用过程中，EBP保持不变，因此可以安全地访问函数的局部变量、参数等。

而ESP则会随着压栈和弹栈操作而变化，始终指向栈顶。

在函数调用开始时，通常会先将当前的EBP值压栈保存，然后将当前的ESP值赋给EBP，从而确定新的栈帧的底部。

在函数执行过程中，可以通过EBP加上或减去一定的偏移量来访问栈帧内的局部变量、参数等。

在函数返回前，需要将ESP恢复到函数调用前的值（通常是通过将之前保存的EBP值弹出到ESP中），然后弹出返回地址并跳转到该地址继续执行。

综上所述，栈是一种后进先出的数据结构，用于存储临时数据；而栈帧则是函数调用时用于管理局部变量、参数和返回地址等的一种数据结构，通过栈帧可以实现函数的调用和返回。

后进先出法的数据结构

栈与以下多个方面有关：

后进先出（LIFO）原则：

栈是一种遵循后进先出原则的数据结构，即最后进入栈中的元素最先被取出。

这是栈的核心特性，使其与其他数据结构（如队列）区分开来。

操作：

栈支持三种基本操作：压栈（Push）、出栈（Pop）和查看栈顶元素（Peek）。

压栈是将一个元素添加到栈顶，出栈是从栈顶移除一个元素，而查看栈顶元素则是查看栈顶元素但不移除它。

应用场景：

栈在多个领域有广泛应用，如函数调用（函数调用栈）、递归（存储函数调用的状态）、表达式求值（存储操作数，特别是在逆波兰表达式中）以及语法分析（在编译原理中实现语法分析器）。

实现方式：

栈可以通过数组或链表来实现。

数组实现较为简单，但存在栈满的风险；链表实现则更加灵活，但可能会增加额外的内存开销。

性能：

栈的操作通常是O(1)的时间复杂度，这意味着无论栈的大小如何，操作的时间都是常数级别的。

这使得栈在高性能场景中非常有用。

数据类型：

栈可以存储任何类型的数据，包括基本数据类型（如整数、浮点数等）和复杂的数据结构（如对象、数组等）。

这使得栈成为一种非常灵活和通用的数据结构。