目录
一、?栈（Stack）
1.?什么是栈？
?栈
?栈的特点
2.?栈的使用
3.?栈的模拟实现
4.?栈的优缺点
?优点：
?缺点:
二、?队列（Queue）
1.?什么是队列？
?队列
?队列的特点
2.?队列的使用
?实例化
?Queue中的方法
?队列的使用
3.?队列模拟实现
4.?队列的优缺点
?优点：
?缺点：
一、?栈（Stack）
1.?什么是栈？
?栈
栈是一种数据结构，他是一种只允许在一端固定进行插入和删除操作的特殊线性表。先进入的数据被压入栈底，最后进入的数据被放在栈顶，需要读出的数据从栈顶开始弹出，按照先入后出的原则。
操作：
入栈：也称为压栈/进栈，将插入的元素放在栈顶；
出栈： 将栈顶的元素进行删除；
?栈的特点
操作受限性：只允许在一端固定进行插入和删除操作，不像顺序表可以进行任意的插入和删除；数据存储的有序性：元素遵循先进后出的原则，即先入栈的元素后出栈；空间效率：无需像数组等数据结构分配存储大量的固定空间，可以根据元素的入栈和出栈发生动态变化，可以避免空间的浪费；时间复杂度：出栈和出栈的时间复杂度都为O（1），操作效率高；2.?栈的使用
栈的方法
| 方法 | 功能 |
| Stack（） | 构造一个空的栈 |
| E push（E e） | 将元素入栈 |
| E pop（） | 将元素出栈 |
| E peek（） | 获取栈顶元素 |
| int size（） | 获取栈中有效个数大小 |
| boolean empty（） | 判断栈是否为空 |
细心的同学观察图片和表格中的方法会发现，图片中并没有size方法，是因为Stack继承于Vector，他使用的size方法是Vector中的方法；
什么是Vector？
Vector继承与List接口，他与ArrayList相似，与ArrayList不同的是，Vector是线程安全，当其相对性能较低。在当线程的情况下，如果不需要线程安全，更推荐ArrayList。什么是线程安全？
线程安全指的是在多线程的环境下，程序或代码能过正确地运行，不会出现数据不一致、竞争条件、死锁等问题。方法的使用:
public static void main(String[] args) { Stack<Integer> stack=new Stack<>(); //入栈 stack.push(1); stack.push(2); stack.push(3); //获取有效个数大小 System.out.println(stack.size());//3 //获取栈顶元素 System.out.println(stack.peek());//3 //出栈 stack.pop(); //获取栈顶元素 System.out.println(stack.peek());//2 //查找元素下标 System.out.println(stack.search(2)); }3.?栈的模拟实现
//数组模拟实现栈public class MyStack { //元素 public int[] n; //有效元素大小 public int usedsize; //构造方法 public MyStack(int[] n) { this.n = n; } //入栈:将元素进行插入 //1.判断是否满了，满了用Arrays.copyOf进行扩容 //1.用元素放入数组中， //2.元素个数增加 public void push(int x){ if(isFull()){ this.n= Arrays.copyOf(n,2*n.length); } n[usedsize]=x; usedsize++; } private boolean isFull(){ return usedsize==n.length; } //出栈：将栈顶元素拿出 //1.判断栈是否为空； // 2.将栈中元素减减即可 public int pop(){ if(empty()){ return -1; } int val=n[usedsize-1]; usedsize--; return val; } //获取栈顶元素 //1.判断栈是否为空,如果为空抛出异常 // 2.获取栈中元素 public int peek(){ if(empty()){ throw new EmptyStackException(); } return n[usedsize-1]; } //判断栈是否为空 //看其有效个数是否为0 public boolean empty()throws EmptyStackException{ return this.usedsize==0; }}可以通过链表来模拟实现栈吗？
答案是：可以的；
1.如果采用单链表来实现：
采用的是头插法，入栈和出栈的时间复杂度都为O(1);采用的是尾插法，入栈的时间复杂度为O（n），如果有last，那么时间复杂度为O（1），但是出栈时间复杂度一定是O（n）；2.如果采用双链表来实现：
不管是头插法和尾插法都可以实现；4.?栈的优缺点
?优点：
数据存储的有序性：元素遵循先进后出的原则，即先入栈的元素后出栈；操作简单高效：栈的入栈和出栈操作都在栈顶进行，时间复杂度在为O（1），能迅速实现插入和删除；空间效率：无需像数组等数据结构分配存储大量的固定空间，可以根据元素的入栈和出栈发生动态变化，可以避免空间的浪费；?缺点:
功能有限：功能比较单一，只能在一端进行简单的插入和删除；数据访问有限：除栈顶元素外，访问其他元素需要一一弹出，操作麻烦且效率低；存储容量问题：虽然可以动态扩容，但是在大量元素入栈的时候，栈的连续空间可能受内存限制；二、?队列（Queue）
1.?什么是队列？
?队列
队列就像日常生活中的排队一样，一端用于插入元素，称为队尾；另一端用于删除元素，称为队头。其遵循的的是先进先出的原则。
操作：
入队：插入元素在队尾；出队： 删除元素在队头；?队列的特点
顺序性：队列按照先进先出的原则；操作受限性：队列主要集中于队头和队尾；存储结构的多样性：队列可以通过不同的存储结构来实现，常见的有数组和链表；并发处理优势：在多线程或多任务环境中，队列常用于实现数据的缓冲和同步；空间利用效率：可以实现空间的动态调整，提高空间的利用效率，避免空间浪费；队列的分类
普通队列：普通队列是队列最基本的形式，遵循先进先出的原则；
2.?队列的使用
?实例化
Queue是一个接口，不能实例化本身，但只要实现了这个接口都可以实例化，比如LinkedList、ArrayDeque以及PriorityQueue等等其他；
public static void main(String[] args) { Queue<Integer> queue=new LinkedList<>(); Queue<Integer> queue1=new ArrayDeque<>(); Queue<Integer> queue2=new PriorityQueue<>(); }?Queue中的方法
看下面的图片，我们可以发现他们分为两类使用效果相同，但是使用目的不同：
| 方法 | 功能 |
| boolean offer（E e） | 入列队 |
| E poll（） | 出列队 |
| peek（） | 获取队头元素 |
| int size（） | 有效元素个数 |
| boolean isEmpty（） | 判断是否为空 |
?队列的使用
public static void main(String[] args) { Queue<Integer> queue=new LinkedList<>(); //入队 queue.offer(1); queue.offer(2); queue.offer(3); //获取有效元素个数 System.out.println(queue.size());//3 //获取队头元素 System.out.println(queue.peek());//1 //出队 System.out.println(queue.poll());//1 }3.?队列模拟实现
普通队列用双链表模拟实现：
public class MyQueue { //创建节点类 static class ListNode{ public int val; public ListNode prev; public ListNode next; public ListNode(int val) { this.val = val; } } public ListNode first=null; public ListNode last=null; public int usedSize=0; //入队 //判断是否为空,如果为空将头尾节点都等于该新节点 //如果不是，将节点添加到队尾 //有效元素个数增加 public void offer(int val){ ListNode listNode=new ListNode(val); if(isEmpty()){ first=last=listNode; }else{ last.next=listNode; listNode.prev=last; last=listNode; } usedSize++; } //出队 //判断队列是否为空； //出队头元素,将队头指针向后移动 //使用元素个数减少 public int poll(){ if(isEmpty()){ return -1; } int val= first.val; first=first.next; if(first!=null){ first.prev=null; } return val; } //获取队头元素 //判断队列是否为空 //如果不为空，直接返回队头元素 public int peek(){ if(isEmpty()){ return -1; } return first.val; } //判断是否为空 //判断有效元素个数是否为0 public boolean isEmpty(){ return usedSize==0; }}4.?队列的优缺点
?优点：
顺序处理：能保证顺序的依次处理；数据缓存：可作为数据缓存区。防止数据丢失；动态扩展：队列实现可以按需要实现动态扩展；?缺点：
访问受限：遵循先进先出原则；存储限制：通常有长度限制，如果超过容量会有数据丢失；性能问题：如果队列过长，可能会导致性能下降；