栈又名堆栈，是一种运算受限的线性表，限定仅在表尾进行插入和删除操作的线性表。这一端被成为栈顶，相对地，另一端被成为栈底。向一个栈插入新元素被成为进栈，入栈或者压栈，它是把新元素放到当前栈顶元素的上面，使之成为新的栈顶元素。从一个栈删除元素又被成为出栈或者退栈，它是把当前栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读取数据的时候从栈顶开始弹出数据（最上面的数据被第一个读取出来）。栈具有记忆作用，对栈的插入和删除操作，不需要改变栈底指针。 栈是允许在同一端进行插入和删除操作的特殊线性表。允许插入和删除操作的一端称为栈顶（top），另一端为栈底（bottom）；栈底固定，而栈顶浮动；栈中元素个数为0时称为空栈。插入一般被称为进栈（push），删除则被称为退栈（pop）。因此栈也被称为先进后出表。 栈可以用来在函数调用的时候存储断点，做递归时要用到栈。 栈保存了一个函数调用时所需要的维护信息，这通常称为栈帧或者活动记录。栈帧一般包含以下信息：
- 函数的返回地址和参数。
- 临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量。 同顺序表和链表一样，栈也是用来存储逻辑关系为“一对一”数据的线性存储结构。 ![[Pasted image 20220404200753.png]]
- 栈只能从表的一端存取数据，另一端是封闭的。
- 在栈中，无论是存数据还是取数据，都必须遵循先进后出的原则，即最先进栈的元素最后出栈。从图中数据的存储状态可以判断出，元素1是最先进的栈，因此当需要从栈中取出元素1时，根据先进后出的原则，需要先将元素4，元素3，元素2从栈中取出，然后才能成功取出元素1。
基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：
- 向栈中添加元素，此过程被称为进栈（入栈或压栈）。
- 从栈中取出指定元素，此过程被称为出栈（或弹栈）。
栈是一种特殊的线性存储结构，因此对栈的具体实现有以下两种方式：
- 顺序栈：采用顺序存储结构可以模拟栈存储的特点，从而实现栈存储结构。
- 链栈：采用链式存储结构实现栈结构。