面试题：使用数组实现一个简单的阻塞队列
这道题是我亲身经历的一道大厂面试题，非常值得分享！
这道题可以分为两个步骤进行编码解答，第一步是基于数组实现一个队列，第二步是实现线程阻塞。
如果是基于数组实现栈的数据结构，那么我们只需要一个指针进行来回移动即可。
想象一下，脑海中有一个竖立起来的栈，指针上移代表元素进栈，指针下移，代表元素出栈，整个过程只需要一个指针进行上下移动即可。
由此可以写出下面的代码：
import java.util.Arrays;
import java.util.EmptyStackException;
public class ArrayStack {
private Object[] elements = new Object[16]; //数组大小默认16
private int count; //1.-1后指向栈内末尾的元素 2.统计栈内元素的数量
public void push(T e){
//数组扩容
if (count == elements.length){
elements = Arrays.copyOf(elements,2*count+1);
}
elements[count++] = e;
}
public T pop(){
if (count == 0){
throw new EmptyStackException();
}
T o = (T) elements[--count];
elements[count] = null; //防止内存泄漏
return o;
}
public static void main(String[] args) {
ArrayStack arrayStack = new ArrayStack<>();
arrayStack.push(1);
arrayStack.push(2);
System.out.println(arrayStack.pop()); //2
System.out.println(arrayStack.pop()); //1
}
}
但是，基于数组实现队列却需要两个指针进行来回移动。
想象一下，脑海中有一个横放的空队列，在向队列进行ADD操作时，ADD指针从首端右移，直到移到末端填满队列；在向一个满队列进行GET操作时，GET指针从首端右移，直到移到末端取出所有元素。
这些步骤都是需要前提条件的，满队列无法进行ADD操作，同理，空队列无法进行GET操作，在ADD和GET操作之前还需要对此进行检查。
其次，ADD和GET指针会一直循环移动下去，它们移动到末端并不代表任何意义（即ADD指针移动到末端不代表队列已满，GET指针移动到末端不代表队列已空），所以，我们需要一个变量用做计数器，专门负责统计队列元素数量，检查队列是否已满或已空。
至于阻塞/唤醒部分的逻辑就比较简单了，只需要使GET线程访问空队列时进行阻塞，ADD线程访问满队列时进行阻塞即可，并在GET方法、ADD方法操作结束时唤醒一下对方线程，如果对方正在阻塞状态就可以被唤醒继续向下运行。
由此可以写出下面的代码：
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class ArrayBlockingQueue {
private Lock lock = new ReentrantLock();
private Object[] item;
//两个指针负责ADD与GET操作
//count负责统计元素数量
private int addIndex, getIndex, count;
//等待、通知
private Condition addCondition = lock.newCondition();
private Condition getCondition = lock.newCondition();
public ArrayBlockingQueue(int size) {
item = new Object[size];
}
public void add(T t) {
lock.lock();
try {
System.out.println("正在ADD对象：" + t);
while (count == item.length) {
try {
System.out.println("队列已满，阻塞ADD线程");
addCondition.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
//队列未满，添加对象并使计数器+1
item[addIndex++] = t;
count++;
//ADD指针指向末端，重置
if (addIndex == item.length) {
addIndex = 0;
}
System.out.println("唤醒GET线程");
getCondition.signal();
} finally {
lock.unlock();
}
}
public T get() {
lock.lock();
try {
while (count == 0) {
try {
System.out.println("队列空了，阻塞GET线程");
getCondition.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
//队列不空，获取对象并使计数器-1
T t = (T) item[getIndex++];
System.out.println("正在GET对象：" + t);
count--;
//GET指针到达末端、重置
if (getIndex == item.length) {
getIndex = 0;
}
System.out.println("唤醒ADD线程");
addCondition.signal();
return t;
} finally {
lock.unlock();
}
}
public static void main(String[] args) {
final ArrayBlockingQueue queue = new ArrayBlockingQueue<>(3);
new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < 3; i++) {
queue.add(i);
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}).start();
new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < 3; i++) {
queue.get();
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}).start();
}
}
// 打印输出：
// 正在ADD对象：0
// 唤醒GET线程
// 正在GET对象：0
// 唤醒ADD线程
// 队列空了，阻塞GET线程
// 正在ADD对象：1
// 唤醒GET线程
// 正在GET对象：1
// 唤醒ADD线程
// 队列空了，阻塞GET线程
// 正在ADD对象：2
// 唤醒GET线程
// 正在GET对象：2
// 唤醒ADD线程
程序员柯南∣一个有故事的公众号
作者：像风一样
出处：https://www.cnblogs.com/yueshutong/p/10689976.html
本站使用「署名 4.0 国际」创作共享协议，转载请在文章明显位置注明作者及出处。
分类: 算法
赞赏支持
你一赞赏, 我就写的更来劲了
+关注收藏7点赞
« 上一篇：是时候理解下HTTPS的原理及流程了
» 下一篇：面试题：请使用递归构建N叉树
posted @ 2019-04-11 15:26 像风一样i 阅读(410) 评论(0) 编辑 收藏
刷新评论刷新页面返回顶部
注册用户登录后才能发表评论，请 登录 或 注册，访问网站首页。
https://www.cnblogs.com/yueshutong/p/10689976.html