1.栈

栈（Stack）是只允许在一端进行插入或删除操作的线性表。

栈的示意图：

• 栈顶Top：线性表允许插入和删除的那一端。（栈尾一端）
• 栈底Bottom：固定的，不允许进行插入和删除的另一端。（栈头一端）
• 不含元素的空表称空栈
• 假设某个栈S={a1,a2, … ,an}，如上图所示，则a1为栈底元素，an为栈顶元素。
• 由于只能在栈顶进行插入和删除操作，故进栈顺序为a1,a2, … ,an，出栈顺序为an, … ,a2,a1。因此，栈的操作特性是后进先出LIFO（Last In First Out），称为后进先出的线性表。
• 按存储方式可分为：顺序栈 和 链栈（链栈用S表示栈顶指针）

**应用场景：**递归调用、函数调用、表达式求值

2.队列

队列是一种操作受限的线性表，队列只允许在表的一端进行插入，在表的另一端进行删除。

• 可进行插入的一段称为队尾，可进行删除的一端称为队头。
• 队列的主要特点就是先进先出FIFO（First In First Out）。
• 依照存储结构可分为：循环队列、顺序队和链式队。

ac68fb42-4d76-11ec-83a4-ce3d0ca5d0cc.mp4

• 链队列删除元素时，一般情况下只移动头指针，但当删除最后一个元素时，尾指针将丢失，需对尾指针重新进行赋值。