链式队列通过链表实现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
}
}链式队列和数组队列，我该选哪个？
数组队列通常在你知道队列的最大容量，并且需要高性能的场景下更合适。因为数组在内存中是连续存储的，访问速度快。但数组队列的缺点是大小固定，容易出现空间浪费或溢出的情况。
立即学习“Java免费学习笔记（深入）”；
链式队列则更灵活，可以动态地增加或减少队列的大小，不需要预先知道队列的最大容量。但是，链式队列的内存占用比数组队列略高，因为每个节点都需要额外的空间来存储指针。 选择哪个，还是得看你的具体需求。如果对内存使用非常敏感，且队列大小可预测，数组队列可能更好。如果队列大小不确定，或者对内存占用不是特别敏感，链式队列会更方便。
链式队列在实际开发中有什么用？
链式队列在很多场景下都有应用，比如：
- 任务调度： 在操作系统中，可以使用链式队列来管理等待执行的任务。
- 消息队列： 在分布式系统中，可以使用链式队列来实现消息队列，用于异步地传递消息。
- 缓冲： 在网络编程中，可以使用链式队列来缓冲数据，防止数据丢失。
举个实际的例子，假设你正在开发一个多线程下载器。你可以使用链式队列来管理下载任务。每个下载任务就是一个节点，当一个线程完成一个下载任务后，就从队列中取出一个新的任务来执行。 这样做的好处是，可以充分利用多线程的优势，提高下载速度。
使用链式队列时，需要注意哪些问题？
- 空指针异常： 在出队操作时，需要判断队列是否为空，避免空指针异常。
- 内存泄漏： 如果链式队列使用不当，可能会导致内存泄漏。例如，如果出队后没有将节点从内存中释放，就会造成内存泄漏。
- 线程安全： 如果多个线程同时访问链式队列，需要考虑线程安全问题。可以使用锁或其他同步机制来保证线程安全。
关于线程安全，我再多说两句。如果你的链式队列需要在多线程环境下使用，那么你需要采取一些措施来保证线程安全。 一种常见的做法是使用
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.");
}
} 
