【数据结构】队列(Queue)

Queue

定义

Java中的队列(Queue)是一种先进先出(FIFO)的数据结构。队列只允许在一段进行插入数据操作，称为入队，在另一端进行删除数据操作，称为出队。我们可以把队列形象看作为排队。在最前面的进行出队，从最后面进行入队。

队列的基本概念

FIFO原则：先进入队列的元素将先离开队列

队头：进行删除操作(出队)的一端

队尾：进行插入操作(入队)的一端

语法定义

public interface Queue<E> extends Collection<E> 

Java中队列的几种实现方式

Java提供了多种队列的实现，以下只是几种常见的队列实现：

1.LinkedList

·LinkedList类实现了Queue接口，因此可以用作队列

·它是一个双向链表，允许在两端进行高效的插入和删除操作

2.ArrayDeque

·ArrayDeque是一个基于动态数组的双端队列实现

·它提供了高效的插入和删除操作，并且没有容量限制(动态扩容)

·与LinkedList相比，ArrayDeque在大多数情况下性能更优，因为它没有链表节点的开销

3.BlockingQueue

·BlockingQueue是Java并发库中的一个队列接口(阻塞队列)，提供了线程安全的操作

·它适用于多线程环境，可以通过put()和take()方法阻塞线程，直到队列中有元素可以插入或取出

·常见的实现类有ArrayBlockingQueue、LinkedBlockingQueue等

注意：由于Queue是接口，不能直接创建实例。需要使用其实现类来创建实例。

如：Queue<Integer> queue=new ArrayDeque<>();

其实，在Java中，并不仅仅只有这三种实现方式，还有优先队列等。这三种队列的实现方式后续会专门讲解。

主要方法

入队：将元素添加到队列的末尾，返回boolean值表示是否成功入队

·boolean add(E e):但与offer方法有一点区别，在无法入队时会抛出异常

·boolean offer(E e)

出队：从队列的头部移除并返回元素

·E remove()：返回移除的元素，如果队列为空则会抛出异常

·E poll()：返回移除的元素，如果队列为空则返回null

查看队首元素：返回队列头部的元素但不移除它

·E element()：返回队首元素，如果队列为空则会抛出异常

·E peek()：返回队首元素，如果队列为空则返回null

上述便是Queue接口中的所有方法，在其实现类中还有其他方法。如：在ArrayDeque中有size()、isEmpty().....等方法

循环队列与双端队列

1.循环队列

·循环队列是一种基于数组的队列实现，通过"循环"使用数组空间来避免浪费

·它需要额外的逻辑来处理队列的空和满状态，通常通过保留一个位置或使用标记来判断

2.双端队列(Deque)

·双端队列允许在两端进行插入和删除操作，因此它比普通的队列更加灵活

·Java中的Deque接口及其实现类(如ArrayDeque、LinkedList)提供了双端队列的功能

循环队列和双端队列我们后续也会专门进行讲解。在本章，我们需要学习使用Queue的主要方法