【数据结构与算法】6.栈

1. 栈

1.1 栈的概念

栈：一种特殊的线性表，其**只允许在固定的一端进行插入和删除元素操作（表的末端）。**进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

对栈的基本操作有push（入栈）和pop（出栈），前者相当于插入，后者则时删除最后插入的元素。

栈又称为 LIFO（后进先出）表。

栈在生活中的例子：

图片1

1.2 栈的使用

2. 栈的模拟实现

栈的定义

定义一个数组，用于存储栈的元素

定义一个变量，用于记录栈的有效元素个数

定义一个常量NUMBER，其值为10，表示栈的默认大小

构造方法，初始化栈

栈的定义完整代码：

入栈（push操作）

定义方法判断栈是否已满（即是否还有入栈空间）：如果usedSize等于数组长度，则表示栈已满，返回true；否则返回false

判断栈是否已满（usedSize等于数组长度），则需要扩展数组的大小）,使用Arrays.copyOf方法将原数组复制一份，长度为原数组的两倍

将val存入数组的usedSize位置，并将usedSize加1，表示有一个新元素入栈

入栈完整代码：

出栈（pop操作）

判断栈是否为空，如果为空则抛出异常

EmptyStackException异常类：

不为空则usedSize - 1，表示有一个元素出栈

返回usedSize位置的元素值（即栈顶元素）

出栈完整代码：

查看栈顶元素（peek操作）

判断栈是否为空，如果为空则抛出异常

返回uesedSize - 1位置的元素值（即栈顶元素）

判断栈是否为空

如果usedSize等于0，则表示栈为空，返回true；否则返回false

3. 完整代码

MyStack类：

EmptyStackException类：