当前位置：首页 > article >正文

Java Queue实现类面试题

article 2025/2/25 18:01:43

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");   // 队列满时返回false
        try {
            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;
        }
        
        @Override
        public long getDelay(TimeUnit unit) {
            return unit.convert(delayTime - System.currentTimeMillis(), 
                              TimeUnit.MILLISECONDS);
        }
        
        @Override
        public 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;
        
        // ArrayBlockingQueue
        BlockingQueue<Integer> abq = new ArrayBlockingQueue<>(n);
        testQueue("ArrayBlockingQueue", abq, n);
        
        // LinkedBlockingQueue
        BlockingQueue<Integer> lbq = new LinkedBlockingQueue<>();
        testQueue("LinkedBlockingQueue", lbq, n);
        
        // ConcurrentLinkedQueue
        Queue<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));
    }
}