BAT面试题:使用数组实现一个简单的阻塞队列

时间:2022-12-10 14:43:57

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

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

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

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

由此可以写出下面的代码:

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线程