Day6 - Stack Pre-Knowledge

Day6 - 栈前置知识

1. 栈的介绍

栈是一种抽象的数据类型，它支持push操作(在栈顶插入一个新元素)和pop操作(移除并返回最近添加的元素，即栈顶的元素)。作为一种抽象数据类型，栈可以使用数组或单链表来实现。

栈的操作通常被称为后进先出(LIFO)。

主要实现工具：栈顶指针、栈头（存储栈容量、栈数量、栈基底）

嵌套或递归函数调用都是通过栈来实现的，栈还用于实现深度优先搜索(DFS)，深度优先搜索可以使用递归或栈来实现。

函数的递归操作：实则是内存栈中的调用

其他应用：四则符号运算操作同理

2. 栈的实现

语言	对应接口
C++	std::stack
Java	java.util.Stack
Python	通过List 来模拟栈的操作
JavaScript	通过Array 来模拟栈的操作

3. 栈的复杂度

操作	时间复杂度
top	O(1)
push	O(1)
pop	O(1)
empty	O(1)
查找	O(n)

4. 栈边界条件

• 空栈（不要从空的栈里面取元素）

• 只有一个元素的栈。

• 只有两个元素的栈。