JAVA初阶数据结构栈（工程文件后续会上传）（+专栏数据结构练习是完整版）

1.栈的概念讲解(Stack)）

定义：栈是一种先进后出的数据结构

要想拿到12就要把它头上的所有东西给移出去 

 2.栈的实现（代码）

2.1栈的方法逻辑的讲解

（1）新建一个测试类Frank

（2）进入源码进行分析

其中栈就只有3个方法

pop （弹出元素）stack （放入元素）peek(输出元素)

其中如果选中pop相当于删除这个要弹出的元素

其中如果选中peek相当于获取栈内元素但是不删除

empty方法是用来判断栈是否为空的

（3）图解

栈本质上是一个数组()

定义一个useSize它的作用写道图片里面了

2.2栈中的push方法的实现（压栈操作）

先定义一个数组，（栈就是数组）然后定义一个数组长度usesize代表数组的长度，elem是数组，然后定义一个长度为10的数组。

 鉴于我们之前实现的顺序表的操作，我们首先要先定义一个判断栈是否为满的方法（isFull方法）

这个方法

 之后利用这个方法来实现入栈操作

如果这个数组为满，那么数组的长度就扩容两倍，之后useSize的第useSize+1的位置等于要先高要加入的元素

 2.3pop方法（弹出栈定元素操作）

我们删除只需要将上面的代码给usedSize给变成--然后剪刀3位置，然后回收

代码实现

首先定义一个isEmpty方法来判断数组是否为空

定义一个异常类，当发生数组为空的时候记得报错。

总体代码

 2.4peek（查看栈中元素（栈定元素）操作）

既然我们不需要进行弹出，那么我们就不需要usesize--来对数组（栈）进行操作

所以和上面代码差不多，如果想简化可以把return old改成elem【usiedsize--】

代码实现

2.5. 总结

入栈出栈的时间复杂度都为1，

2.6通过链表实现栈

通过链表实现栈可以使用单链表，也可以使用双链表，不管使用哪个链表一定要保证，入栈出栈的操作时间复杂度都为o（1）（我写的这些是为了能够让你们更好的了解）

2.6.1单向链表实现栈（可以实现队列和栈）

如果用尾插法那么遍历整个链表就不是o（1）

所以要用头插法

入栈用头插法

删除就删除头结点

图解

2.6.2双向链表实现栈（可以实现队列和栈）

双向链表的化head和last都可以来实现栈

由于在jdk中实现的就是双向链表，所以我们实例化一个双向链表

进入源码

 可以看到在源码中又push方法来压栈

其中还有pop方法来弹出栈

还有peek方法

k