(一).栈
1.栈的概念
栈是一种先进后出的顺序表，只允许在固定的一端进行插入和删除。进行插入和删除的一端称为栈顶，另一端称为栈底
在栈中，插入数据叫做入栈/压栈/进栈
删除数据也叫做出栈
在生活中，羽毛球就和栈类似，先放进去的球最后拿出来
2.模拟实现栈
这是Java提供的栈所提供的功能
所以接下来我们就要模拟实现这些功能
(1).创建成员变量
public int[] element; public int usedSize; public MyStack() { this.element =new int[10]; }首先我们要明确，实现栈我们是用数组进行实现，所以我们首先是要有一个数组，同时需要一个变量来记录当前栈我们所使用的个数
同时我们需要一个构造方法，即当程序运行起来的时候，我们首先开辟10个空间
(2).入栈
//入栈 public void push(int val){ //判断栈是否满了 if (isFull()){ //满了则需要扩容 this.element= Arrays.copyOf(element,2*this.element.length); }else{ this.element[this.usedSize]=val; this.usedSize++; } } private boolean isFull(){ return this.element.length==this.usedSize; }首先我们先判断栈是否满了，如果满了，则需要我们手动扩容，当然，我们自己实现的时候是2倍扩容
如果没满，我们只需要将下标为usedSize的数组的值设为val即可，同时usedSize要++
(3).出栈
//出栈 public int pop(){ //判断栈是否为null if (isEmpty()){ throw new EmptyStackException("栈为空，无法出栈"); } int value=this.element[this.usedSize-1]; this.usedSize--; return value; } private boolean isEmpty(){ return this.usedSize==0; }在出栈时，我们首先要判断栈是否为空，那么如何判断栈是否为空？
我们说过，usedSize表示栈中的数据个数，所以当usedSize=0的时候，此时栈就是空的
当栈不为空时，我们只需要将数组下标为usedSize-1位置的值返回即可，因为数组下标为usedSize位置表示即将插入数据的下标，而不是栈中最后一个数据的下标，所以我们要返回usedSize-1位置的下标
(4).查看栈顶的数据
public int peek(){ if (isEmpty()){ throw new EmptyStackException("栈为空，无法获取栈顶数据"); } return this.element[this.usedSize-1]; }首先同样我们也要先判断栈是否为空，如果为空，则抛出异常
public class EmptyStackException extends RuntimeException{ public EmptyStackException() { super(); } public EmptyStackException(String s) { super(s); } }如果不抛出异常，直接返回栈顶的数据
注意：查看栈顶的数据并不是出栈！！！
(5).判断栈是否为空
private boolean isEmpty(){ return this.usedSize==0; }我们只需要判断usedSize是否为0即可
3.链式栈
顾名思义，就是用链表来存储栈
此时，建议使用头插和头删来实现我们的push()和pop()方法，因为这样的时间复杂度低，为
O(1)，如果采用尾插尾删，你每次都需要找到前一个节点，这样的时间复杂度为O(N)。
如果使用双向链表，则push()和pop()的时间复杂度都是O(1)
4.栈，虚拟机栈，栈帧的区别
栈是数据结构中的其中一种数据结构
虚拟机栈是JVM虚拟机的一块内存
栈帧是封装了方法运行所需的所有信息的内存块
(二).队列
1.概念
队列是一种先进先出的特殊顺序表。只允许一端进行插入数据，另一端进行删除数据，进行插入数据的一端称为队尾，进行删除数据的一端称为队头。
插入数据也称为入队
删除数据也称为出队
2.模拟实现队列
这是Java提供的队列的方法，下面我们就模拟实现这些功能
(1).创建成员变量
static class ListNode{ public int val; public ListNode prev; public ListNode next; public ListNode(int val) { this.val = val; } }首先我们使用双向链表来实现我们的队列
同时提供一个构造方法来初始化我们的val
(2).创建头尾节点
public ListNode first; public ListNode last;接下来我们只需要对first和last进行操作即可
(3).入队
//入队 尾插 public void offer(int val){ ListNode node=new ListNode(val); if (isEmpty()){ this.first=this.last=node; }else{ this.last.next=node; node.prev=last; this.last=node; } } public boolean isEmpty(){ if (this.first==null){ return true; } return false; }入队我们采取的是尾插，首先我们先判断一下队是否为空
在判断队是否为空时，我们只需要判断头节点是否为空即可，如果为空，则表示整个队就是空的，此时返回true即可，否则返回false
如果为空，那么要入队的这个节点既是头节点也是尾节点
如果队不为空，那么只需要让last节点的后驱next指向node，然后让node节点的前驱prev指向last，同时让node成为新的尾即可
(4).出队
//出队 头删 public int poll(){ int value; if (isEmpty()){ System.out.println("队为空，无法删除"); return -1; }else{ value=this.first.val; this.first=this.first.next; if (this.first!=null){ this.first.prev=null; } } return value; } public boolean isEmpty(){ if (this.first==null){ return true; } return false; }出队，我们采取的是头删
首先依旧是先判断队是否为空，如果为空，则返回-1
如果不为空，我们通过变量value来接收first节点的值，然后让first=first.next，即让first指向下一个节点
然后我们需要判断一下此时的first是否为空，如果为空，说明此时这个队列只有一个头节点，所以我们就不需要将first的前驱置为空了，因为first此时已经为空了
如果此时的first不为空，那么我们将first的前驱再置为空
最后返回我们的value值
(5).获取队头元素
//获取队头元素 public int peek(){ if (this.first==null){ System.out.println("队为空，无法删除"); return -1; } return this.first.val; }首先我们先判断一下，队头是否为空，如果为空，则直接返回-1
如果不为空，直接返回first.val即可
3.循环队列
我们可以使用数组来实现一个循环队列
但是这样会有一个问题
当前五个数据都出队了之后，那么我们前五个数据的空间用不了了，也就是说每次出队之后都会浪费一个空间
那么我们该如何解决这个问题，同时我们如何判断这个顺序队是否满了和空了？
答：只要first和last相遇了，那么这个队列就空了
如何判断是否满了？
1.定义一个size来统计个数
2.添加一个标记，可以定义一个boolean类型的数据
3.浪费一个空间，即开辟空间的时候多开一个，在判断是否满了的时候，我们可以通过看last的下一个是否为first
但是还有一个问题
此时，当我想要在last的位置插入数据的时候，我该如何进行判断？
last+1==first吗？
这样肯定是不正确，因为，如果last再+1，那么数组就越界了，那我们该如何解决？
我们可以这样判断
(last+1)%arr.length
我们可以想一想是不是这样，此时last=10，此时数组的长度为11，那么就是(10+1)%11
正好等于0，恰好可以解决我们的问题
那么我们该如何判断满？
同样要进行模除
即如果(last+1)%arr.length==first，此时队列就满了
完整版代码
public int first; public int last; public int[] arr; public test(int k) { arr=new int[k+1]; } public boolean enQueue(int value) { if(isFull()){ return false; } arr[last]=value; last=(last+1)%arr.length; return true; } public boolean deQueue() { if(isEmpty()){ return false; } first=(first+1)%arr.length; return true; } public int Front() { if(isEmpty()){ return -1; } return arr[first]; } public int Rear() { if(isEmpty()){ return -1; } int index=last==0?arr.length-1:last-1; return arr[index]; } public boolean isEmpty() { return first==last; } public boolean isFull() { return first==(last+1)%arr.length; }4.双端队列
双端队列，允许两端都可以进行插入和删除数据
可是通过上面的图片我们可以看到，Queue和双端队列Deque都是接口，不能实例化，那么我们要怎么进行使用？
通过上面的图片我们可以看到，我们的双向链表是实现了Deque接口的
同时Deque接口继承了Queue接口
也就是说我们可以实例化一个LinkedList接口然后用Deque接收，我们就可以使用双端队列的方法了
同样也可以实例化一个LinkedList接口然后用Queue接收，就可以使用普通队列的方法了
同样，站和队列都可以使用Deque接口
public static void main(String[] args) { //双端链式队列 Deque<Integer> deque1=new LinkedList<>(); //双端数组队列 Deque<Integer> deque2=new ArrayDeque<>();//底层是一个数组 }
