一、什么是队列？
队列是一种“操作受限”的线性表，只允许在一端插入和另一端输出。
队列和栈都是操作受限的线性表，区别在于栈是一头操作的，先进后出，后进先出，队列是尾部进入，头部输出。
队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
二、队列的类型
1.顺序队列
用数组实现的队列叫作顺序队列
//大佬写的代码
// 用数组实现的队列
public class ArrayQueue {
// 数组：items，数组大小：n
private String[] items;
private int n = 0;
// head表示队头下标，tail表示队尾下标
private int head = 0;
private int tail = 0;
// 申请一个大小为capacity的数组
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入队
public boolean enqueue(String item) {
// 如果tail == n 表示队列已经满了
if (tail == n) return false;
items[tail] = item;
++tail;
return true;
}
// 出队
public String dequeue() {
// 如果head == tail 表示队列为空
if (head == tail) return null;
// 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
String ret = items[head];
++head;
return ret;
}
}
//他自己优化的代码
// 入队操作，将item放入队尾
public boolean enqueue(String item) {
// tail == n表示队列末尾没有空间了
if (tail == n) {
// tail ==n && head==0，表示整个队列都占满了
if (head == 0) return false;
// 数据搬移
for (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
// 搬移完之后重新更新head和tail
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
2.链式队列
用链表实现的队列叫作链式队列
3.循环队列
循环队列仍然是基于数组实现的，使用一组地址连续的存储单元依次存放从队头到队尾的元素，且仍然设置两个指针front，rear。注意的是，其实这两个指针是整数型的，起得是知识的作用便于理解，所以称之为指针。这两个指针，一个指着队头，一个指着队尾。
这两个指针可以看做动态的过程，即这两个指针其实是互相追赶的。在追赶中就是队列中元素添加和删除的过程。当rear追到front时就表示队列已经满了，当front追上rear时就表示队列已经空了。
4.阻塞队列
阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
5.并发队列
线程安全的队列我们叫作并发队列。
6.无界队列
无界队列：指的是没有设置固定大小的队列。这些队列的特点是可以直接入列，直到溢出。当然现实几乎不会有到这么大的容量（超过 Integer.MAX_VALUE），所以从使用者的体验上，就相当于 “无界”。比如没有设定固定大小的 LinkedBlockingQueue。
7.有界队列
有界队列：就是有固定大小的队列。比如设定了固定大小的 LinkedBlockingQueue，又或者大小为 0，只是在生产者和消费者中做中转用的 SynchronousQueue。
三、Java中的队列（Queue）
源码：
//Queue继承于Collection接口
public interface Queue<E> extends Collection<E> {
/**
* Inserts the specified element into this queue if it is possible to do so
* immediately without violating capacity restrictions, returning
* {@code true} upon success and throwing an {@code IllegalStateException}
* if no space is currently available.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Collection#add})
* @throws IllegalStateException if the element cannot be added at this
* time due to capacity restrictions
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this queue
* @throws NullPointerException if the specified element is null and
* this queue does not permit null elements
* @throws IllegalArgumentException if some property of this element
* prevents it from being added to this queue
*/
boolean add(E e);
/**
* Inserts the specified element into this queue if it is possible to do
* so immediately without violating capacity restrictions.
* When using a capacity-restricted queue, this method is generally
* preferable to {@link #add}, which can fail to insert an element only
* by throwing an exception.
*
* @param e the element to add
* @return {@code true} if the element was added to this queue, else
* {@code false}
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this queue
* @throws NullPointerException if the specified element is null and
* this queue does not permit null elements
* @throws IllegalArgumentException if some property of this element
* prevents it from being added to this queue
*/
boolean offer(E e);
/**
* Retrieves and removes the head of this queue. This method differs
* from {@link #poll poll} only in that it throws an exception if this
* queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
E remove();
/**
* Retrieves and removes the head of this queue,
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, or {@code null} if this queue is empty
*/
E poll();
/**
* Retrieves, but does not remove, the head of this queue. This method
* differs from {@link #peek peek} only in that it throws an exception
* if this queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
E element();
/**
* Retrieves, but does not remove, the head of this queue,
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, or {@code null} if this queue is empty
*/
E peek();
}
JAVA中的队列分为阻塞队列和非阻塞队列两类
一.非阻塞队列（线程不安全）
常用的非阻塞队列有三个：LinkedList、PriorityQueue和ConcurrentLinkedQueue.
1、LinkedList
LinkedList队列用法主要来自于Deque,而Deque继承自Queue。
2、PriorityQueue（优先队列）
队列的规则是先进先出，后进后出。
队列无法处理插队这件事情，PriorityQueue和Queue的区别在于，它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。
要使用PriorityQueue，我们就必须给每个元素定义“优先级”。
PriorityQueue非线程安全。
//自定义的比较器，降序排列
static Comparator<Integer> cmp = new Comparator<Integer>() {
public int compare(Integer e1, Integer e2) {
return e2 - e1;
}
};
public static void main(String[] args) {
//不用比较器，默认升序排列
Queue<Integer> q = new PriorityQueue<>();
q.add(3);
q.add(2);
q.add(4);
while(!q.isEmpty())
{
System.out.print(q.poll()+" ");
}
/**
* 输出结果
* 2 3 4
*/
//使用自定义比较器，降序排列
Queue<Integer> qq = new PriorityQueue<>(cmp);
qq.add(3);
qq.add(2);
qq.add(4);
while(!qq.isEmpty())
{
System.out.print(qq.poll()+" ");
}
/**
* 输出结果
* 4 3 2
*/
}
2、ConcurrentLinkedQueue（并发容器，线程安全的非阻塞队列）
ConcurrentLinkedQueue是线程安全的队列，它适用于“高并发”的场景。
它是一个基于链接节点的无界线程安全队列，按照 FIFO（先进先出）原则对元素进行排序。队列元素中不可以放置null元素（内部实现的特殊节点除外）。
实现安全队列的方式有2种：
方式1：加锁，即阻塞队列。
方式2：使用循环CAS算法实现。
什么是CAS
CAS全称Compare and swap，比较和替换。是设计并发算法时用到的一种技术，比较和替换是使用一个期望值和一个变量的当前值进行比较，如果当前变量的值与我们期望的值相等，就使用一个新值替换当前变量的值。
二.阻塞队列（线程安全）
常用的非阻塞队列有七个
1、ArrayBlockingQueue （由数组结构组成的有界阻塞队列）
2、LinkedBlockingQueue （由链表结构组成的有界阻塞队列）
3、PriorityBlockingQueue (支持优先级排序的无界阻塞队列)
4、DelayQueue(使用优先级队列实现的无界阻塞队列)
5、SynchronousQueue(不存储元素的阻塞队列)
6、LinkedTransferQueue(由链表结构组成的无界阻塞队列)
7、LinkedBlockingDeque(由链表结构组成的双向阻塞队列)
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: