队列其实和栈的特性刚好相反，队列是先进先出的，这个特性很容易就想到排队。
队列的基本操作
- 入队(enqueue)，即从队尾插入一个元素
- 出队(dequeue)，即从队首取出一个元素
顺序队列和链式队列
顺序队列和链式队列是两种非常常见（但日常工作其实不太常用）的队列，区别在于，顺序队列是用数组实现的，链式队列是用链表实现的。
以顺序队列为例
package queue;
/**
* @author TioSun
* 顺序队列
*/
public class ArrayQueue {
/**
* 用于存放队列数据
*/
private String[] items;
/**
* 数组大小
*/
private int n = 0;
/**
* 队首标记
*/
private int head = 0;
/**
* 队尾标记
*/
private int tail = 0;
/**
* 初始化一个容量为capacity的队列
*
* @param capacity 队列容量
*/
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
/**
* 入队操作
*
* @param item 入队数据
* @return 是否入队成功
*/
public boolean enqueue(String item) {
if (tail == n) {
if (head == 0) {
// tail == n and head == 0，表示队满，无法再入队
return false;
}
rearrange();
}
items[tail] = item;
++tail;
return true;
}
/**
* 重新整理数组
*/
private void rearrange() {
// 将数据移至数组首部
for (int i = head; i < tail; i++) {
items[i-head] = items[i];
}
// 重置队尾标记
tail -= head;
// 重置队首标记
head = 0;
}
/**
* 出队操作
*
* @return 队首数据
*/
public String dequeue() {
// 如果head == tail 表示队列为空
if (head == tail)
return null;
String ret = items[head];
++head;
return ret;
}
}
循环队列
我们可以很直接的体会到正常情况下，入队或出队操作都是O(1)的复杂度，但是当tail == n的时候，需要对数组进行搬移，时间复杂度为O(n)。那是否有办法避免这种情况，这个时候就需要搬出循环队列了。
什么是循环队列？
循环队列顾名思义，是一个环型结构，但这只是模型概念，真实数据结构还是使用数组
image.png
可以看到，虽然tail指针处在数组的最后一位，但是当有新数据入队时，tail指针会直接跨越数组，变成0的位置，这样就不存在tail == n 的情况，也就不会发生对数组的搬移动作，保证入队的时间复杂度是O(1)。
循环数组的队空判断依然是tail == head，但是队满判断会有所不一样，其队满判断是(tail+1)%n == head（%n是为了处理head == 0, tail == n-1的情况）如图所示：
image.png
大家可能会发现，判断队满之后，其实下标13的位置数据还是空的，所以这种实现下，会浪费一个位置。
代码实现如下
package queue;
/**
* @author sunyixuan
* 循环队列
*/
public class CircularQueue {
/**
* 用于存放队列数据
*/
private String[] items;
/**
* 数组大小
*/
private int n = 0;
/**
* 队首标记
*/
private int head = 0;
/**
* 队尾标记
*/
private int tail = 0;
/**
* 初始化一个容量为capacity的队列
*
* @param capacity 队列容量
*/
public CircularQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
/**
* 入队操作
*
* @param item 入队数据
* @return 是否入队成功
*/
public boolean enqueue(String item) {
// 队列满了
if ((tail + 1) % n == head) {
return false;
}
items[tail] = item;
tail = (tail + 1) % n;
return true;
}
/**
* 出队操作
*
* @return 队首数据
*/
public String dequeue() {
// 如果head == tail 表示队列为空
if (head == tail) {
return null;
}
String ret = items[head];
head = (head + 1) % n;
return ret;
}
}
其他日常工作中常用的队列
阻塞队列
阻塞队列顾名思义，在队空时会阻塞出队动作，队满时会阻塞入队 动作。有没有很眼熟？是的，它常被用来实现生产-消费者模型，当生产速度大于消费速度时，导致队满，然后生产者的生产动作即被阻塞。消费速度大于生产速度时同理。而且可以根据具体情况去调配生产或消费者的数量。
并发队列
并发队列即线程安全的队列，支持在多线程情况下使用，简单实现可以直接在入队或者出队动作上加锁，但是这样锁的粒度会比较粗，如果追求高性能的话，可以尝试用CAS（compare and set）去实现高效的并发队列。
网友评论