目录：

一. 栈（Stack）

1.  栈的概念和特点
2. 栈的使用
3. 栈的模拟实现
4. 栈的优点和缺点

二. 队列（Queue）

1. 队列的概念和特点
2. 队列的使用
3. 队列的模拟实现
4. 队列的优点和缺点

一. 栈（Stack）

1.什么是栈？

栈：是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。

 栈在生活中的例子：

 

 

栈的特点： 

操作受限：只允许在一端固定进行插入和删除操作。

有序性：元素遵循先进后出的原则，即先入栈的元素后出栈。

空间效率：无需像数组等数据结构分配存储大量的固定空间，可以根据元素的入栈和出栈发生动态变化，可以避免空间的浪费；。

时间复杂度：出栈和出栈的时间复杂度钧为O（1），操作效率高。

2.栈的使用

方法的使用

 

 4.栈的模拟实现

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

 当然栈也可以通过链表来实现。

4.栈的优缺点

优点
       栈结构简单、操作高效，入栈和出栈都只在栈顶进行，时间复杂度为 O(1)，存取速度快，且不易产生内存碎片，非常适合函数调用、递归、括号匹配、撤销操作等需要后进先出的场景。
 
缺点
       栈的访问限制严格，只能访问栈顶元素，无法随机访问或修改中间数据；用数组实现时容量固定，容易出现栈溢出，整体灵活性差，不适合需要频繁遍历、查找或随机操作的场景。

 

二.对列（Queue）

1.什么是队列？

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

原则：先进先出 

操作：

•  入队：插入元素在对尾。
• 出队：删除元素在对头。

队列的特点：

       队列是先进先出（FIFO）的线性数据结构，数据从队尾入队，从队头出队，不允许插队、不允许从中间取出。操作简单，入队和出队效率高，适合排队、任务调度、消息处理等需要按顺序公平处理的场景。

队列的使用：

在Java中，Queue是个接口，底层是通过链表实现的。

 

 

 注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

 

2.队列的分类:

普通队列：普通队列是队列最基本的形式，遵循先进先出的原则：

 

双端队列（Dequeue）：双端队列允许两端进行插入和删除操作，元素可以从队头出队和入队。

 

循环队列：循环列队是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的闭环。

循环列表判满：

1. 通过添加 size 属性记录
2. 保留一个位置
3. 使用标记
 

 

 

3.队列的模拟实现：

 4.队列的优缺点：

优点：
 队列遵循先进先出原则，结构简单、操作高效，入队和出队时间复杂度均为 O(1)，能保证数据处理的有序性与公平性，适合任务排队、消息处理、缓冲等按顺序执行的场景。
 
缺点：
队列只能在队头删除、队尾插入，无法随机访问或修改中间元素；顺序队列易出现假溢出，链式队列虽可动态扩容但会占用额外空间，整体灵活性较差。