一文搞懂队列

队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。

和栈一样，队列是一种操作受限制的线性表。队列是先进先出（FIFO）的。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列和栈非常相似，栈有入栈和出栈两个基本操作操作，队列也有两个基本操作：入队（enqueue），把数据放到队尾。出队（dequeue）,从队头取出一个数据。

队列出队和入队的时间复杂度都是O(1)。

顺序队列

用数组实现的队列叫做顺序队列。

// 用数组实现的队列

public class ArrayQueue {

 // 数组：arr，数组大小：len

 private String[] arr;

 private int len = 0;

 // front 队头下标，rear 队尾下标

 private int front = 0;

 private int rear = 0;

 // 创建一个数组

 public ArrayQueue(int length) {

     items = new String[length];

     n = length;

 }

 // 入队

 public boolean enqueue(String item) {

     // 队列已满

     if (rear == len) return false;

     items[rear] = item;

     rear++;

     return true;

 }

 // 出队

 public String dequeue() {

     // 队列为空

     if (front == rear) return null;

     String result = items[front];

     front++;

     return result;

 }

}

队列有两个指针一个是front指向队头，一个是rear指向队尾。

如a、b、c、d、e 入列后，队头指针指向是的下标为0的位置，队尾指针指向的是下标为6的位置。

然后不断进行出列和入列的操作，两个指针也不断往后移动，当队尾指针到达最右边的位置，就算数组中还有一个空闲的空间，但也没有办法继续向队列中加数据了。

回想数组空间不足，进行扩容，迁移数据的操作。

同理在这里也要对队列进行数据搬迁，只要在入列的时候判断一下 （rear == len ）队列尾是已经到最后的话就进行数据迁移，然后重新计算两个指针的指向，然后再入列就可以了。

链式队列

用链表实现的队列叫做链式队列。同样需要两个指针，队头指向第一个节点，队尾指向最后一个节点。

入队：rear -> next = newnode , rear = rear -> next

出队：front = front-> next

循环队列

用数组实现队列的时候，如果 rear == len ，就需要进行数据迁移操作。

了避免进行数据迁移操作，可以用循环队列来解决。

循环队列首尾相接。

队空条件：front == rear

队满条件：(rear + 1) % len = front

确定好上面的两个条件，代码实现就很容易了。

阻塞队列

在队列的基础上增加了阻塞操作。

队列为空，队头取数据阻塞，等队列中有数据才会返回数据。

队列已满，队尾插数据阻塞，等队列中有空闲位置再插入数据。

其实这就是「生产者 - 消费者模型」，还可以通过配置多个「消费者」来对应一个「生产者」。

并发队列

在多线程情况下，会有多个线程访问队列，会存在线程安全问题。

线程安全的队列叫做并发队列。

通过在enqueue()、dequeue()加锁来实现。