队列的基本概念

\qquad











队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，在表的后端进行插入操作，与栈一样，队列是一种操作受限制的线性表。




\qquad











进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素，称为空队列。

队列分类：


按照实现方式：

（1）单向队列（Queue）:只能在一端插入数据，在另一端删除数据。

（2）双向队列（Deque）:每一端都可以进行插入数据和删除数据操作。

（3）优先级队列：优先级队列是比栈和队列更专用的数据结构，在优先级队列中，数据项按照关键字进行排序，关键字最小（或者最大）的数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。

按照存储方式：

队列与栈一样是一种线性结构，因此以常见的线性表如数组、链表作为底层的数据结构，以数组、链表为底层数据结构构建队列。

（1）基于数组的顺序存储方式




缺点

：通过出队列操作将数据弹出队列后，font指针之前的的空间就不能再次得到了，这样导致了大量的空间丢失。


使用循环数组作为存储结构：





\qquad











为了解决上述问题，将普通数组换成循环数组，在循环数组中，末尾元素的下一个元素不是数组外，而是数组的头元素。 这样就能够再次使用front之前的存储空间了。



(2)基于链表的链式存储方式




\qquad











队列的链式存储可以使用单链表来实现。了操作实现方便，这里采用带头结点的单链表结构。 根据单链表的特点，选择链表的头部作为队首，链表的尾部作为队尾。




\qquad











除了链表头结点需要通过一个引用来指向之外，还需要一个对链表尾结点的引用，以方便队列的入队操作的实现。为此一共设置两个指针，一个队首指针和一个队尾指针，如图 所示。




说明

：队首指针指向队首元素的前一个结点，即始终指向链表空的头结点，队尾指针指向队列当前队尾元素所在的结点。当队列为空时，队首指针与队尾指针均指向空的头结点

队列（Queue）方法:

Queue是java中实现队列的接口，它总共只有6个方法，我们一般只用其中3个就可以了。Queue的实现类有LinkedList和PriorityQueue。最常用的实现类是LinkedList，因为LinkedList进行插入、删除操作效率较高




\qquad











队列的语法结构：

  （1）  Queue<String>  queue = new LinkedList<String>();  
         queue.offer()       将元素添加到队列末尾，若添加成功则返回true，该操作主要是给            容量受限的队列设计的。
         queue.poll()         从队首删除并返回该元素
         queue.peek()       返回队首元素，但是不删除 

说明

：add() 、 remove() 、 element() 方法的使用与上面方法一一对应，但是区别就是操作失败（因容量超出或容量为零时的操作）的时候会抛出异常NoSuchElementException，而上述方法对应返回false 、 false、null。

 （2） Deque<String> deque  =  new LinkedList<String>();

说明

： 双向队列(Deque),是Queue的一个子接口，双向队列是指该队列两端的元素既能入队 (offer) 也能出队 (poll), 如果将Deque限制为只能从一端入队和出队，则可实现栈的数据结构，对于栈而言，有入栈(push)和出栈(pop)，遵循先进后出原则。

（3）PriorityQueue<Integer>  p = new PriorityQueue<Integer>();