链式队列通过链表实现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."); } }
评论（已关闭）
评论已关闭