目录
一、队列基本知识
二、队列在Java中的实现
1.Queue
2.Deque
①实现普通队列
②实现栈
③实现双端队列
3.基于底层数据结构
4.组合模式
三、相关算法题目
思路
代码
四、栈和队列总结
一、队列基本知识
队列只能在队尾添加元素，在队头删除元素，因此具有先进先出的特点（FIFO），比如排队，队列只能在首尾两端进行操作，做不到随机访问；
队尾入，队头处
常用操作方法：
入队（enQueue）：将元素添加到队列的末尾，如果队列已满，可能会抛出异常或返回错误（取决于实现）；
出队（deQueue）：在队头移除并返回队列的第一个元素，如果队列为空，可能会抛出异常或者返回错误；
获得队首元素（peek）：返回队列的第一个元素，但不移除它，如果队列为空，可能会抛出异常或返回错误；
判空（isEmpty）：检查队列是否为空，为空，返回true，不为空，返回false；
获取队列长度（size）：返回队列中元素的数量；
二、队列在Java中的实现
1.Queue
Queue是java中实现队列的接口（此处队列指普通队列，FIFO型），实现类有LinkedList（基于双向链表实现）、PriorityQueue（基于堆实现，元素按优先级出队），常用LinkedList；
Queue常用的方法有6个，分为3类：插入、移除、获取元素，每个方法存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null或false）；
| 操作失败情况 | 抛出异常 | 返回特殊值(null / false) | |
| 将元素e插入到队尾 | 超出队列容量 | boolean add(E e) | bollean offer(E e)：false |
| 获取并移除此队列的头 | 队列为空 | E remove() | E poll()：null |
| 获取但不移除此队列的头 | 队列为空 | E element() | E peek()：null |
参考：【Java】Java队列Queue使用详解_java queue-CSDN博客 博主：devnn
2.Deque
Deque 是一个双端队列接口，支持在两端插入和移除元素；继承自Queue接口；
Deque的实现类有ArrayDeque（基于动态数组实现）、LinkedList（基于双向链表实现）、LinkedBlocking Deque；
ArrayDeque在用作队列时快于LinkedList；
Deque有三种用途：普通队列、双端队列、栈，常用方法有12种，不同的数据结构实现选用不同方法；建议最好不要在Deque实现中插入null元素；
①实现普通队列
将元素添加到双端队列的末尾，从双端队列的开头移除元素，得到 FIFO（先进先出）行为
Deque<E> deque = new ArrayDeque<>();
Deque<E> deque = new LinkedList<>();
Queue<E> queue = new ArrayDeque<>();
Queue<E> queue = new LinkedList<>();
常用方法：从 Queue 接口继承的方法完全等效于 Deque 方法
| Queue方法 | 等效Deque方法 | ||
| 将指定元素插入Deque末尾 (入队) | 抛出异常 | boolean add(E e) | void addLast(E e) |
| 返回特殊值 | bollean offer(E e) | boolean offerLast(E e) | |
| 获取并移除Deque第一个元素（出队） | 抛出异常 | E remove() | E removeFirst() |
| 返回特殊值 | E poll() | E pollFirst() | |
| 获取但不移除Deque第一个元素 | 抛出异常 | E element() | E getFirst() |
| 返回特殊值 | E peek() | E peekFirst() |
示例代码：
Deque<String> deque = new LinkedList<>();//创建一个LinkedList实现类的对象
//Deque<String> deque = new ArrayDeque<>();//创建一个ArrayDeque实现类的对象
deque.addLast("A");
deque.addLast("B");
System.out.println(deque.removeFirst()); // 输出: A②实现栈
Deque<E> stack = new ArrayDeque<>();
Deque<E> stack = new LinkedList<>();
详见栈
代码随想录刷题day28|（栈与队列篇:栈）232.用栈实现队列-CSDN博客
③实现双端队列
Deque<E> deque = new ArrayDeque<>();
Deque<E> deque = new LinkedList<>();
Queue<E> queue = new ArrayDeque<>();
Queue<E> queue = new LinkedList<>();
注意：Queue接口只能实现队列，Deque接口既能实现队列，也能实现栈；
参考：【Java】Java双端队列Deque使用详解_dequeuejava-CSDN博客
3.基于底层数据结构
数组：使用循环数组实现
链表：使用单链表实现
了解即可
4.组合模式
原理类似栈，常用LinkedList（底层是链表）实现队列，ArrayList底层是基于动态数组，在ArrayList中，移除第一个元素会导致后面的所有元素向前移动一位，时间复杂度为O(n)，如果出队操作频繁，时间开销比较大；
示例代码
import java.util.LinkedList;public class ComposedQueue<E> {private LinkedList<E> list;public ComposedQueue() {list = new LinkedList<>();}// 入队public void enqueue(E element) {list.addLast(element);}// 出队public E dequeue() {if (isEmpty()) {throw new IllegalStateException("队列为空");}return list.removeFirst();}// 查看队首元素public E peek() {if (isEmpty()) {throw new IllegalStateException("队列为空");}return list.getFirst();}// 判断队列是否为空public boolean isEmpty() {return list.isEmpty();}// 获取队列大小public int size() {return list.size();}
}三、相关算法题目
225.用队列实现栈
思路
关键是出栈操作和获取栈顶元素操作，每次出栈时，将deque1中的元素倒序存入deque2中，原本元素队尾入，想要倒序就让元素从队头入，deque2运行addFirst(x)方法（从队头添加元素，元素顺序和deque1的入队出队顺序一致）即可实现，注意！倒序存入deque2的操作不需要在deque2为空时再操作，举个例子：
按照1 2 3的顺序
首先deque1执行push方法入队，deque1：（队头）1 2 3（队尾），相当于栈的入栈操作
deque2此时为空，将deque1中的元素倒序存入，deque2：3 2 1
deque2从队头出队：3 2 1，实现先进后出，相当于栈的出栈操作；
此时，按照4 5 的顺序再次入队deque1：4 5
如果之前deque2中只出队元素3，还剩元素2 1，此时不为空，假设时在deque2为空才运行addFirst方法，那么此时出栈操作，不会运行该方法，直接从deque2中移除元素，那么将会移除元素2，而在栈中，从栈顶往下应该是：5 4 2 1，应该出栈的是元素5
而每次出队时deque2都执行addFirst操作，此时deque2中：（队头）5 4 2 1（队尾）
出队元素为5，正确
代码
225. 用队列实现栈 - 力扣（LeetCode）
class MyStack {//成员变量Deque<Integer> deque1;Deque<Integer> deque2;public MyStack() {deque1 = new LinkedList<>();deque2 = new LinkedList<>();} public void push(int x) {//deque1入队deque1.addLast(x);} public int pop() {//deque1出队---倒序入队deque2---deque2出队method();return deque2.removeFirst();}public void method(){//确保deque2中包含的是deque1中所有元素的倒叙 不用借助数组 deque中有对应方法while(!deque1.isEmpty()){deque2.addFirst(deque1.removeFirst());}}public int top() {method();return deque2.getFirst(); } public boolean empty() {return deque1.isEmpty() && deque2.isEmpty();}
}四、栈和队列总结
java中栈和队列的实现有四种方式：
栈：Stack类、Deque接口、组合模式、底层数据结构（数组、链表）
队列：Queue接口和Deque接口、组合模式、底层数据结构（数组、链表）
其中Deque接口中两个实现类ArrayDeque和LinkedList都可以实现栈和队列，组合模式中通常封装List接口，创建其实现类ArrayList（底层数组）和LinkedList（底层链表）的实例对象，对于栈，常用ArrayList实现，对于队列，常用LinkedList实现；
对于栈，Stack类已经过时，java官方不推荐；
组合模式和底层数据结构的方式均需要手写方法，较为复杂，更推荐使用Deque接口；