Java Queue实现类面试题
ArrayDeque
Q1: ArrayDeque的实现原理是什么？
ArrayDeque是基于循环数组实现的双端队列。
public class ArrayDequePrincipleExample {// 模拟ArrayDeque的基本实现public class SimpleArrayDeque<E> {private static final int MIN_INITIAL_CAPACITY = 8;private Object[] elements;private int head;private int tail;@SuppressWarnings("unchecked")public SimpleArrayDeque() {elements = new Object[MIN_INITIAL_CAPACITY];}// 从队首添加元素public void addFirst(E e) {if (e == null) throw new NullPointerException();head = (head - 1) & (elements.length - 1);elements[head] = e;if (head == tail) doubleCapacity();}// 从队尾添加元素public void addLast(E e) {if (e == null) throw new NullPointerException();elements[tail] = e;tail = (tail + 1) & (elements.length - 1);if (tail == head) doubleCapacity();}// 扩容private void doubleCapacity() {int p = head;int n = elements.length;int r = n - p;int newCapacity = n << 1;Object[] a = new Object[newCapacity];System.arraycopy(elements, p, a, 0, r);System.arraycopy(elements, 0, a, r, p);elements = a;head = 0;tail = n;}}
}
Q2: ArrayDeque相比LinkedList有什么优势？
public class ArrayDequeVsLinkedListExample {public void comparePerformance() {ArrayDeque<Integer> arrayDeque = new ArrayDeque<>();LinkedList<Integer> linkedList = new LinkedList<>();int n = 1000000;// 1. 添加性能对比long start = System.currentTimeMillis();for (int i = 0; i < n; i++) {arrayDeque.addLast(i);}System.out.println("ArrayDeque添加耗时：" + (System.currentTimeMillis() - start));start = System.currentTimeMillis();for (int i = 0; i < n; i++) {linkedList.addLast(i);}System.out.println("LinkedList添加耗时：" + (System.currentTimeMillis() - start));// 2. 随机访问性能对比start = System.currentTimeMillis();for (int i = 0; i < n; i++) {arrayDeque.contains(i);}System.out.println("ArrayDeque查找耗时：" + (System.currentTimeMillis() - start));start = System.currentTimeMillis();for (int i = 0; i < n; i++) {linkedList.contains(i);}System.out.println("LinkedList查找耗时：" + (System.currentTimeMillis() - start));}
}
PriorityQueue
Q3: PriorityQueue的实现原理是什么？
PriorityQueue是基于堆（最小堆）实现的优先级队列。
public class PriorityQueuePrincipleExample {// 1. 自然排序public void naturalOrdering() {PriorityQueue<Integer> pq = new PriorityQueue<>();pq.offer(3);pq.offer(1);pq.offer(2);while (!pq.isEmpty()) {System.out.println(pq.poll()); // 输出1,2,3}}// 2. 自定义排序public void customOrdering() {PriorityQueue<Person> pq = new PriorityQueue<>((p1, p2) -> {int ageCompare = Integer.compare(p1.getAge(), p2.getAge());if (ageCompare != 0) return ageCompare;return p1.getName().compareTo(p2.getName());});pq.offer(new Person("Tom", 20));pq.offer(new Person("Jerry", 18));pq.offer(new Person("Bob", 20));}// 3. 堆操作示例public void heapOperations() {PriorityQueue<Integer> pq = new PriorityQueue<>();// 添加元素（上浮）pq.offer(5);pq.offer(2);pq.offer(8);// 删除元素（下沉）int min = pq.poll(); // 获取并删除最小元素// 查看最小元素int peek = pq.peek(); // 只查看不删除}
}
BlockingQueue
Q4: BlockingQueue的特点和实现类有哪些？
public class BlockingQueueExample {// 1. ArrayBlockingQueue示例public void arrayBlockingQueueDemo() {ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<>(3);// 生产者线程new Thread(() -> {try {queue.put("1"); // 阻塞式添加queue.put("2");queue.put("3");queue.put("4"); // 队列满，阻塞} catch (InterruptedException e) {e.printStackTrace();}}).start();// 消费者线程new Thread(() -> {try {Thread.sleep(1000);System.out.println(queue.take()); // 阻塞式获取System.out.println(queue.take());} catch (InterruptedException e) {e.printStackTrace();}}).start();}// 2. LinkedBlockingQueue示例public void linkedBlockingQueueDemo() {LinkedBlockingQueue<String> queue = new LinkedBlockingQueue<>();// 无界队列，默认容量Integer.MAX_VALUE// 添加元素的不同方法queue.add("1"); // 队列满时抛出异常queue.offer("2"); // 队列满时返回falsetry {queue.put("3"); // 队列满时阻塞} catch (InterruptedException e) {e.printStackTrace();}}// 3. DelayQueue示例public static class DelayedElement implements Delayed {private final String data;private final long delayTime;public DelayedElement(String data, long delay) {this.data = data;this.delayTime = System.currentTimeMillis() + delay;}@Overridepublic long getDelay(TimeUnit unit) {return unit.convert(delayTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);}@Overridepublic int compareTo(Delayed o) {return Long.compare(getDelay(TimeUnit.MILLISECONDS), o.getDelay(TimeUnit.MILLISECONDS));}}public void delayQueueDemo() {DelayQueue<DelayedElement> queue = new DelayQueue<>();queue.offer(new DelayedElement("1", 1000)); // 延迟1秒queue.offer(new DelayedElement("2", 2000)); // 延迟2秒try {System.out.println(queue.take().data); // 1秒后输出"1"System.out.println(queue.take().data); // 2秒后输出"2"} catch (InterruptedException e) {e.printStackTrace();}}
}
Q5: 如何选择合适的Queue实现类？
public class QueueSelectionExample {public void demonstrateUsage() {// 1. 一般用途，双端队列Deque<String> arrayDeque = new ArrayDeque<>();// 2. 需要优先级排序PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();// 3. 固定大小，线程安全BlockingQueue<String> arrayBlockingQueue = new ArrayBlockingQueue<>(10);// 4. 无界，线程安全BlockingQueue<String> linkedBlockingQueue = new LinkedBlockingQueue<>();// 5. 延迟队列DelayQueue<DelayedElement> delayQueue = new DelayQueue<>();// 6. 优先级阻塞队列BlockingQueue<String> priorityBlockingQueue = new PriorityBlockingQueue<>();}// 使用场景示例public void usageScenarios() {// 1. 实现栈Deque<String> stack = new ArrayDeque<>();stack.push("A");stack.pop();// 2. 任务优先级排序PriorityQueue<Task> taskQueue = new PriorityQueue<>((t1, t2) -> Integer.compare(t2.getPriority(), t1.getPriority()));// 3. 生产者-消费者模式BlockingQueue<String> messageQueue = new ArrayBlockingQueue<>(100);// 生产者线程new Thread(() -> {try {messageQueue.put("message");} catch (InterruptedException e) {Thread.currentThread().interrupt();}}).start();// 消费者线程new Thread(() -> {try {String message = messageQueue.take();process(message);} catch (InterruptedException e) {Thread.currentThread().interrupt();}}).start();}private void process(String message) {// 处理消息}
}
Q6: 并发队列的性能考虑
public class ConcurrentQueuePerformanceExample {// 1. 不同并发队列的性能对比public void comparePerformance() {int n = 100000;// ArrayBlockingQueueBlockingQueue<Integer> abq = new ArrayBlockingQueue<>(n);testQueue("ArrayBlockingQueue", abq, n);// LinkedBlockingQueueBlockingQueue<Integer> lbq = new LinkedBlockingQueue<>();testQueue("LinkedBlockingQueue", lbq, n);// ConcurrentLinkedQueueQueue<Integer> clq = new ConcurrentLinkedQueue<>();testQueue("ConcurrentLinkedQueue", clq, n);}private void testQueue(String name, Queue<Integer> queue, int n) {long start = System.currentTimeMillis();// 多线程添加元素Thread[] producers = new Thread[4];for (int i = 0; i < producers.length; i++) {producers[i] = new Thread(() -> {for (int j = 0; j < n/4; j++) {queue.offer(j);}});producers[i].start();}// 等待所有生产者完成for (Thread producer : producers) {try {producer.join();} catch (InterruptedException e) {Thread.currentThread().interrupt();}}System.out.println(name + " 耗时：" + (System.currentTimeMillis() - start));}
}
面试关键点
- 理解ArrayDeque的循环数组实现
- 掌握PriorityQueue的堆实现
- 了解BlockingQueue的特点和实现类
- 熟悉不同队列的使用场景
- 掌握并发队列的性能特点
- 理解阻塞队列的工作原理
- 注意队列的边界条件处理
- 掌握队列的选择原则
