Java中的Queue数据结构

发布时间：2023-05-11

Java中的Queue是一个基于先进先出（FIFO）原则的数据结构，它支持在队列头部插入元素、在队列尾部删除元素、查找元素、以及获取队列的状态等基本操作。Queue的实现类有很多，包括了ArrayDeque、LinkedList、PriorityQueue等等，每个实现类又有其自身的特点。下面从多个方面来详细阐述Java中的Queue数据结构。

一、Queue的基本操作

Queue是一个接口，它定义了以下基本操作：

  1. boolean add(E e) ：将指定元素插入队列尾部，如果队列已满，抛出IllegalStateException异常。
  2. boolean offer(E e) ：将指定元素插入队列尾部，如果队列已满返回false。
  3. E remove() ：将队列头部元素弹出，并返回弹出的元素，如果队列为空，抛出NoSuchElementException异常。
  4. E poll() ：将队列头部元素弹出，并返回弹出的元素，如果队列为空，返回null。
  5. E element() ：获取队列头部元素，但不弹出，如果队列为空，抛出NoSuchElementException异常。
  6. E peek() ：获取队列头部元素，但不弹出，如果队列为空，返回null。 下面是一个基于ArrayDeque实现Queue的示例：
import java.util.ArrayDeque;
import java.util.Queue;
public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new ArrayDeque<>();
        queue.add("java");
        queue.add("python");
        queue.add("javascript");
        System.out.println("队列的头部元素是：" + queue.element());
        while(!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

上述示例中，我们使用了ArrayDeque实现了一个队列，并向其中添加了三个元素。然后通过element()方法获取队列头部元素，最后通过poll()方法弹出并输出了队列中的所有元素。

二、Queue的实现类

Java中，Queue的实现类有多种，我们可以根据具体需求来选择合适的实现类。主要有以下几种：

  1. ArrayDeque：该实现类是一个基于数组实现的双端队列，可以在队列头部和尾部插入、删除元素，因此不仅可以用于队列，还可以用于栈的实现。
  2. LinkedList：该实现类是一个基于链表实现的队列，可以将元素任意添加、删除，支持高效的线性遍历操作。
  3. PriorityQueue：该实现类是一个基于堆实现的优先队列，可以按照自定义的顺序获取队列中的元素。 下面是一个使用PriorityQueue实现的队列示例：
import java.util.PriorityQueue;
import java.util.Queue;
public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new PriorityQueue<>();
        queue.offer(5);
        queue.offer(3);
        queue.offer(7);
        queue.offer(1);
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

上述示例中，我们使用了PriorityQueue实现一个队列，并添加了四个元素，然后打印出了队列中的元素。由于PriorityQueue是一个优先队列，我们这里添加的元素默认是按照自然顺序递增的。

三、Queue的应用场景

Queue数据结构在日常开发中有着广泛的应用场景，比如以下几个方面：

  1. 消息队列：用于消息的异步处理，可以解决高并发场景下的服务优化问题。
  2. 线程池：用于线程池的任务队列，当线程池中所有线程都在处理任务时，新任务会被加入队列中等待执行。
  3. 数据库连接池：用于多线程并发访问数据库时，通过队列管理连接，实现线程池之间复用数据库连接的功能。 下面是一个使用Queue实现线程池示例：
import java.util.LinkedList;
import java.util.Queue;
public class ThreadPool {
    private int maxCount;
    private WorkerThread[] workerThreads;
    private Queue<Runnable> taskQueue = new LinkedList<>();
    public ThreadPool(int count) {
        maxCount = count;
        workerThreads = new WorkerThread[maxCount];
        for (int i = 0; i < maxCount; i++) {
            workerThreads[i] = new WorkerThread();
            workerThreads[i].start();
        }
    }
    public void execute(Runnable task) {
        synchronized (taskQueue) {
            taskQueue.offer(task);
            taskQueue.notify();
        }
    }
    private class WorkerThread extends Thread {
        public void run() {
            while (true) {
                Runnable task;
                synchronized (taskQueue) {
                    while (taskQueue.isEmpty()) {
                        try {
                            taskQueue.wait();
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                    }
                    task = taskQueue.poll();
                }
                task.run();
            }
        }
    }
}

上述示例中，我们使用一个Queue来管理线程池中的任务，当线程池中所有线程都在处理任务时，新任务会被加入队列中等待执行。

四、Queue的遍历

Queue数据结构可以用Iterator或者foreach遍历，遍历的顺序是按照元素插入队列的顺序进行的。下面是一个使用foreach遍历LinkedList队列的示例：

import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("java");
        queue.offer("python");
        queue.offer("javascript");
        for (String s : queue) {
            System.out.println(s);
        }
    }
}

上述示例中，我们使用foreach遍历了一个LinkedList队列，并输出了队列中的所有元素。同样的，我们也可以使用Iterator来遍历Queue数据结构。

五、Queue的注意事项

  1. Queue不支持null元素，插入null元素会抛出NullPointerException异常。
  2. Queue的size()方法可能会因为并发操作而不准确，因此不能完全依赖于它。
  3. Queue的实现类都是线程安全的，可以用于多线程并发操作。
  4. 使用Queue时应注意队列容器的大小，避免因队列容量不足导致插入、删除元素失败的情况发生。

总结

Java中的Queue是一个基于先进先出原则的数据结构，可以在队列头部插入元素，也可以在队列尾部删除元素。Queue的实现类有很多种，比如ArrayDeque、LinkedList、PriorityQueue等等。Queue数据结构在日常开发中有广泛的应用，比如消息队列、线程池、数据库连接池等等。在使用Queue时，应注意队列容器的大小，以及Queue的线程安全问题等注意事项。

推荐文章