队列

队列的概念

队列是一种先进先出，后进后出的特点，是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
进行删除操作的一端为队头，另一端插入操作的为队尾

在这里插入图片描述
队列术语：

在末尾进行插入元素，叫做队尾
在删除元素时，只能从第一个元素开始删除，而第一个元素的位置称为队头
在向队列插入元素时称为入队（进队），新元素进队后就成为新的队尾元素
在队列删除元素时称为出队（离队），元素出队后，后一个元素就成为队首元素

队列的使用(Queue)

队列的使用是通过 Queue 来实现， Queue是个接口，底层是通过链表实现的

Queue包含的方法有：

方法名称	功能描述
`add(E)`	入队列
boolean `offer(E e)`	入队列（`offer`在容量受限制的情况下，不会抛异常）
E `remove()`	出队列，并返回队头元素，出队失败引发异常
E `poll()`	出队列，并返回队头元素
E `element()`	获取队头元素，获取失败引发异常
`peek()`	获取队头元素
int`size()`	获取队列中有效元素个数
boolean `isEmpty()`	检测队列是否为空

add方法与offer方法的区别：
两者都是在队列队头或队尾插入元素，前者（add）插入元素失败会引发异常，后者（offer）插入元素失败不会引发异常，只会以返回false的形式表示插入元素失败
remove方法与poll方法的区别：
remove方法与poll方法都是在队头或队尾删除并返回元素，前者（remove）删除元素失败会引发异常，后者（poll）删除元素失败不会引发异常，只会以返回null的形式表示删除元素失败
element方法与peek方法的区别：
两者都是在队列队头或队尾获取并返回元素，前者（get）获取元素失败会引发异常，后者（peek）获取元素失败不会引发异常，只会以返回null的形式表示获取元素失败
总结：
在有容量限制的情况下，使用 add（入队列）、remove（出队列）、element()（获取队头元素） 方法失败会引发异常
而使用 offer（入队列）、poll（出队列）、peek获取队头元素） 方法不会

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

public static void main(String[] args) {Queue queue = new LinkedList<>();queue.offer(1);// 入列queue.offer(2);queue.offer(3);queue.offer(4);System.out.println(queue.poll());//出队列System.out.println(queue.peek());//获取队列的第一个元素System.out.println(queue.isEmpty());//判断队列是否为空}

队列的模拟实现

队列可以用链式队列或者顺序队列来实现，但是队列使用链式队列实现更好
Java中队列是用双链表来实现的

例如：
使用双向链表来实现队列
在这里插入图片描述
使用双向链表来实现队列的具体过程和模拟实现LinkedLisd是一样的
不过是添加了入队和出队的方法

使用单链表来实现队列
在这里插入图片描述
代码示例：

public class MyQueue {static class ListNode{//定义节点public int val;//存放数值public ListNode next;//存放地址//初始化  构造方法public ListNode(int val) {this.val = val;}}public ListNode head;//头节点public ListNode tail;//尾节点public int usedSize;//记录节点个数// 入队public void offer(int val){ListNode node = new ListNode(val);if(head == null){head = node;tail = node;}else{tail.next = node;tail = tail.next;}usedSize++;}//出队public int poll(){if(head == null){return -1;}int ret = head.val;head = head.next;if(head == null){//如果是只有一个节点的情况下tail = null;//尾节点也要置空}usedSize--;//节点个数减1return ret;}//获取队列的头元素public int peek(){if(head == null){return -1;}return head.val;//返回队列的头节点}//判断是否为空队列public boolean empty(){return usedSize==0;}//返回队列元素个数public int getUsedSize(){return usedSize;}
}