队列，是一个先进先出的数据结构，与栈一样，队列也是一种数组与链表的一种的受限操作所形成的特殊数据结构。
相比于栈的先进后出，队列的先进先出是怎么样一个抽象模型呢。
队列模型
队列只支持两个操作，分别是入队和出队，入队只能在队尾进行，出队只能在队头进行。
队列作为一种基础的数据结构，它的应用是十分广泛的。其中以它的一些特殊实现为最，比如循环队列，阻塞队列，并发队列，优先队列等。
下面以数组来实现一个简单的队列。
/**
* 以数组实现队列
*/
public class Queue_4_19 {
private static int DEFAULT_SIZE =10;
private int tail =0;// 队尾
private int font =0;// 队头
private int[]array;
public Queue_4_19() {
this(DEFAULT_SIZE);
}
public Queue_4_19(int size) {
array =new int[size];
}
private boolean enqueue(int val) {
if (tail ==array.length -1) {// 判满
return false;
}
array[tail++] = val;
return true;
}
private boolean dequeue() {
if (font ==tail) {// 判空
return false;
}
font++;
return true;
}
}
从上面的代码可以看出来，当tail==n时，这个队列就无法插入新元素了，那么当里面的元素全部出队时，这个队列就不可用了，那么我们就可以设计一个循环队列来解决这种问题。
与普通队列不同的是，循环队列可以理解为一个圆形环。下面放上两张图，可以更好的理解。
循环队列A
循环队列B
从上图的循环队列A可以看出，此时的队尾已经指向了数组的最后一个下标，按照普通的队列，这个时候已经无法插入了，但是我们可以看到，此时数组下标0-3都是没有元素，表明可以插入的，那我们可以怎么做呢，这个时候，我们把数据a放进数组，但是我们不把tail更新为8，而是更新为0，然后继续放入b，把tail更新为1。然后就变成了循环队列B这个样子。
这就是循环队列的设计理念，与普通队列一样，循环队列的关键也在于判空与判满，就像循环队列A哪个图，如果依然按照tail==array.length -1来判满，那么就无法插入新的数据，这是不对的。但是判空与普通队列一样，依然是font==tail。
下面上一张图，可以更好理解怎么判满：
循环队列判满
计算下标，多画一些图，就可以得到规律，当(tail+1)%(array.length)==font时，就标明队列已经满了，我们这个样子设计，会浪费一个存储单元，为什么要这个样子，因为如果tail==font，那么就和判空冲突了，当然，这个也可以解决，使用一个计数器就可以，不过相比于在维护一个计数器，单纯浪费一个存储单元更可以接受，也更简单。下面写出循环队列的实现代码：
/**
* Insert an element into the circular queue. Return true if the operation is successful.
*/
public boolean enQueue(AnyType value) {//需要判断满
if (isFull())
return false;
array[tail] = value;
tail = (tail +1) %array.length;
return true;
}
/**
* Delete an element from the circular queue. Return true if the operation is successful.
*/
public boolean deQueue() {
if(isEmpty())
return false;
font = (font+1)%array.length;
return true;
}
/**
* Checks whether the circular queue is empty or not.
*/
public boolean isEmpty() {
return font ==tail;//头指针尾指针指向同一位置
}
/**
* Checks whether the circular queue is full or not.
*/
public boolean isFull() {
return (tail +1) %array.length ==font;
}
这就是循环队列的实现。相比于单纯的队列，更加应用广泛。
阻塞队列
相比于上面的普通队列，循环队列，阻塞队列的应用场景更加广泛，组织队列的含义就是，当队列空的时候，我们就阻止从队头取数据，当队列满的时候，我们就阻止从队尾放数据。
阻塞队列A
阻塞队列B
基于这样一个概念，我们可以轻松的设计出一个生产者--消费者模型，可以有效协调生产者和消费者的效率，当生产者生产过多二消费不了时，队列就会满，此时就停止生产，而当消费过多生产不够时，就阻止消费操作。同时，我们也可以配置多个消费者同时消费，当生产过多时，这样可以更好的利用资源。
上面就是队列的一些概念与实现。也可以做一些专门题目进行训练。
网友评论