Java链式队列实现与应用技巧

链式队列通过链表实现FIFO，适合大小不确定的场景，而数组队列适用于容量固定且追求高性能的情况；实际应用包括任务调度、消息队列和多线程下载器；需注意空指针、内存泄漏和线程安全问题，多线程下推荐使用ConcurrentLinkedQueue保证安全。

用链表实现链式队列，关键在于利用链表的特性来模拟队列的先进先出（FIFO）原则。简单来说，就是用链表的节点来存储队列中的元素，并维护一个指向队头和队尾的指针。

解决方案

public class LinkedQueue<T> {

    private static class Node<T> {
        T data;
        Node<T> next;

        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node<T> head; // 队头
    private Node<T> tail; // 队尾
    private int size;

    public LinkedQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    public boolean isEmpty() {
        return head == null; // 或者 size == 0;
    }

    public int size() {
        return size;
    }

    public void enqueue(T data) {
        Node<T> newNode = new Node<>(data);
        if (isEmpty()) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }

    public T dequeue() {
        if (isEmpty()) {
            return null; // 或者抛出异常，根据实际情况选择
        }
        T data = head.data;
        head = head.next;
        if (head == null) {
            tail = null; // 队列为空时，tail也要置空
        }
        size--;
        return data;
    }

    public T peek() {
        if (isEmpty()) {
            return null; // 或者抛出异常
        }
        return head.data;
    }

    public static void main(String[] args) {
        LinkedQueue<Integer> queue = new LinkedQueue<>();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        System.out.println("Queue size: " + queue.size()); // Output: Queue size: 3
        System.out.println("Dequeue: " + queue.dequeue()); // Output: Dequeue: 1
        System.out.println("Peek: " + queue.peek());       // Output: Peek: 2
        System.out.println("Queue size: " + queue.size()); // Output: Queue size: 2
    }
}

链式队列和数组队列，我该选哪个？

数组队列通常在你知道队列的最大容量，并且需要高性能的场景下更合适。因为数组在内存中是连续存储的，访问速度快。但数组队列的缺点是大小固定，容易出现空间浪费或溢出的情况。

链式队列则更灵活，可以动态地增加或减少队列的大小，不需要预先知道队列的最大容量。但是，链式队列的内存占用比数组队列略高，因为每个节点都需要额外的空间来存储指针。 选择哪个，还是得看你的具体需求。如果对内存使用非常敏感，且队列大小可预测，数组队列可能更好。如果队列大小不确定，或者对内存占用不是特别敏感，链式队列会更方便。

链式队列在实际开发中有什么用？

链式队列在很多场景下都有应用，比如：

1. 任务调度： 在操作系统中，可以使用链式队列来管理等待执行的任务。
2. 消息队列： 在分布式系统中，可以使用链式队列来实现消息队列，用于异步地传递消息。
3. 缓冲： 在网络编程中，可以使用链式队列来缓冲数据，防止数据丢失。

举个实际的例子，假设你正在开发一个多线程下载器。你可以使用链式队列来管理下载任务。每个下载任务就是一个节点，当一个线程完成一个下载任务后，就从队列中取出一个新的任务来执行。 这样做的好处是，可以充分利用多线程的优势，提高下载速度。

使用链式队列时，需要注意哪些问题？

1. 空指针异常： 在出队操作时，需要判断队列是否为空，避免空指针异常。
2. 内存泄漏： 如果链式队列使用不当，可能会导致内存泄漏。例如，如果出队后没有将节点从内存中释放，就会造成内存泄漏。
3. 线程安全： 如果多个线程同时访问链式队列，需要考虑线程安全问题。可以使用锁或其他同步机制来保证线程安全。

关于线程安全，我再多说两句。如果你的链式队列需要在多线程环境下使用，那么你需要采取一些措施来保证线程安全。 一种常见的做法是使用synchronized关键字来同步对队列的操作。 另一种做法是使用java.util.concurrent包中的线程安全队列，例如ConcurrentLinkedQueue。 至于选择哪种方式，取决于你的具体需求和性能要求。 如果对性能要求比较高，可以考虑使用ConcurrentLinkedQueue，因为它使用了无锁算法，可以减少线程之间的竞争。

import java.util.concurrent.ConcurrentLinkedQueue;

public class ThreadSafeLinkedQueue<T> {

    private ConcurrentLinkedQueue<T> queue = new ConcurrentLinkedQueue<>();

    public void enqueue(T data) {
        queue.offer(data);
    }

    public T dequeue() {
        return queue.poll();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public static void main(String[] args) throws InterruptedException {
        ThreadSafeLinkedQueue<Integer> queue = new ThreadSafeLinkedQueue<>();

        // 多个线程向队列中添加元素
        Thread producer1 = new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                queue.enqueue(i);
                System.out.println("Producer 1 enqueue: " + i);
                try {
                    Thread.sleep(100); // 模拟生产过程
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        });

        Thread producer2 = new Thread(() -> {
            for (int i = 10; i < 20; i++) {
                queue.enqueue(i);
                System.out.println("Producer 2 enqueue: " + i);
                try {
                    Thread.sleep(150); // 模拟生产过程
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        });

        // 单个线程从队列中取出元素
        Thread consumer = new Thread(() -> {
            while (!queue.isEmpty() || producer1.isAlive() || producer2.isAlive()) {
                Integer data = queue.dequeue();
                if (data != null) {
                    System.out.println("Consumer dequeue: " + data);
                }
                try {
                    Thread.sleep(200); // 模拟消费过程
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            System.out.println("Consumer finished.");
        });

        producer1.start();
        producer2.start();
        consumer.start();

        producer1.join();
        producer2.join();
        consumer.join();

        System.out.println("Main thread finished.");
    }
}