这道题是我亲身经历的一道大厂面试题,非常值得分享!

这道题可以分为两个步骤进行编码解答,第一步是基于数组实现一个队列,第二步是实现线程阻塞。

如果是基于数组实现栈的数据结构,那么我们只需要一个指针进行来回移动即可。

想象一下,脑海中有一个竖立起来的栈,指针上移代表元素进栈,指针下移,代表元素出栈,整个过程只需要一个指针进行上下移动即可。

由此可以写出下面的代码:
import java.util.Arrays; import java.util.EmptyStackException; public class
ArrayStack<T> { 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<Integer> 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<T> {
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<Integer> 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线程

友情链接
ioDraw流程图
API参考文档
OK工具箱
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:637538335
关注微信